[SCOI2011]棘手的操作(可并堆/并查集/线段树)

我懒死了

过于棘手

但这题真的很水的说

毕竟写啥都能过

常见思路：

①：由于不强制在线，所以重新编号之后线段树维护

②：用各种可以高速合并的数据结构，比如可并堆，可并平衡树啥的

讲一种无脑算法：

对于$F1$，并查集乱搞

对于$F2$，用可并堆维护连通块里的值，并维护对应的时间，如果堆顶访问到旧的值直接抛出

对于$F3$，用全局堆维护每个连通块的最大值的集合并维护对应的时间，如果堆顶访问到旧的值直接抛出

$A1$：单点修改时在所在可并堆里插入一个新的，维护修改时间，同时在全局堆里插入一个新的该可并堆的最大值

$A2$：在堆上打tag，在全局堆中插入新的最大值

$A3$：维护一个全局变量

$U$:略

好气啊将近二百行可并堆写的一点问题没有结果十多行并查集出了三处锅...

  1 #include<cstdio>
  2 #include<queue>
  3 #include<algorithm>
  4 using std::max;
  5 using std::priority_queue;
  6 using std::swap;
  7 const int N=300011;
  8 int n,v[N],del[N],Del;
  9 char op[32];
 10 
 11 int lta[N],ltb[N];
 12 struct shino
 13 {
 14     int id,v,t;
 15     shino(){}
 16     shino(int a,int b,int c){id=a,v=b,t=c;}
 17     bool friend operator < (shino x,shino y){return x.v<y.v;}
 18 }g;
 19 struct merheap
 20 {
 21     int dis[N<<1],tag[N<<1],son[N<<1][2],fa[N<<1],kr,yop[N<<1],rt[N<<1];
 22     shino el[N<<1];
 23     int find(int x)
 24     {
 25         if(fa[x]==x) return x;
 26         else return fa[x]=find(fa[x]);
 27     }
 28     void fuckdown(int x)
 29     {
 30         if(tag[x])
 31         {
 32             int k=son[x][0];
 33             if(k){el[k].v+=tag[x];tag[k]+=tag[x];}
 34             k=son[x][1];
 35             if(k){el[k].v+=tag[x];tag[k]+=tag[x];}
 36             tag[x]=0;
 37         }
 38     }
 39     int makenew(shino sn)
 40     {
 41         kr++;
 42         el[kr]=sn;
 43         fa[kr]=kr;
 44         return kr;
 45     }
 46     int merge(int x,int y)
 47     {
 48         if(!x) return y;
 49         if(!y) return x;
 50         fuckdown(x);
 51         fuckdown(y);
 52         if(el[x]<el[y]) swap(x,y);
 53         son[x][1]=merge(son[x][1],y);
 54         fa[son[x][1]]=x;
 55         if(dis[son[x][0]]<dis[son[x][1]]) swap(son[x][0],son[x][1]);
 56         dis[x]=dis[son[x][1]]+1;
 57         return x;
 58     }
 59     void push(int x,shino ei)
 60     {
 61         int tmp=makenew(ei);
 62         int xx=find(x);
 63         rt[x]=merge(xx,tmp);
 64     }
 65     void pop(int x)
 66     {
 67         int xx=find(x);
 68         fuckdown(xx);
 69         int tmp=merge(son[xx][0],son[xx][1]);
 70         fa[xx]=tmp;
 71         if(son[xx][0]) fa[son[xx][0]]=tmp;
 72         if(son[xx][1]) fa[son[xx][1]]=tmp;
 73         rt[x]=tmp;
 74     }
 75     shino top(int x)
 76     {
 77         x=find(x);
 78         return el[x];
 79     }
 80     void update(int x)
 81     {
 82         int xx=find(x);
 83         while(xx)
 84         {
 85             xx=find(xx);
 86             g=top(xx);
 87             if(g.t!=lta[g.id]) pop(xx);
 88             else break;
 89         }
 90     }
 91     void add(int x,int vi)
 92     {
 93         int xx=find(x);
 94         el[xx].v+=vi;
 95         tag[xx]+=vi;
 96     }
 97     void init()
 98     {
 99         for(int i=1;i<=n;i++)
100         {
101             makenew(shino(i,v[i],0));
102             rt[i]=i;
103         }
104     }
105 }rk;
106 int fa[N];
107 bool isrt[N];
108 void domerge(int x,int y);
109 priority_queue<shino> q;
110 void find(int x)
111 {
112     if(fa[x]!=fa[fa[x]]) find(fa[x]),v[x]+=del[fa[x]];
113     fa[x]=fa[fa[x]];
114 }
115 void merge(int x,int y,int tt)
116 {
117     find(x),find(y);
118     int fx=fa[x],fy=fa[y];
119     if(fx==fy) return;
120     domerge(fx,fy);
121     q.push(shino(fy,rk.top(fy).v,tt));
122     ltb[fy]=tt;
123     fa[fx]=fy;
124     del[fx]-=del[fy];
125     v[fx]+=del[fx];
126     isrt[fx]=0;
127 }
128 void domerge(int x,int y)
129 {
130     int xx=rk.find(x),yy=rk.find(y);
131     int tmp=rk.merge(xx,yy);
132     rk.fa[xx]=rk.fa[yy]=rk.rt[y]=tmp;
133 }
134 void fuckdate()
135 {
136     while(!q.empty())
137     {
138         g=q.top();
139         if(!isrt[g.id]||g.t!=ltb[g.id]) q.pop();
140         else break;
141     }
142 }
143 
144 int main()
145 {
146     scanf("%d",&n);
147     for(int i=1;i<=n;i++) scanf("%d",&v[i]),fa[i]=i,isrt[i]=1;
148     int T;
149     scanf("%d",&T);
150     rk.init();
151     for(int i=1;i<=n;i++) q.push(shino(i,v[i],0));
152     int xin,yin,vin;
153     for(int t=1;t<=T;t++)
154     {
155         scanf("%s",op);
156         if(op[0]=='U')
157         {
158             scanf("%d%d",&xin,&yin);
159             merge(xin,yin,t);
160         }else if(op[0]=='A')
161         {
162             if(op[1]=='1')
163             {
164                 scanf("%d%d",&xin,&vin);
165                 find(xin);
166                 v[xin]+=vin;
167                 rk.push(fa[xin],shino(xin,v[xin]+del[fa[xin]],t));
168                 lta[xin]=t;
169                 rk.update(fa[xin]);
170                 q.push(shino(fa[xin],rk.top(fa[xin]).v,t));
171                 ltb[fa[xin]]=t;
172             }else if(op[1]=='2')
173             {
174                 scanf("%d%d",&xin,&vin);
175                 find(xin);
176                 del[fa[xin]]+=vin;
177                 rk.add(fa[xin],vin);
178                 q.push(shino(fa[xin],rk.top(fa[xin]).v,t));
179                 ltb[fa[xin]]=t;
180             }else
181             {
182                 scanf("%d",&vin);
183                 Del+=vin;
184             }
185         }else if(op[0]=='F')
186         {
187             if(op[1]=='1')
188             {
189                 scanf("%d",&xin);
190                 find(xin);
191                 printf("%d
",v[xin]+del[fa[xin]]+Del);
192             }else if(op[1]=='2')
193             {
194                 scanf("%d",&xin);
195                 find(xin);
196                 rk.update(fa[xin]);
197                 printf("%d
",rk.top(fa[xin]).v+Del);
198             }else
199             {
200                 fuckdate();
201                 g=q.top();
202                 printf("%d
",g.v+Del);
203             }
204         }
205     }
206     return 0;
207 }

巨佬您txdy

题外话：你这题解也太水了吧

rkk：因为确实水死了啊...都快成板子了...