題目描述

給定一個長度為 n 的序列 a，一共有 m 個操作。
每次操作的內容為：給定 x,y，序列中所有 x 會變成 y。

同時我們有一份代碼：

int ans = 2147483647; for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {if (a[i] == a[j])ans = std::min(ans, j - i);} } std::cout << ans << std::endl;

請在每次修改后輸出代碼運行的結果。

輸入格式

第一行兩個數，表示 n,m。
第二行 n 個數，表示 a1,a2,?,an .
然后 m 行每行兩個數 x 和 y，表示序列中所有 x 會變成 y。

輸出格式

對于每次修改，輸出答案。

樣例

樣例輸入

5 10
2 7 6 3 8
6 1
7 1
1 3
5 6
1 7
9 5
1 10
7 6
7 5
3 9

樣例輸出

2147483647
1
1
1
1
1
1
1
1
1

數據范圍與提示

1≤n,m≤1000001≤n,m≤100000

每個出現的數字絕對值在 int 范圍內。

Solution

• 題意：給出 MM 個操作，將長度為 NN 序列中 所有的 某一個數字替換為另一個，

• 詢問每次操作后距離最近的兩個 相同 數字的距離。

• 由于每個位置上的數都只對它的 前驅和后繼 產生影響，

• 于是我們開 NN 個 setset （每個數一個），每次啟發式合并，將較小的暴力合并到大的上面。

• 每次在 setset 上 lower_bound()lower_bound() 計算前驅和后繼的貢獻即可。

• 如果不想離散化就用個 mapmap 來存這 NN 個 setset 。

• 時間復雜度 O(N?log?N)O(NlogN) ，常數較大。

Code

#include<cstdio> #include<algorithm> #include<set> #include<map> #include<cctype> using namespace std; map<int,set<int> >mp; int ans=2147483647; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline int min(int x,int y) {return x<y?x:y; } inline void update(int x,int y) {set<int>::iterator it=mp[x].lower_bound(y);if(it!=mp[x].end()) ans=min(ans,*it-y);if(it!=mp[x].begin()) ans=min(ans,y-*--it); } int main() {int n=read(),m=read();for(int i=1;i<=n;i++){int x=read();update(x,i);mp[x].insert(i);}while(m--){int x=read(),y=read();if(x^y){if(mp[x].size()>mp[y].size()) swap(mp[x],mp[y]);for(set<int>::iterator it=mp[x].begin();it!=mp[x].end();it++){update(y,*it);mp[y].insert(*it);}mp[x].clear();}write(ans),putchar('\n'); }return 0; }

總結

以上是生活随笔為你收集整理的LOJ #516. 「LibreOJ β Round #2」DP 一般看规律的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。