BZOJ4399 魔法少女LJJ —— 线段树合并

题意

提示

对100%的数据 0<=m<=400000,c<=7,所有出现的数均<=1000000000,所有出现的点保证存在

【HINT】请认真阅读题面 考语文

分析

由于只有合并，没有分裂，所以只需要考虑合并联通块中的信息即可。

具体而言，在联通块的根对应的线段树下标存储该联通块下元素对应的权值。

直接线段树合并，更新新联通块的根即可。

#include<bits/stdc++.h>
using namespace std;

const int N=4e5+100,INF=1e9;
typedef long long ll;

struct segtree
{
    struct node
    {
        int siz,tag,lc,rc;
        double val;
    }s[N<<6];
    int tot,root[N],all,f[N];

    int fin(int x){return (x==f[x])?(x):(f[x]=fin(f[x]));}

    void pushup(int i)
    {
        s[i].siz=s[ s[i].lc ].siz+s[ s[i].rc ].siz;
        s[i].val=s[ s[i].lc ].val+s[ s[i].rc ].val;
    }

    void upd(int &i,int l,int r,int x,int y)
    {
        if(!i)
            i=++tot;
        if(l==r)
        {
            s[i].siz+=y;
            s[i].val+=1.0*y*(log(x));
            return ;
        }
        pushdown(i);
        int mid=(l+r)>>1;
        if(x<=mid)
            upd(s[i].lc,l,mid,x,y);
        else
            upd(s[i].rc,mid+1,r,x,y);
        pushup(i);

    }

    void pushtag(int &i)
    {
        if(!i)
            return ;
        s[i].tag=1;
        s[i].val=s[i].siz=0;
    }

    void pushdown(int i)
    {
        if(!s[i].tag)
            return ;
        pushtag(s[i].lc);
        pushtag(s[i].rc);
        s[i].tag=0;
    }

    int quek(int i,int l,int r,int k)
    {
        if(l==r)
            return l;
        pushdown(i);
        int mid=(l+r)>>1,num=s[ s[i].lc ].siz;
        if(num>=k)
            return quek(s[i].lc,l,mid,k);
        else
            return quek(s[i].rc,mid+1,r,k-num);
    }

    int que0(int i,int l,int r,int x,int y)
    {
        if(!i || s[i].siz==0)
            return 0;
        if(l>=x && r<=y)
            return s[i].siz;
        pushdown(i);
        int mid=(l+r)>>1,sum=0;
        if(x<=mid)
            sum+=que0(s[i].lc,l,mid,x,y);
        if(y>mid)
            sum+=que0(s[i].rc,mid+1,r,x,y);
        return sum;
    }

    void cl(int i,int l,int r,int x,int y)
    {
        if(!i)
            return ;
        if(l>=x && r<=y)
        {
            pushtag(i);
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(i);
        if(x<=mid)
            cl(s[i].lc,l,mid,x,y);
        if(y>mid)
            cl(s[i].rc,mid+1,r,x,y);
        pushup(i);
    }

    void create(int x)
    {
        ++all;
        f[all]=all;
        upd(root[all],1,INF,x,1);
    }

    void merg(int &i,int &j,int l,int r)
    {
        if(!i || !j)
        {
            i+=j;
            return ;
        }
        if(l==r)
        {
            s[i].siz+=s[j].siz;
            s[i].val+=s[j].val;
            return ;
        }
        pushdown(i);
        pushdown(j);
        int mid=(l+r)>>1;
        merg(s[i].lc,s[j].lc,l,mid);
        merg(s[i].rc,s[j].rc,mid+1,r);
        pushup(i);
    }

    int qsiz(int x)
    {
        x=fin(x);
        return s[ root[x] ].siz;
    }

    void grem(int x,int y)
    {

        x=fin(x);
        y=fin(y);
        if(x==y)
            return ;
        f[y]=x;
        merg(root[x],root[y],1,INF);
    }

    void mov(int rt,int x,int y,int z)
    {
        rt=fin(rt);
        if( y>INF || (x>y) )
            return ;
        int num=que0(root[rt],1,INF,x,y);
        upd(root[rt],1,INF,z,num);
        cl(root[rt],1,INF,x,y);
    }

    int gotk(int rt,int k)
    {
        rt=fin(rt);
        return quek(root[rt],1,INF,k);
    }

    int com(int x,int y)
    {
        x=fin(x);
        y=fin(y);
        return s[ root[x] ].val>s[ root[y] ].val;
    }

}T;
int n;
void work()
{
    cin>>n;
    while(n--)
    {
        int opt,x,y,ans=0;
        scanf("%d%d",&opt,&x);
        if(opt==1)
            T.create(x);
        else if(opt==7)
        {

            ans=T.qsiz(x);
            if(ans<0)printf("%d ",opt);
            printf("%d\n",ans);
        }
        else
        {
            scanf("%d",&y);
            if(opt==2)
                T.grem(x,y);
            else if(opt==3)
                T.mov(x,1,y-1,y);
            else if(opt==4)
                T.mov(x,y+1,INF,y);
            else
            {
                if(opt==5)
                    ans=T.gotk(x,y);//wrong
                else
                    ans=T.com(x,y);
                if(ans<0)printf("%d ",opt);
                printf("%d\n",ans);
            }

        }
    }
}

int main()
{
    work();
    return 0;
}