題目鏈接：棘手的操作

　　網上的題解大部分都是在線用可并堆艸……但是樹高嚴格\(\log\)的可并堆我不會啊……還是離線大法好……

　　我們可以先把所有的合并操作用并查集給處理好，把得到的森林記錄下來。然后，我們對這個森林進行\(dfs\)，就可以得到一個\(dfs\)序，那么我們把所有點按照\(dfs\)序重標號，每個聯通塊就成為了一段區間了。然后就可以直接用線段樹維護了。

　　注意一個細節：在\(dfs\)的時候對于一個點連出去的所有邊，要優先走先連的邊，這樣才能保證聯通塊始終是一段區間。

　　下面貼代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 300010 #define INF 2147483647using namespace std; typedef long long llg;struct data{int op,x,y; }s[maxn]; int head[maxn],next[maxn],to[maxn],tt,du[maxn]; int fa[maxn],n,m,a[maxn],le[maxn],ri[maxn],b[maxn]; int maxv[maxn<<2],addv[maxn<<2],L,R,z,_max,_add; char ss[20];int getint(){int w=0;bool q=0;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') c=getchar(),q=1;while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();return q?-w:w; }int find(int x){return fa[fa[x]]==fa[x]?fa[x]:fa[x]=find(fa[x]);} void link(int x,int y){du[x]++;to[++tt]=y;next[tt]=head[x];head[x]=tt;} void dfs(int u){le[u]=++tt;int *d=new int[du[u]];for(int i=head[u],j=0;i;i=next[i]) d[j++]=to[i];for(int i=du[u];i;i--) dfs(d[i-1]); }void build(int u,int l,int r){int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1;if(l==r){maxv[u]=b[l];return;}build(lc,l,mid); build(lv,mid+1,r);maxv[u]=max(maxv[lc],maxv[lv]); }void add(int u,int l,int r){int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1;if(l>=L && r<=R){maxv[u]+=z,addv[u]+=z;return;}if(L<=mid) add(lc,l,mid);if(R>mid) add(lv,mid+1,r);maxv[u]=max(maxv[lc],maxv[lv])+addv[u]; }void query(int u,int l,int r){int lc=u<<1,lv=u<<1|1,mid=(l+r)>>1;if(l>=L && r<=R){_max=max(_max,maxv[u]+_add);return;}_add+=addv[u];if(L<=mid) query(lc,l,mid);if(R>mid) query(lv,mid+1,r);_add-=addv[u]; }void work(){_max=-INF; query(1,1,n);printf("%d\n",_max); }int main(){File("a");n=getint();for(int i=1;i<=n;i++) a[i]=getint(),fa[i]=i;m=getint();for(int i=1,u,v;i<=m;i++){scanf("%s",ss); if(!ss[1]) ss[1]='1';s[i].op=(ss[0]=='A')+(ss[0]=='F')*4+ss[1]-'0';if(s[i].op<7) s[i].x=getint();if(s[i].op<4) s[i].y=getint();if(s[i].op==1){u=find(s[i].x),v=find(s[i].y);if(u!=v) fa[u]=v,link(v,u);}}tt=0;for(int i=1;i<=n;i++) if(find(i)==i) dfs(i);for(int i=1;i<=n;i++) b[le[i]]=a[i],ri[i]=le[i];for(int i=1;i<=n;i++) fa[i]=i; build(1,1,n);for(int i=1,u,v;i<=m;i++){u=s[i].x; z=v=s[i].y;if(s[i].op==1){u=find(u),v=find(v);if(u!=v) fa[u]=v,ri[v]=ri[u];}else if(s[i].op==2) L=R=le[u],add(1,1,n);else if(s[i].op==3) u=find(u),L=le[u],R=ri[u],add(1,1,n);else if(s[i].op==4) z=u,L=1,R=n,add(1,1,n);else if(s[i].op==5) L=R=le[u],work();else if(s[i].op==6) u=find(u),L=le[u],R=ri[u],work();else printf("%d\n",maxv[1]);}return 0; }

