题解 P3273 【[SCOI2011]棘手的操作】
feilongz
2017-09-05 19:01:39
18本
楼上 @远航之曲 的题解非常正确。虽然这道题有更优秀的线段数解法，但是毕竟可以作为可并堆裸题。只是这道题左偏树的复杂度值得商榷。因为左偏树并不能保持平衡，其深度最差可能是O（n），而寻找某个节点的堆顶需要跳到顶，这个操作的效率可能被退化成O（n）。
一些类似的题目往往不需要。
但是根据bzojdiscuss里的说法，貌似数据是特别设计的，左偏树可以跑过，我就不清楚了。
楼上题解左偏树的写法，有一个下传标记操作，在Del操作和Add操作之前都需要下传标记。我这里有一种不同的方法。
对于每个存在的堆，只会维护一个标记，这个标记的数值表示这个堆中的所有元素都加了这个值。
也就是说，堆中某个点的实际值为点值+标记值。
你可以理解为，任何一个节点，如果不是某个堆得根节点，那么它绝对不会有mark（==0）。为了实现这一点，每次Merge的时候，并不是合并某两个具体的点，而只是合并他们的根节点。每次合并，只会在两个根节点上有标记需要考虑（其他点都没有mark啊。）
合并的时候，我们只能保留一个标记，另一个标记就必须暴力下传到每一个点。这里如果随便下传一个堆，保留另一个堆的mark，复杂度就不能保证。可以用一种类似启发式合并的方法，对堆中每个节点维护一个size，合并标记的时候选择小的堆下传，大的堆标记保留。这样总复杂度是可以证明的。
另外，要明白合并之后，两个堆公用一个标记（现在是一个堆了），我们还需要在下传小堆标记的时候减去大堆标记的影响。
例如，小堆的某个点是2，mark为1，那么这个点的实际值为3.但是如果大堆有一个MARK=3，合并之后共用标记，这个点的值就会变成6，显然是不可以的（因为合并前大堆的标记只对大堆有效）。因此下传小堆标记的时候要下传mark-MARK，这样下传之后该点的值为0，统计的时候加上MARK=3，正好等于3.
具体还有细节需要注意。上代码。（理论复杂度并不慢，只是我自带大常数。）
```cpp
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
struct heap
{
struct node
{
int val,dist,size;
int l,r,fa;
}e[301000];
int ROOT;
int mark[301000];
int getroot(int x)
{
while(e[x].fa) x=e[x].fa;
return x;
}
void pushup(int x)
{
if(!x)
return;
e[x].size=1;
if(e[x].l)
e[x].size+=e[e[x].l].size;
if(e[x].r)
e[x].size+=e[e[x].r].size;
}
void pushdown(int root,int val)
{
e[root].val+=val;
if(e[root].l)
pushdown(e[root].l,val);
if(e[root].r)
pushdown(e[root].r,val);
}
void Mergemark(int x,int y)
{
int fx=getroot(x);
int fy=getroot(y);
if(fx==fy)
return;
int Y=fy,X=fx;
if(e[fx].size<e[fy].size)
swap(X,Y);
pushdown(Y,mark[Y]-mark[X]);
if(e[fx].val<e[fy].val)
swap(fx,fy);
mark[fx]=mark[X];
mark[fy]=0;
}
int Merge2(int x,int y)
{
if(!x) return y;
if(!y) return x;
int fx=getroot(x);
if(fx==getroot(y))
return fx;
if(e[x].val<e[y].val)
swap(x,y);
// down(x);
e[x].r=Merge2(e[x].r,y);
e[e[x].r].fa=x;
if(e[e[x].r].dist>e[e[x].l].dist)
swap(e[x].l,e[x].r);
if(!e[x].r)
e[x].dist=0;
else
e[x].dist=e[e[x].r].dist+1;
pushup(x);
return x;
}
int Merge(int x,int y)
{
Mergemark(x,y);
return Merge2(x,y);
}
int Del(int x)
{
if(!x) return 0;
e[e[x].l].fa=0;
e[e[x].r].fa=0;
int q=e[x].fa,p=Merge(e[x].l,e[x].r);
pushup(p);
e[p].fa=q;
if(q&&e[q].l==x)
e[q].l=p;
if(q&&e[q].r==x)
e[q].r=p;
if(!q)
mark[p]=mark[x];
while(q)
{
if (e[e[q].l].dist<e[e[q].r].dist)
swap(e[q].l,e[q].r);
if (e[e[q].r].dist+1==e[q].dist)
return ROOT;
e[q].dist=e[e[q].r].dist+1;
p=q;
q=e[q].fa;
pushup(q);
}
return p;
}
void re(int x,int val)
{
mark[x]=0;
e[x].fa=0;
e[x].size=1;
e[x].val=val;
e[x].dist=0;
e[x].l=e[x].r=0;
}
void Add(int x,int val)
{
re(x,val);
if(!ROOT) ROOT=x;
else ROOT=Merge(ROOT,x);
}
}hp1,hp2;
int n;
void Merge(int x,int y)
{
int fx=hp1.getroot(x);
int fy=hp1.getroot(y);
if(fx==fy)
return;
hp2.ROOT=hp2.Del(fx);
hp2.ROOT=hp2.Del(fy);
int z=hp1.Merge(fx,fy);
hp2.Add(z,hp1.e[z].val+hp1.mark[z]);
}
void Addpoint(int x,int v)
{
int fx=hp1.getroot(x);
hp2.ROOT=hp2.Del(fx);
int val=hp1.e[x].val;
if(fx==x)
if(!hp1.e[x].l&&!hp1.e[x].r)
{
hp1.e[x].val+=v;
hp2.Add(x,hp1.e[x].val+hp1.mark[x]);
return;
}
else
{
if(hp1.e[x].l)
fx=hp1.e[x].l;
if(hp1.e[x].r)
fx=hp1.e[x].r;
}
hp1.Del(x);
int z=hp1.getroot(fx);
hp1.re(x,hp1.e[x].val+v+hp1.mark[z]),z=hp1.Merge(x,z);
hp2.Add(z,hp1.e[z].val+hp1.mark[z]);
}
void Addlink(int x,int v)
{
int fx=hp1.getroot(x);
hp1.mark[fx]+=v;
hp2.ROOT=hp2.Del(fx);
hp2.Add(fx,hp1.e[fx].val+hp1.mark[fx]);
}
int buff=0;
void Addheap(int v)
{
buff+=v;
}
int Getpoint(int x)
{
int addition=hp1.mark[hp1.getroot(x)];
return hp1.e[x].val+addition+buff;
}
int Getlink(int x)
{
int fx=hp1.getroot(x);
return hp1.mark[fx]+hp1.e[fx].val+buff;
}
int Getheap()
{
return hp2.e[hp2.ROOT].val+buff;
}
int a[301000];
queue<int> q;
int main()
{
scanf("%d",&n);
hp2.e[0].dist=-1;
hp1.e[0].dist=-1;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),hp1.re(i,a[i]),hp2.re(i,a[i]),q.push(i);
while(!q.empty())
{
int a1=q.front();
q.pop();
if(q.empty())
break;
int a2=q.front();
q.pop();
hp2.ROOT=hp2.Merge(a1,a2);
q.push(hp2.ROOT);
}
int q;
scanf("%d",&q);
while(q--)
{
char s[3];
int x,y,v;
scanf("%s",&s);
if(s[0]=='U')
{
scanf("%d %d",&x,&y);
Merge(x,y);
}
if(s[0]=='A')
{
if(s[1]=='1'){ scanf("%d %d",&x,&v); Addpoint(x,v); }
if(s[1]=='2'){ scanf("%d %d",&x,&v); Addlink(x,v); }
if(s[1]=='3'){ scanf("%d",&v); Addheap(v); }
}
if(s[0]=='F')
{
int ans=0;
if(s[1]=='1'){ scanf("%d",&x); ans=Getpoint(x);}
if(s[1]=='2'){ scanf("%d",&x); ans=Getlink(x); }
if(s[1]=='3') ans=Getheap();
printf("%d\n",ans);
}
}
return 0;
}
```