自动搬运

查看原文

来自洛谷，原作者为

	ouuan 如果奇迹有颜色的话，那么其中之一必是橙色的吧。

搬运于2025-08-24 21:47:13，当前版本为作者最后更新于2019-04-04 08:26:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题目前题解中所有左偏树做法均可被卡（一条链，不停单点询问链底端）。

其实这题是有左偏树正解的，就是这篇题解的做法，然而他是暴力向上跳找根的，所以还是可以被卡。

首先，找一个节点所在堆的堆顶要用并查集，而不能暴力向上跳。

再考虑单点查询，若用普通的方法打标记，就得查询点到根路径上的标记之和，最坏情况下可以达到 $\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 最大值+全局标记。

参考代码：

#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]);
}