[SCOI2011]棘手的操作

前言

  • 不得不说，这题得劲。因为这几天复习数据结构都疯了QwQ，一来就想码并查集+线段树，但是想了一想(wtcl)，似乎不太容易维护每个块。emmm，然后去网上看看题解，发现竟然可以用堆合并与删除解决，以简单方法吊打难题
    图片说明

分析

  • 纵观全局，可以先确定能用并查集。每一个都需要维护。而需要维护的则是每一个块的最大值，每一个块有哪些节点
  • 维护方法：因为既要求所有节点中的最大值，也要求各个块中的，那就对全局以及每一个块都建立一个堆，同时维护一个容器 c [ i ] 表示在块 i 中的有哪些节点。因为每次对一个点进行修改时，不能直接提出来进行修改(即先进行pop找到节点，修改完后在push回去)，那么换种方式，对每一个块再建立一个队列del存下本应该删去的值，每一次取出块中的最大值的时候，先与队列del中的数进行比较
  • 详细过程：
    U x v：合并x，v所在的两个堆。为了减少时间复杂度，选择把块中节点较少的合并到块中节点较多的。不断取出其中一个堆中的元素，加入到另一个中去
    A1 x v：先把它push进入堆del中，修改完再入队
    A2 x v：只需要对每一个联通块维护一个变量 jub [ i ] ，与线段树中的懒标记类似
    A3 x v：同上，只需要用一个全局变量记录一下
    F1 x：输出 a [ i ] + jub [ i对应块的编号 ]，就像一个下传操作
    F2 x：每一个连通块都建立了一个堆，输出堆顶
    F3 x：在全局也建立了一个堆，输出堆顶

代码

/*
U  x y:合并他们的两个堆

A1 x v:先pop到del,再push回val

A2 x v:连通块的变量处理

A3 x v:全局变量处理

F1 x:找到所属连通块,加上局部和全局变量

F2 x:直接pop

F3 x:整体的pop
*/
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=3e5+10;

int n,zt,m;
ll a[N],jub[N];int f[N];

vector<int>num[N];
//连通块里的点
struct nkl
{
    priority_queue<ll>q,del;

    void push(ll x){q.push(x);}
    void pop(ll x){del.push(x);}
    int top()
    {
        while(del.size()&&del.top()==q.top())
            del.pop(),q.pop();
        return q.top();
    }
}wl,bl[N];

inline int find(int x)
{
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        f[i]=i;//并查集初始化
        num[i].push_back(i);//连通块的点
        wl.push(a[i]);
        bl[i].push(a[i]);
        //全局与局部的点 
    }

    scanf("%d",&m);char ins[5];int x,v;
    while(m--)
    {
        scanf("%s",ins);
        if(ins[0]=='U')
        {
            scanf("%d%d",&x,&v);
            x=find(x),v=find(v);
            if(x==v) continue;

            if(num[x].size()<num[v].size()) swap(x,v);
            wl.pop(bl[v].top()+jub[v]);
            wl.pop(bl[x].top()+jub[x]);
            int len=num[v].size();
            for (int i=0;i<len;i++)
            {
                int j=num[v][i];
                f[j]=x;
                a[j]=a[j]+jub[v]-jub[x];
                bl[x].push(a[j]);
                num[x].push_back(j);
            }//开始合并
            num[v].clear();
            wl.push(bl[x].top()+jub[x]);
            //重回最大值
        }
        else if(ins[0]=='A')
        {
            if(ins[1]=='1')
            {
                scanf("%d%d",&x,&v);
                int u=find(x);
                wl.pop(bl[u].top()+jub[u]);
                bl[u].pop(a[x]);
                a[x]+=v;
                bl[u].push(a[x]);
                wl.push(bl[u].top()+jub[u]);
            }
            else if(ins[1]=='2')
            {
                scanf("%d%d",&x,&v);int u=find(x);
                wl.pop(bl[u].top()+jub[u]);
                jub[u]+=v;
                wl.push(bl[u].top()+jub[u]);
            }
            else scanf("%d",&v),zt+=v;
        }
        else
        {
            if(ins[1]=='3')
                printf("%lld\n",wl.top()+(ll)zt);
            else
            {
                scanf("%d",&x);
                int u=find(x);
                if(ins[1]=='1')
                    printf("%lld\n",(ll)a[x]+zt+jub[u]);
                else
                    printf("%lld\n",(ll)bl[u].top()+zt+jub[u]);
            }
        }
    }

    return 0;
}