B 色球

用平衡树模拟这个过程，每个点维护它代表的小球的颜色和个数。

操作一新建一个颜色为 x，个数为 y 的结点。

操作二是基本的平衡树删除操作。

操作三，把第 u 个桶的平衡树打上翻转标记，再合并到第 v 个桶的平衡树上。

Code：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const int maxn=3e5+5;

template <typename T>
inline void read(T &x)
{
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    x*=f;
}

int n,m;

namespace Treap
{
    int tot,pool[maxn],top;
    int ch[maxn][2];
    lxl siz[maxn],cnt[maxn];
    int val[maxn],rnd[maxn];
    bool rev[maxn];
    inline int new_node()
    {
        int p=top?pool[top--]:++tot;
        ch[p][0]=ch[p][1]=0;
        siz[p]=cnt[p]=0;
        val[p]=rnd[p]=0;
        rev[p]=false;
        return p;
    }
    inline void reverse(int p)
    {
        swap(ch[p][0],ch[p][1]);
        rev[p]^=1;
    }
    inline void push_down(int p)
    {
        if(!rev[p]) return;
        reverse(ch[p][0]);
        reverse(ch[p][1]);
        rev[p]=0;
    }
    inline void update(int p)
    {
        siz[p]=siz[ch[p][0]]+siz[ch[p][1]]+cnt[p];
    }
    void split_rnk(int p,int k,int &x,int &y,int &z)
    {
        if(!p) return x=y=z=0,void();
        push_down(p);
        if(siz[ch[p][0]]>=k)
        {
            z=p;
            split_rnk(ch[p][0],k,x,y,ch[p][0]);
        }
        else if(siz[ch[p][0]]+cnt[p]<k)
        {
            x=p;
            split_rnk(ch[p][1],k-siz[ch[p][0]]-cnt[p],ch[p][1],y,z);
        }
        else
        {
            x=ch[p][0],y=p,z=ch[p][1];
            ch[p][0]=ch[p][1]=0;
        }
        update(p);
    }
    int merge(int a,int b)
    {
        if(!a||!b) return a|b;
        push_down(a),push_down(b);
        if(rnd[a]<rnd[b])
        {
            ch[a][1]=merge(ch[a][1],b);
            update(a);
            return a;
        }
        else
        {
            ch[b][0]=merge(a,ch[b][0]);
            update(b);
            return b;
        }
    }
    inline int new_node(int s,int c)
    {
        if(!s) return 0;
        int p=new_node();
        siz[p]=cnt[p]=s;
        val[p]=c;
        rnd[p]=rand();
        return p;
    }
    inline void erase(int &p)
    {
        if(!p) return;
        erase(ch[p][0]);
        erase(ch[p][1]);
        pool[++top]=p;
        p=0;
    }
    // inline void print(int p)
    // {
    //     if(!p) return;
    //     push_down(p);
    //     print(ch[p][0]);
    //     for(int i=1;i<=cnt[p];++i)
    //         printf("%d ",val[p]);
    //     print(ch[p][1]);
    // }
}
int rt[maxn];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
#endif
    read(n),read(m);
    char opt[5];
    int x,y,z;
    while(m--)
    {
        scanf(" %s",opt);
        read(x),read(y);
        if(opt[2]=='s')
        {
            read(z);
            rt[z]=Treap::merge(Treap::new_node(x,y),rt[z]);
        }
        else if(opt[2]=='p')
        {
            int a,b,c;
            Treap::split_rnk(rt[y],x,a,b,c);
            rt[y]=Treap::merge(Treap::new_node(Treap::siz[a]+Treap::cnt[b]-x,Treap::val[b]),c);
            printf("%d\n",Treap::val[b]);
            Treap::erase(a);
            Treap::erase(b);
        }
        else
        {
            Treap::reverse(rt[x]);
            rt[y]=Treap::merge(rt[x],rt[y]);
            rt[x]=0;
        }
        // puts("---");
        // for(int i=1;i<=n;++i)
        //     Treap::print(rt[i]),puts("");
        // puts("---");
    }
    return 0;
}