這里放傳送門
這道題有兩種做法：可并堆和線段樹。相比于可并堆的寫法來說線段樹的寫法非常簡單并且好懂。。。然而這道題作為可并堆的練習(xí)也確實(shí)很有價(jià)值。。
首先提一句線段樹的解法。可以發(fā)現(xiàn)它只要并到一起去的聯(lián)通塊是不會再拆開的，所以我們能夠把每個時(shí)刻出現(xiàn)的連通塊都標(biāo)號為一個連續(xù)的區(qū)間，那么就可以用線段樹進(jìn)行區(qū)間修改區(qū)間查詢。
操作方法是先把操作離線，然后對于每個合并操作用并查集來維護(hù)，為每個集合維護(hù)一個ed數(shù)組表示這一塊的最后一個點(diǎn)的編號，再為每個點(diǎn)維護(hù)一個nxt值表示它的下一個節(jié)點(diǎn)編號。也就是說用并查集的father數(shù)組可以找到這個連通塊的第一個節(jié)點(diǎn)，而ed數(shù)組可以找到最后一個，這就保證了節(jié)點(diǎn)的順序。
在合并兩個集合的時(shí)候按照順序把一段節(jié)點(diǎn)接到另一段節(jié)點(diǎn)后面，這就要求在修改的時(shí)候一定要按順序進(jìn)行。并且這種操作方式?jīng)Q定了只有代表元素的ed值是正確的，因?yàn)槊看涡薷牡臅r(shí)候不能順著并查集全改一遍不然肯定T死。
遍歷所有點(diǎn)的時(shí)候每次遇到一個代表元素就用nxt數(shù)組遍歷所有連通塊然后依次標(biāo)號就可以了。然后把father和ed數(shù)組初始化，重新做一邊操作來處理詢問就可以了。
對于可并堆來說的話就不需要離線直接在線處理就可以了。對于第一個操作就是直接合并兩個堆，對于第二個操作它需要修改單個元素的值，那么這個可并堆必須支持找到某個元素的位置并且修改它，那么向上調(diào)整和向下調(diào)整兩個操作都要搞出來；然后因?yàn)榭刹⒍延弥羔樣涗浟俗笥覂鹤雍透赣H的位置，相當(dāng)于是搞了一個雙向指針的東西，動了一個地方其它都跟著亂動就特?zé)┤恕！?/p>
因?yàn)榈谌齻€操作要修改整個連通塊，所以要在可并堆里面維護(hù)lazy標(biāo)記，每次merge操作的時(shí)候得先push一下把標(biāo)記傳下去。并且向上調(diào)整之前還要先把它祖先的標(biāo)記都放下來。
最麻煩的操作就是整體最大值的維護(hù)。。因?yàn)榫幪柺巧y的所以沒法直接用線段樹之類的東西來搞，所以就搞了個堆套堆。。似乎用STL也可以？這題ATP在WC的時(shí)候調(diào)了三天因?yàn)楦愕脭鄶嗬m(xù)續(xù)所以也寫得奇丑無比。。目測根本沒法看qwq
簡潔明了的線段樹版本
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m,a[300010],father[300010],ed[300010],w[300010],num[300010],next[300010],cnt;int Max[1500000],dlt[1500000];struct question{ int k,x,y;}q[300010];char get(){ int c=getchar(); while (c>'Z'||c<'A') c=getchar(); return c;}int find(int x){ if (father[x]!=x) father[x]=find(father[x]); return father[x];}void update(int i){ Max[i]=max(Max[i<<1],Max[(i<<1)+1]);}void pushdown(int i){ if (dlt[i]!=0){ Max[i<<1]+=dlt[i];Max[(i<<1)+1]+=dlt[i]; dlt[i<<1]+=dlt[i];dlt[(i<<1)+1]+=dlt[i]; dlt[i]=0; }}void build(int i,int l,int r){ if (l==r){ Max[i]=num[l];return; } int mid=(l+r)>>1; build(i<<1,l,mid); build((i<<1)+1,mid+1,r); update(i);}void change(int i,int l,int r,int left,int right,int v){ if (left<=l&&right>=r){ Max[i]+=v;dlt[i]+=v;return; } int mid=(l+r)>>1; pushdown(i); if (left<=mid) change(i<<1,l,mid,left,right,v); if (right>mid) change((i<<1)+1,mid+1,r,left,right,v); update(i);}int ask(int i,int l,int r,int left,int right){ if (left<=l&&right>=r) return Max[i]; int mid=(l+r)>>1,ans=-0x7fffffff; pushdown(i); if (left<=mid) ans=max(ans,ask(i<<1,l,mid,left,right)); if (right>mid) ans=max(ans,ask((i<<1)+1,mid+1,r,left,right)); return ans;}int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); father[i]=ed[i]=i; } scanf("%d",&m); for (int i=1;i<=m;i++){ char c=get(); if (c=='U'){ int r1,r2; q[i].k=1;scanf("%d%d",&q[i].x,&q[i].y); r1=find(q[i].x);r2=find(q[i].y); if (r1!=r2){//注意合并操作的順序要求 father[r2]=r1;next[ed[r1]]=r2;ed[r1]=ed[r2]; } } if (c=='A'){ char z=getchar(); if (z=='3'){ q[i].k=4;scanf("%d",&q[i].x); }else{ q[i].k=z-'0'+1;scanf("%d%d",&q[i].x,&q[i].y); } } if (c=='F'){ char z=getchar(); if (z=='3') q[i].k=7; else {q[i].k=z-'0'+4;scanf("%d",&q[i].x);} } } for (int i=1;i<=n;i++) if (find(i)==i){ for (int j=i;j!=0;j=next[j]){ w[j]=++cnt;num[cnt]=a[j]; } } for (int i=1;i<=n;i++) father[i]=ed[i]=i; build(1,1,n); for (int i=1;i<=m;i++) switch (q[i].k){ case 1:{ int r1,r2; r1=find(q[i].x);r2=find(q[i].y); if (r1!=r2){ father[r2]=r1;next[ed[r1]]=r2;ed[r1]=ed[r2]; }//重新進(jìn)行一遍操作 break; } case 2:{ change(1,1,n,w[q[i].x],w[q[i].x],q[i].y); break; } case 3:{ int r=find(q[i].x); change(1,1,n,w[r],w[ed[r]],q[i].y); break; } case 4:{ change(1,1,n,1,n,q[i].x); break; } case 5:{ 丑陋至極的可并堆版本#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,q,a[300010],delta,father[300010],ptr[300010];struct Node{ Node *l,*r,*fa; int val,NPL,dlt; Node(); Node(int x); void count(){NPL=r->NPL+1;} void push(); void Add(int v); void pushdlt(); void faswap(); void pushup(int rt); void pushdown(int rt);}*null,H[300010],*h[300010],*st[300010];struct Temp{ Node* *p; int id;}tmp[300010];Node::Node(){l=r=fa=null;val=NPL=dlt=0;}Node::Node(int x){l=r=fa=null;val=x;NPL=1;dlt=0;}void Node::Add(int v){val+=v;dlt+=v;}void Node::push(){ if (dlt!=0){ if (l!=null) l->Add(dlt); if (r!=null) r->Add(dlt); dlt=0; }}void Node::pushdlt(){ Node *ptr=this; int top=0; while (ptr!=null){ st[++top]=ptr; ptr=ptr->fa; } for (int i=top;i>=1;i--) st[i]->push();}void Node::faswap(){ Node *k=fa; if (this==k->l){ swap(r,k->r);k->l=l;l=k; }else{swap(l,k->l);k->r=r;r=k;} fa=k->fa; if (k==k->fa->l) k->fa->l=this; else k->fa->r=this; if (k->r!=null) k->r->fa=k; if (k->l!=null) k->l->fa=k; if (l!=null) l->fa=this; if (r!=null) r->fa=this; count();k->count();}void Node::pushup(int rt){ Node *k=fa; if (k==null){h[rt]=this;return;} if (val<=k->val) return; faswap();pushup(rt);}void Node::pushdown(int rt){ int Maxs=-1; Node *tmp; if (this==null||(l==null&&r==null)) return; Maxs=max(l->val,r->val); l->push();r->push(); if (Maxs<=val) return; if (Maxs==l->val) l->faswap(); else r->faswap(); if (fa->fa==null) h[rt]=fa; pushdown(rt);}Node* merge(Node *x,Node *y){ if (x==null) return y; if (y==null) return x; if (x->val<y->val) swap(x,y); x->push(); x->r=merge(x->r,y); x->r->fa=x; if (x->l->NPL<x->r->NPL) swap(x->l,x->r); x->count();return x;}int comp(Temp x,Temp y){return (*(x.p))->val>(*(y.p))->val;}int find(int x){ if (father[x]==x) return father[x]; father[x]=find(father[x]); return father[x];}int getnum(char x,char y){ int c; if (x=='U') return 1; if (x=='A') c=1; else c=4; return c+y-'0';}void pushup(int now){ int fa=now>>1; if (fa==0||(*tmp[now].p)->val<=(*tmp[fa].p)->val) return; tmp[now].id=find(tmp[now].id); tmp[fa].id=find(tmp[fa].id); if (tmp[now].id!=0&&tmp[fa].id!=0) swap(ptr[tmp[now].id],ptr[tmp[fa].id]); swap(tmp[now],tmp[fa]); pushup(fa);}void pushdown(int now){ int Maxs=-0x7fffffff,l=now<<1,r=l+1,r1,r2,r3; if (l>n&&r>n) return; if (l<=n) Maxs=max(Maxs,(*tmp[l].p)->val); if (r<=n) Maxs=max(Maxs,(*tmp[r].p)->val); tmp[now].id=r1=find(tmp[now].id); tmp[l].id=r2=find(tmp[l].id); tmp[r].id=r3=find(tmp[r].id); if (r2==0&&r3==0) return; if (Maxs<=(*tmp[now].p)->val||r1==0) return; if (r2!=0&&Maxs==(*tmp[l].p)->val){ swap(ptr[r2],ptr[r1]); swap(tmp[l],tmp[now]); pushdown(l); }else if (r3!=0){ swap(ptr[tmp[r].id],ptr[tmp[now].id]); swap(tmp[r],tmp[now]); pushdown(r); }}void Union(int x,int y){ int r1=find(x),r2=find(y); if (r1==r2) return; tmp[ptr[r2]].p=&null; pushdown(ptr[r2]); tmp[ptr[r2]].id=ptr[r2]=0; father[r2]=r1; h[r1]=merge(h[r1],h[r2]); pushup(ptr[r1]);}void Addpoint(int x,int v){ int rt=find(x); H[x].pushdlt();//下放當(dāng)前節(jié)點(diǎn)的標(biāo)記 H[x].val+=v; if (v>0) H[x].pushup(rt); else H[x].pushdown(rt);//調(diào)整節(jié)點(diǎn)在當(dāng)前堆里的位置 if (v<0) pushdown(ptr[rt]);//調(diào)整當(dāng)前堆頂?shù)奈恢? else pushup(ptr[rt]);}void Addblock(int x,int v){ int rt=find(x); h[rt]->Add(v); if (v<0) pushdown(ptr[rt]); else pushup(ptr[rt]);}int main(){ null=new Node;*null=Node(); null->val=-0x7fffffff; scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); father[i]=i;H[i]=Node(a[i]); h[i]=H+i;tmp[i].p=h+i; tmp[i].id=i; } sort(tmp+1,tmp+n+1,comp); for (int i=1;i<=n;i++) ptr[tmp[i].id]=i; scanf("%d",&q); for (int i=1;i<=q;i++){ char s[5];scanf("%s",s); int opt,x,y,v,rt; opt=getnum(s[0],s[1]); switch (opt){ case 1:{ scanf("%d%d",&x,&y); Union(x,y);break; } case 2:{ scanf("%d%d",&x,&v); Addpoint(x,v);break; } case 3:{ scanf("%d%d",&x,&v); Addblock(x,v);break; } case 4:{ scanf("%d",&v); delta+=v;break; } case 5:{ scanf("%d",&x);H[x].pushdlt(); printf("%d/n",H[x].val+delta);break; } case 6:{ scanf("%d",&x);rt=find(x); printf("%d/n",h[rt]->val+delta);break; } case 7:{printf("%d/n",(*tmp[1].p)->val+delta);break;} } } return 0;}這題的線段樹做法是很經(jīng)典的思路啊 可并堆的做法就適合閑著沒事的時(shí)候花上一天磨磨蹭蹭寫著玩啊
新聞熱點(diǎn)
疑難解答
