[BZOJ2333/Luogu3273][SCOI2011]棘手的操作(可并堆,左偏树)

发布于 2018-02-23  106 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2333/Luogu3273][SCOI2011]棘手的操作(可并堆,左偏树)

Description

有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:
U x y: 加一条边,连接第x个节点和第y个节点
A1 x v: 将第x个节点的权值增加v
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
A3 v: 将所有节点的权值都增加v
F1 x: 输出第x个节点当前的权值
F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值
F3: 输出所有节点中,权值最大的节点的权值

Http

BZOJ
Luogu

Tag

可并堆,左偏树

解决思路

考虑到题目中所有的询问操作都是求最大值,再看到第一种操作只有合并没有分离,那么可以想到用可并堆来维护每一个联通块,至于整个连通块的修改可以用\(lazy\)标记来维护。下面依次具体来看每一个操作。
U x y: 加一条边,连接第x个节点和第y个节点,这个直接分别找到\(x\)和\(y\)所在的可并堆的根,若不在同一个可并堆则合并两个可并堆。注意,这里跳祖先不能用并查集,具体原因下面会说。时间复杂度\(O(logn)\)
A1 x v: 将第x个节点的权值增加v,在可并堆中分离出节点\(x\),然后把\(x\)的权值修改了后再与\(x\)原来所在的可并堆合并。注意,由于有\(lazy\)标记,在分离之前要把从根到\(x\)路径上的所有\(lazy\)都下放。具体分离的步骤是先把\(x\)的两个儿子合并,然后把儿子合并后的新根连上原来\(x\)的父亲,同时修改父亲对应的儿子指针。时间复杂度\(O(logn)\)
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v,跳到\(x\)所在可并堆的根,对根打上\(lazy\)标记。时间复杂度\(O(logn)\)
A3 v: 将所有节点的权值都增加v,在全局维护一个\(allsum\)表示所有\(A3\)操作之和,每一次要输出的时候再加上即可。时间复杂度\(O(1)\)
F1 x: 输出第x个节点当前的权值,类似的,要先从根向下下放所有的\(lazy\)标记再得到值。时间复杂度\(O(logn)\)
F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值,跳到根后输出根的值。时间复杂度\(O(logn)\)
F3: 输出所有节点中,权值最大的节点的权值,由于权值最大的值一定是可并堆的根,所以可以在全局再维护一个代删除的堆,每一次有对可并堆的堆顶的修改时就在这个全局的堆中进行修改,那么\(F3\)操作就直接输出这个堆顶即可。为了方便,可以用两个系统堆来实现带删除的堆的操作,具体来说,用一个堆表示实际的堆,另一个标记垃圾堆,每一次要删除实际堆中的元素时,把这个元素丢入垃圾堆中,当实际堆与垃圾堆的堆顶相同时,同时弹出两个堆的堆顶。时间复杂度\(O(logn)\)
至于为什么不能用路径压缩并查集来维护堆顶。由于这里再可并堆上有\(lazy\)标记用来下放,那么至少需要带权并查集来维护,又因为\(lazy\)是在不断下放的,那么可能并查集还没有更新到,\(lazy\)就已经下放了。再加上有分离出某一个点修改再丢回去的操作,这时候带权并查集的权就会更加混乱。所以不能路径压缩。
这里用左偏树实现可并堆。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=300100;
const int inf=2147483647;

class Heap
{
public:
    int key;
    int ls,rs,dis,fa,lazy;
};

int n;
Heap H[maxN];
priority_queue<int> Q1,Q2;//Q1,Q2分别是全局的实际堆和垃圾堆

