bzoj 2333 [SCOI2011]棘手的操作 —

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2333

稍微复杂，参考了博客：http://hzwer.com/5780.html

用 set 维护全局的最大值就可以方便地删除和查询了；

大概就是写一堆关于可并堆的子函数吧；

这里还用了斜堆，但其实并不明白原因是什么...

斜堆和左偏树只有一点点不同，它不用 dis ，而是每次都交换左右儿子，随机地保证了复杂度？

要注意 solvetag 函数是要把跟 x 有关的所有 lzy 关系都处理掉，所以也要处理 x 到其儿子的；

还有 del 处的顺序，小心不要让 set 查询的东西为空。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

int const maxn=3e5+;

int n,m,a[maxn],ls[maxn],rs[maxn],fa[maxn],lzy[maxn],ad,sta[maxn],top;

multiset<int>st;

char ch[];

int find(int x){while(fa[x])x=fa[x]; return x;}

void pushdown(int x)

{

    if(!lzy[x])return;

    if(ls[x])lzy[ls[x]]+=lzy[x],a[ls[x]]+=lzy[x];

    if(rs[x])lzy[rs[x]]+=lzy[x],a[rs[x]]+=lzy[x];

    lzy[x]=;

}

int merge(int x,int y)

{

    if(!x||!y)return x+y;

    if(a[x]<a[y])swap(x,y);

    pushdown(x);

    rs[x]=merge(rs[x],y);

    fa[rs[x]]=x;

    swap(ls[x],rs[x]);

    return x;

}

void solvetag(int x)

{

//    x=fa[x];    //从 x 开始，使 x 对儿子没有 lzy 的关联

    while(x)sta[++top]=x,x=fa[x];

    while(top)pushdown(sta[top]),top--;

}

int del(int x)

{

    solvetag(x);

    int f=fa[x],k=merge(ls[x],rs[x]);

    ls[x]=rs[x]=fa[x]=;

    fa[k]=f;

    if(ls[f]==x)ls[f]=k;

    else rs[f]=k;

    return find(k);

}

int rd()

{

    int ret=,f=; char cc=getchar();

    while(cc<''||cc>''){if(cc=='-')f=-; cc=getchar();}

    while(cc>=''&&cc<='')ret=(ret<<)+(ret<<)+cc-'',cc=getchar();

    return ret*f;

}

int main()

{

    n=rd();

    for(int i=;i<=n;i++)a[i]=rd(),st.insert(a[i]);

    m=rd();

    for(int i=,x,y;i<=m;i++)

    {

        cin>>ch;

        if(ch[]=='U')

        {

            x=rd(); y=rd();

            x=find(x); y=find(y);

            if(x==y)continue;//

            if(merge(x,y)==x)st.erase(st.find(a[y]));

            else st.erase(st.find(a[x]));

        }

        if(ch[]=='A'&&ch[]=='')

        {

            x=rd(); y=rd();

            solvetag(x);

//            int u=del(x); a[x]+=y;

//            st.erase(st.find(a[u])); //如果 x 只有自己，则删除后为空！ 则RE

//            st.insert(a[merge(u,x)]);

            st.erase(st.find(a[find(x)]));

            a[x]+=y;

            st.insert(a[merge(x,del(x))]);

        }

        if(ch[]=='A'&&ch[]=='')

        {

            x=rd(); y=rd();

            int u=find(x); lzy[u]+=y; a[u]+=y;

            st.erase(st.find(a[u]-y));

            st.insert(a[u]);

        }

        if(ch[]=='A'&&ch[]=='')y=rd(),ad+=y;

        if(ch[]=='F'&&ch[]=='')x=rd(),solvetag(x),printf("%d\n",a[x]+ad);

        if(ch[]=='F'&&ch[]=='')x=rd(),printf("%d\n",a[find(x)]+ad);

        if(ch[]=='F'&&ch[]=='')printf("%d\n",*(--st.end())+ad);

    }

    return ;

}

但是左偏树也可以做，而且也许是 set 常数太大，两种做法用时相差无几(都很慢，5000ms+)；

不过比斜堆多开了一个数组呢。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

using namespace std;

int const maxn=3e5+;

int n,m,a[maxn],ls[maxn],rs[maxn],fa[maxn],lzy[maxn],ad,sta[maxn],top,dis[maxn];

multiset<int>st;

char ch[];

int find(int x){while(fa[x])x=fa[x]; return x;}

void pushdown(int x)

{

    if(!lzy[x])return;

    if(ls[x])lzy[ls[x]]+=lzy[x],a[ls[x]]+=lzy[x];

    if(rs[x])lzy[rs[x]]+=lzy[x],a[rs[x]]+=lzy[x];

    lzy[x]=;

}

int merge(int x,int y)

{

    if(!x||!y)return x+y;

    if(a[x]<a[y])swap(x,y);

    pushdown(x);

    rs[x]=merge(rs[x],y);

    fa[rs[x]]=x;

    if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);

    if(rs[x])dis[x]=dis[rs[x]]+;

    else dis[x]=;

    return x;

}

void solvetag(int x)

{

//    x=fa[x];    //从 x 开始，使 x 对儿子没有 lzy 的关联

    while(x)sta[++top]=x,x=fa[x];

    while(top)pushdown(sta[top]),top--;

}

int del(int x)

{

    solvetag(x);

    int f=fa[x],k=merge(ls[x],rs[x]);

    ls[x]=rs[x]=fa[x]=dis[x]=;

    fa[k]=f;

    if(ls[f]==x)ls[f]=k;

    else rs[f]=k;

    return find(k);

}

int rd()

{

    int ret=,f=; char cc=getchar();

    while(cc<''||cc>''){if(cc=='-')f=-; cc=getchar();}

    while(cc>=''&&cc<='')ret=(ret<<)+(ret<<)+cc-'',cc=getchar();

    return ret*f;

}

int main()

{

    n=rd();

    for(int i=;i<=n;i++)a[i]=rd(),st.insert(a[i]);

    m=rd();

    for(int i=,x,y;i<=m;i++)

    {

        cin>>ch;

        if(ch[]=='U')

        {

            x=rd(); y=rd();

            x=find(x); y=find(y);

            if(x==y)continue;//

            if(merge(x,y)==x)st.erase(st.find(a[y]));

            else st.erase(st.find(a[x]));

        }

        if(ch[]=='A'&&ch[]=='')

        {

            x=rd(); y=rd();

            solvetag(x);

//            int u=del(x); a[x]+=y;

//            st.erase(st.find(a[u])); //如果 x 只有自己，则删除后为空！ 则RE

//            st.insert(a[merge(u,x)]);

            st.erase(st.find(a[find(x)]));

            a[x]+=y;

            st.insert(a[merge(x,del(x))]);

        }

        if(ch[]=='A'&&ch[]=='')

        {

            x=rd(); y=rd();

            int u=find(x); lzy[u]+=y; a[u]+=y;

            st.erase(st.find(a[u]-y));

            st.insert(a[u]);

        }

        if(ch[]=='A'&&ch[]=='')y=rd(),ad+=y;

        if(ch[]=='F'&&ch[]=='')x=rd(),solvetag(x),printf("%d\n",a[x]+ad);

        if(ch[]=='F'&&ch[]=='')x=rd(),printf("%d\n",a[find(x)]+ad);

        if(ch[]=='F'&&ch[]=='')printf("%d\n",*(--st.end())+ad);

    }

    return ;

}

巴特西

bzoj 2333 [SCOI2011]棘手的操作 —— 可并堆

最新文章

热门文章