写道数据结构练练手哈哈哈

// It is made by XZZ#include
    
     #include
     
      #include
      
       #include
       
        #define il inline#define rg register#define vd void#define sta static#define pr pair
        
         typedef long long ll;using namespace std;il char gc(){    const int B=10000000;static char b[B+1],*p=b+B;    if(p==b+B)b[fread(b,1,B,stdin)]=0,p=b;    return *p?*p++:0;}il int gi(){    rg int x=0;rg bool flg=0;rg char ch=gc();    while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=gc();}    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=gc();    return flg?-x:x;}const int maxn=100001<<1;int rt,ls[maxn],rs[maxn],ran[maxn],siz[maxn],n,m;ll sum[maxn],w[maxn],tga[maxn],tgb[maxn],tgc[maxn];bool tgd[maxn];il vd Set(int&x,ll y){if(x)w[x]=y,sum[x]=siz[x]*y,tgd[x]=1,tgc[x]=y,tga[x]=tgb[x]=0;}il vd Adda(int&x,ll y){if(x)w[x]+=y*(siz[ls[x]]+1),sum[x]+=y*(1+siz[x])*siz[x]/2,tga[x]+=y;}il vd Addb(int&x,ll y){if(x)w[x]+=y,sum[x]+=siz[x]*y,tgb[x]+=y;}il vd down(int&x){    if(!x)return;    if(tgd[x])tgd[x]=0,Set(ls[x],tgc[x]),Set(rs[x],tgc[x]);    if(tga[x])Adda(ls[x],tga[x]),Adda(rs[x],tga[x]),Addb(rs[x],tga[x]*(siz[ls[x]]+1)),tga[x]=0;    if(tgb[x])Addb(ls[x],tgb[x]),Addb(rs[x],tgb[x]),tgb[x]=0;}il vd upd(int&x){    if(!x)return;    down(ls[x]),down(rs[x]);    siz[x]=siz[ls[x]]+siz[rs[x]]+1,sum[x]=sum[ls[x]]+sum[rs[x]]+w[x];}il int merge(int x,int y){    if(x==0||y==0)return x|y;    if(ran[x]