int Merge(int r1,int r2);
void PushDown(int r);
void Mark(int r,int lazy);
int GetRt(int x);//得到堆顶
void PushLazy(int x);//从堆顶下放所有lazy标记
void QPush(int x);//这三个操作是维护全局的堆顶的值的
void QDel(int x);
int QTop();

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>H[i].key;QPush(H[i].key);
    }
    int Q;cin>>Q;
    char opt[5];
    int allsum=0;
    while (Q--)
    {
        cin>>opt;
        if (opt[0]=='U')
        {
            int x,y;cin>>x>>y;
            x=GetRt(x);y=GetRt(y);//走到堆顶
            if (x!=y){//若不在同一可并堆,则合并,同时注意要修改全局堆
                int t=Merge(x,y);
                if (t==x) QDel(H[y].key);
                else QDel(H[x].key);
            }
        }
        if (opt[0]=='A')
        {
            if (opt[1]=='1')//单点修改
            {
                int x,v;cin>>x>>v;
                PushLazy(x);QDel(H[GetRt(x)].key);//先把堆顶删除

                int nrt=Merge(H[x].ls,H[x].rs),fa=H[x].fa;//合并左右儿子

                if (H[fa].ls==x) H[fa].ls=nrt;//将父亲原来的儿子指针指向新的儿子
                else if (H[fa].rs==x) H[fa].rs=nrt;
                H[x].fa=H[x].ls=H[x].rs=0;H[x].key+=v;//更新该点权值
                H[nrt].fa=fa;//将新儿子指向父亲

                nrt=GetRt(nrt);//得到堆顶
                nrt=Merge(x,nrt);//把修改后的点放回去
                QPush(H[nrt].key);//把新的堆顶放入全局堆
            }
            if (opt[1]=='2')//整块修改
            {
                int x,v;cin>>x>>v;
                x=GetRt(x);QDel(H[x].key);//得到根,并在全局堆中删除
                Mark(x,v);QPush(H[x].key);//修改,并加入全局堆
            }
            if (opt[1]=='3')//全局修改
            {
                int v;cin>>v;allsum+=v;
            }
        }
        if (opt[0]=='F')
        {
            if (opt[1]=='1')//单点询问
            {
                int x;cin>>x;
                PushLazy(x);//下放lazy标记
                printf("%d\n",H[x].key+allsum);
            }
            if (opt[1]=='2')//连通块最值查询
            {
                int x;cin>>x;
                x=GetRt(x);
                printf("%d\n",H[x].key+allsum);
            }
            if (opt[1]=='3')//全局最值查询
            {
                printf("%d\n",QTop()+allsum);
            }
        }
    }
    return 0;
}

int Merge(int r1,int r2)//左偏树合并
{
    if (r1==0) return r2;
    if (r2==0) return r1;
    PushDown(r1);PushDown(r2);
    if (H[r1].key<H[r2].key) swap(r1,r2);
    H[r1].rs=Merge(H[r1].rs,r2);
    H[H[r1].rs].fa=r1;
    if (H[H[r1].ls].dis<H[H[r1].rs].dis) swap(H[r1].ls,H[r1].rs);
    if (H[r1].rs) H[r1].dis=H[H[r1].rs].dis+1;
    else H[r1].dis=0;
    return r1;
}

void PushDown(int r)//标记下放
{
    if (H[r].lazy==0) return;
    if (H[r].ls) Mark(H[r].ls,H[r].lazy);
    if (H[r].rs) Mark(H[r].rs,H[r].lazy);
    H[r].lazy=0;return;
}

void Mark(int r,int lazy)
{
    H[r].key+=lazy;H[r].lazy+=lazy;
    return;
}

int GetRt(int x)
{
    while (H[x].fa) x=H[x].fa;
    return x;
}

int Stack[maxN];

void PushLazy(int x)
{
    int stacktop=0;
    while (x){
        Stack[++stacktop]=x;x=H[x].fa;
    }
    while (stacktop) PushDown(Stack[stacktop--]);
    return;
}

void QPush(int x)
{
    Q1.push(x);return;
}

void QDel(int x)
{
    Q2.push(x);
    while ((!Q1.empty())&&(!Q2.empty())&&(Q1.top()==Q2.top())) Q1.pop(),Q2.pop();
    return;
}

int QTop()
{
    while ((!Q1.empty())&&(!Q2.empty())&&(Q1.top()==Q2.top())) Q1.pop(),Q2.pop();
    return Q1.top();
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2333/Luogu3273][SCOI2011]棘手的操作(可并堆,左偏树)


HNCJ OIer 一枚