?　　UPD 3.2：左偏樹做法

　　其實無須樹高嚴格\(\log\)，左偏樹就夠了

　　網上有的題解是每次用\(O(樹高)\)的時間統計影響這個點的所有標記，可并堆用的是左偏樹= =

　　但是這樣復雜度是不對的，因為左偏樹的樹高可以達到\(O(n)\)級別

　　然后就需要考慮一種別的解法

　　既然不能每次暴力統計到根的所有標記，我們可以考慮把標記永久化了，固定在根節點，這樣每次就只需要查詢根節點的標記就可以了。但是這樣的話合并的時候會出問題，兩個堆無法直接合并。不要慌，我們只需要把\(size\)較小的那個堆里面所有的元素暴力修改掉就可以直接合并了。再用個全局的堆維護一下全局最大值。總復雜度\(O(n\log n)\)。

　　順便Orz告訴我此解法的xlightgod大爺Orz

　　PS：我寫的是斜堆，不是左偏樹

　　下面貼代碼：

#include<bits/stdc++.h> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 300010using namespace std; typedef long long llg;struct Queue{priority_queue<int> q1,q2;void insert(int x){q1.push(x);}void erase(int x){q2.push(x);}int top(){while(!q2.empty() && q1.top()==q2.top()) q1.pop(),q2.pop();return q1.top();} }q; int n,rt[maxn],siz[maxn],fa[maxn],addv[maxn]; int ff[maxn],s[maxn][2],val[maxn],m,z,_add; char ss[20];int getint(){int w=0;bool q=0;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') c=getchar(),q=1;while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();return q?-w:w; }int find(int x){return ff[ff[x]]==ff[x]?ff[x]:ff[x]=find(ff[x]);} int merge(int u,int v){if(!u || !v) return u+v;if(val[u]<val[v]) swap(u,v);fa[s[u][1]=merge(s[u][1],v)]=u;swap(s[u][0],s[u][1]); return u; }void del(int u){int x=find(u),y=fa[u];if(rt[x]==u) fa[rt[x]=merge(s[u][0],s[u][1])]=0;else fa[s[y][u==s[y][1]]=merge(s[u][0],s[u][1])]=y; }void dfs(int u){val[u]+=z;if(s[u][0]) dfs(s[u][0]);if(s[u][1]) dfs(s[u][1]); }int main(){File("a");n=getint();for(int i=1;i<=n;i++){ff[i]=rt[i]=i,siz[i]=1;q.insert(val[i]=getint());}m=getint();while(m--){int x,y,u;scanf("%s",ss+1);if(ss[1]=='U'){x=find(getint()),y=find(getint());if(siz[x]>siz[y]) swap(x,y);if(x!=y){q.erase(min(val[rt[x]]+addv[x],val[rt[y]]+addv[y]));z=addv[x]-addv[y],dfs(rt[x]); siz[y]+=siz[x];ff[x]=y; rt[y]=merge(rt[x],rt[y]);}}else if(ss[1]=='A'){x=getint();if(ss[2]=='1' || ss[2]=='2'){u=find(x); y=getint();q.erase(val[rt[u]]+addv[u]);if(ss[2]=='1'){del(x); val[x]+=y;s[x][0]=s[x][1]=fa[x]=0;rt[u]=merge(rt[u],x);}else addv[u]+=y;q.insert(val[rt[u]]+addv[u]);}else if(ss[2]=='3') _add+=x;}else{if(ss[2]=='3') printf("%d\n",q.top()+_add);else{x=getint(); u=find(x);if(ss[2]=='1') printf("%d\n",val[x]+addv[u]+_add);else if(ss[2]=='2') printf("%d\n",val[rt[u]]+addv[u]+_add);}}}return 0; }

轉載于:https://www.cnblogs.com/lcf-2000/p/6484275.html

總結

以上是生活随笔為你收集整理的BZOJ 2333 【SCOI2011】 棘手的操作的全部內容，希望文章能夠幫你解決所遇到的問題。

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