感谢的题解，经过无数次失败的尝试之后终于AC了...

线段树是维护区间信息的强大工具，但它的形态是固定的，只支持修改和删除操作，不支持插入、反转、复制、分裂合并等操作，而treap支持。这道题有个区间复制的操作，因此只能用treap来代替了。

注意几个坑点：

1.对于操作2，当k<r-l+1时，不是将[l-k,r-k]中的元素直接替换到[l,r]上，而是将[l-k,l-1]中的元素复制多次再替换到[l,r]上，因此需要对[l-k,l-1]区间反复自我merge直至长度大于等于r-l+1，类似倍增的方式。

2.如果对每个结点设置一个静态的随机因子，那么对区间进行复制时，会产生大量重复的随机因子，严重影响树的平衡性。因此可以去掉随机因子，在对结点u,v进行merge的时候动态取一个随机数rnd，检查rnd%(siz[u]+siz[v])与siz[u]的关系来决定以哪种方式进行合并。考虑到评测OS是Windows，rand函数的上限只有2^15-1，因此可以采用rand()<<15|rand()的方法将两个rand函数拼凑起来，这样上限就扩大到2^30-1了。

3.操作3中的merge可以不用可持久化，但操作2中的merge必须可持久化，否则会出现莫名其妙的错误（这里查错查了很久，我暂时也说不清为什么）

4.本题对内存的限制非常严格，因此需要定期检查结点数量，如果快要超过内存上限了，就要对整个序列进行暴力重构。

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int N=28e5+10,inf=0x3f3f3f3f; 5 int ch[N][2],val[N],siz[N],tot,n,m,rt,A,q[200010],nq; 6 ll sum[N]; 7 #define l(u) ch[u][0] 8 #define r(u) ch[u][1] 9 int rnd() {
   return rand()<<15|rand();}10 int newnode(int x) {
   int u=++tot; val[u]=sum[u]=x,siz[u]=1,l(u)=r(u)=0; return u;}11 int cpy(int u) {
   int w=++tot; val[w]=val[u],sum[w]=sum[u],siz[w]=siz[u],l(w)=l(u),r(w)=r(u); return w;}12 void pu(int u) {siz[u]=siz[l(u)]+siz[r(u)]+1,sum[u]=sum[l(u)]+sum[r(u)]+val[u];}13 void sp(int w,int k,int& u,int& v) {14     if(!w) {u=v=0; return;}15     if(k>=siz[l(w)]+1)u=cpy(w),sp(r(w),k-(siz[l(w)]+1),r(u),v),pu(u);16     else v=cpy(w),sp(l(w),k,u,l(v)),pu(v);17 }18 void mg(int& w,int u,int v,int f=0) {19     if(!u||!v) {w=u|v; return;}20     if(rnd()%(siz[u]+siz[v])
      
       r) {u=0; return;}47     int mid=(l+r)>>1;48     u=newnode(q[mid]);49     build(l(u),l,mid-1),build(r(u),mid+1,r),pu(u);50 }51 void rebuild() {tot=siz[A],nq=0,dfs(rt),build(rt);}52 int main() {53     srand(time(0));54     scanf("%d%d",&n,&m);55     for(int i=0; i
       
        2500000)rebuild();65     }66     return 0;67 }