题解 P3273 【[SCOI2011]棘手的操作】
ouuan
2019-04-04 08:26:11
这题目前题解中所有左偏树做法均可被卡（一条链，不停单点询问链底端）。
其实这题是有左偏树正解的，就是[这篇题解](https://www.luogu.org/blog/user17667/solution-p3273)的做法，然而他是暴力向上跳找根的，所以还是可以被卡。
首先，找一个节点所在堆的堆顶要用并查集，而不能暴力向上跳。
再考虑单点查询，若用普通的方法打标记，就得查询点到根路径上的标记之和，最坏情况下可以达到 $\mathcal O(n)$ 的复杂度。如果只有堆顶有标记，就可以 $\mathcal O(\log n)$（只有路径压缩的并查集复杂度）地查询了，但如何做到呢？
可以用类似启发式合并的方式，每次合并的时候把较小的那个堆标记暴力下传到每个节点，然后把较大的堆的标记作为合并后的堆的标记。由于合并后有另一个堆的标记，所以较小的堆下传标记时要下传其标记减去另一个堆的标记。由于每个节点每被合并一次所在堆的大小至少乘二，所以每个节点最多被下放 $\mathcal O(\log n)$ 次标记，暴力下放标记的总复杂度就是 $\mathcal O(n\log n)$。
再考虑单点加，先删除，再更新，最后插入即可。
然后是全局最大值，可以用一个平衡树/左偏树/multiset 来维护每个堆的堆顶。
所以，每个操作分别如下：
1. 暴力下传点数较小的堆的标记，合并两个堆，更新 size、tag，在 multiset 中删去合并后不在堆顶的那个原堆顶。
2. 删除节点，更新值，插入回来，更新 multiset。需要分删除节点是否为根来讨论一下。
3. 堆顶打标记，更新 multiset。
4. 打全局标记。
5. 查询值+堆顶标记+全局标记。
6. 查询根的值+堆顶标记+全局标记。
7. 查询 multiset 最大值+全局标记。
参考代码：
```cpp
#include <iostream>
#include <cstdio>
#include <set>
#include <cctype>
#include <algorithm>
using namespace std;
int read()
{
int out=0,f=1;
char c;
for (c=getchar();!isdigit(c)&&c!='-';c=getchar());
if (c=='-') { f=-1; c=getchar(); }
for (;isdigit(c);c=getchar()) out=out*10+c-'0';
return out*f;
}
const int N=300010;
struct Node
{
int val,ch[2],d,fa;
} t[N];
int& rs(int x);
int merge(int x,int y);
void pushup(int x);
void pushdown(int x,int y);
int find(int x);
int n,m,f[N],tag[N],siz[N],delta;
char op[10];
multiset<int> s;
int main()
{
int i,x,y;
n=read();
for (i=1;i<=n;++i)
{
t[i].val=read();
f[i]=i;
siz[i]=1;
s.insert(t[i].val);
}
m=read();
while (m--)
{
scanf("%s",op);
if (op[0]=='U')
{
x=find(read());
y=find(read());
if (x!=y)
{
if (siz[x]>siz[y]) swap(x,y);
pushdown(x,tag[x]-tag[y]);
f[x]=f[y]=merge(x,y);
if (f[x]==x)
{
s.erase(s.find(t[y].val+tag[y]));
tag[x]=tag[y];
siz[x]+=siz[y];
tag[y]=siz[y]=0;
}
else
{
s.erase(s.find(t[x].val+tag[y]));
siz[y]+=siz[x];
tag[x]=siz[x]=0;
}
}
}
else if (op[0]=='A')
{
if (op[1]=='1')
{
x=read();
if (x==find(x))
{
t[t[x].ch[0]].fa=t[t[x].ch[1]].fa=0;
y=merge(t[x].ch[0],t[x].ch[1]);
s.erase(s.find(t[x].val+tag[x]));
t[x].val+=read();
t[x].fa=t[x].ch[0]=t[x].ch[1]=0;
t[x].d=1;
f[x]=f[y]=merge(x,y);
s.insert(t[f[x]].val+tag[x]);
if (f[x]==y)
{
tag[y]=tag[x];
siz[y]=siz[x];
tag[x]=siz[x]=0;
}
}
else
{
t[t[x].ch[0]].fa=t[t[x].ch[1]].fa=t[x].fa;
t[t[x].fa].ch[x==t[t[x].fa].ch[1]]=merge(t[x].ch[0],t[x].ch[1]);
t[x].val+=read();
t[x].fa=t[x].ch[0]=t[x].ch[1]=0;
t[x].d=1;
y=find(x);
f[x]=f[y]=merge(x,y);
if (f[x]==x)
{
s.erase(s.find(t[y].val+tag[y]));
s.insert(t[x].val+tag[y]);
tag[x]=tag[y];
siz[x]=siz[y];
tag[y]=siz[y]=0;
}
}
}
else if (op[1]=='2')
{
x=find(read());
s.erase(s.find(t[x].val+tag[x]));
tag[x]+=read();
s.insert(t[x].val+tag[x]);
}
else delta+=read();
}
else
{
if (op[1]=='1')
{
x=read();
printf("%d\n",t[x].val+tag[find(x)]+delta);
}
else if (op[1]=='2')
{
x=find(read());
printf("%d\n",t[x].val+tag[x]+delta);
}
else printf("%d\n",*s.rbegin()+delta);
}
}
return 0;
}
int& rs(int x) //一种比较清奇的左偏树写法，无需交换左右儿子，把dist较小的视作右儿子即可
{
return t[x].ch[t[t[x].ch[1]].d<t[t[x].ch[0]].d];
}
int merge(int x,int y)
{
if (!x||!y) return x|y;
if (t[x].val<t[y].val) swap(x,y);
t[rs(x)=merge(rs(x),y)].fa=x;
pushup(x);
return x;
}
void pushup(int x) //一种比较清奇的删节点写法，merge之后递归地pushup即可
{
if (!x) return;
if (t[x].d!=t[rs(x)].d+1)
{
t[x].d=t[rs(x)].d+1;
pushup(t[x].fa);
}
}
void pushdown(int x,int y)
{
if (!x) return;
t[x].val+=y;
pushdown(t[x].ch[0],y);
pushdown(t[x].ch[1],y);
}
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
```