題目鏈接：點擊查看

題目大意：

題目分析：數(shù)據(jù)結(jié)構(gòu)的題目寫起來真好玩~（debug到吐）

考慮離線，題目實質(zhì)上就是維護兩個森林，然后對同一個序列進行的賦值操作，如果是對單一的森林進行加邊刪邊然后連通塊內(nèi)求值修改之類的話，不難想到克魯斯卡爾重構(gòu)樹，但兩個森林的話該怎么辦呢

注意到第一個森林中對連通塊的操作是加法，第二個森林中對連通塊的操作是置零

任取一個點 x 進行討論，假設(shè)現(xiàn)在不考慮第二個森林的貢獻，也就是忽略掉第二種操作和第四種操作，并且在每次操作后都記錄一下點 x 的值，更具體的，設(shè) val_x[ i?] 是在經(jīng)過第 i 個操作后，點 x 的值

現(xiàn)在假設(shè)第 r 個操作是?“ Q x ”，也就是在第 r 個操作時需要輸出 x 的值，但并不是需要輸出 val_x[ r ] ，因為 val_x 記錄的只是第一個森林的貢獻，為了計算總貢獻，我們需要知道在第 r 個操作之前，對于點 x 來說距離最近的一次操作 4，也就是第二個森林的置零操作，找到的這個位置記為 l，換句話說，現(xiàn)在在第 l 個操作時將點 x 置零，需要輸出第 r 個操作時 x 的值，也就是說在閉區(qū)間 [ l + 1 , r ] 內(nèi) val_x 的值只受到了第一個森林的影響，到此為止不難想到答案就是 val_x[ r ] - val_x[ l ] 了

綜上所述，我們將問題又進行了進一步的轉(zhuǎn)換：

先通過第二個森林求出每一個操作 Q x 的可行區(qū)間 [ l , r ] ，滿足：

當(dāng)前的操作 Q x 是第 r 次操作

第 l 次操作是對于點 x 進行的置零操作

閉區(qū)間 [ l + 1 , r ] 內(nèi)再無對于點 x 進行的置零操作

再通過第二個森林去維護每個點的 val_x，對于一個操作 Q x 來說，其通過上述操作求出的區(qū)間為 [ l , r ] ，那么在其 l 位置減去 val_x[ l ]，在其 r 位置減去 val_x[ r ] 就是操作 Q x 的答案

這樣就將第一個森林和第二個森林各自的作用區(qū)分開來，轉(zhuǎn)換成了兩個獨立的森林提供的貢獻

剩下的用克魯斯卡爾重構(gòu)樹亂搞就好了

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char op[N][2];int n,m,a[N];LL ans[N];vector<int>q[N];struct Ex_Kruskal {int f[N],L[N],R[N],sz[N],tot,index;vector<int>node[N];void init(int n){tot=0;index=n;for(int i=0;i<=n<<1;i++)f[i]=i;}int find(int x){return f[x]==x?x:f[x]=find(f[x]);}void addedge(int x,int y){int xx=find(x),yy=find(y);if(xx!=yy){f[xx]=f[yy]=++index;node[index].push_back(xx);node[index].push_back(yy);}}void dfs(int u){L[u]=++tot;sz[u]=(u<=n);for(auto v:node[u]){dfs(v);sz[u]+=sz[v];}R[u]=tot;} };struct Set1 {Ex_Kruskal kru;int n;struct Node{int l,r;LL sum;}tree[N<<2];void get_dfs(){n=kru.index;for(int i=1;i<=n;i++)if(kru.find(i)==i)kru.dfs(i);}void pushdown(int k){if(tree[k].sum){tree[k<<1].sum+=tree[k].sum;tree[k<<1|1].sum+=tree[k].sum;tree[k].sum=0;}}void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void update(int k,int l,int r,int val){if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].sum+=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);}void change(int x){update(1,kru.L[a[x]],kru.R[a[x]],kru.sz[a[x]]);}LL query(int k,int pos){if(tree[k].l==tree[k].r)return tree[k].sum;pushdown(k);int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)return query(k<<1,pos);elsereturn query(k<<1|1,pos);}LL ask(int x){return query(1,kru.L[a[x]]);} }t1;struct Set2 {Ex_Kruskal kru;int n;struct Node{int l,r;int time;}tree[N<<2];void get_dfs(){n=kru.index;for(int i=1;i<=n;i++)if(kru.find(i)==i)kru.dfs(i);}void pushdown(int k){if(tree[k].time){tree[k<<1].time=tree[k<<1|1].time=tree[k].time;tree[k].time=0;}}void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;tree[k].time=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void update(int k,int l,int r,int val){if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].time=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);}void change(int x){update(1,kru.L[a[x]],kru.R[a[x]],x);}int query(int k,int pos){if(tree[k].l==tree[k].r)return tree[k].time;pushdown(k);int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)return query(k<<1,pos);elsereturn query(k<<1|1,pos);}int ask(int x){return query(1,kru.L[a[x]]);} }t2;int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d%d",&n,&m);t1.kru.init(n),t2.kru.init(n);for(int i=1,x,y;i<=m;i++){scanf("%s%d",op[i],&x);switch(op[i][0]){case 'U':scanf("%d",&y);t1.kru.addedge(x,y);break; case 'M':scanf("%d",&y);t2.kru.addedge(x,y);break;case 'A':a[i]=t1.kru.find(x);break;case 'Z':a[i]=t2.kru.find(x);break;case 'Q':a[i]=x;break;}}t1.get_dfs(),t2.get_dfs();t1.build(1,1,t1.n),t2.build(1,1,t2.n);for(int i=1;i<=m;i++){switch(op[i][0]){case 'Z':t2.change(i);break;case 'Q':q[t2.ask(i)].push_back(i);break;}}for(int i=1;i<=m;i++){switch(op[i][0]){case 'A':t1.change(i);break;case 'Z':for(auto it:q[i])ans[it]-=t1.ask(it);break;case 'Q':ans[i]+=t1.ask(i);break;}}for(int i=1;i<=m;i++)if(op[i][0]=='Q')printf("%lld\n",ans[i]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 571D Campus(数据结构综合)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。