写法：可持久化非旋treap

• 定期重构的阈值该如何设定

• 能否帮忙看看为什么我写的程序在随机合并的情况下会随着种子的改变“随机”得分（80~100）不等

• 定期重构的阈值若是设定在 $3.6\times 10^6$ ，则我的程序会 MLE，稍微调低一点就不会，这是为何？

• 经实测，使用高质量的随机数生成器 mt19937 代替 rand 能够让随机合并时的正确性大幅上升。

• 经实测，Nacly_fish 的做法在同一组数据输进去的情况下，运行 $10^6$ 以上次，就会有大概率输出一次跟先前不一样的答案，这是否意味着随机合并的正确性有待商榷？(数据生成器来自本题讨论区，并使用 mt19937 加强)

@NaCly_Fish

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
typedef long long LL;
const int mod=1e9+7;
const int maxn=4e6+3;
int n,q,x,y,z,zz,zzz,cnt,tp;
int sz[maxn],ch[maxn][2],rnd[maxn];
int sum[maxn],val[maxn],add[maxn],ass[maxn];
int a[maxn];
bool rev[maxn];
int root;

void Add(int &a,int b) {
	a=(a+b>=mod?(1ll*a%mod+b)%mod:a+b);
}

int clone(int u) {
	int v=++cnt;
	sz[v]=sz[u],ch[v][0]=ch[u][0],ch[v][1]=ch[u][1];
	rnd[v]=rnd[u],rev[v]=rev[u],sum[v]=sum[u];
	val[v]=val[u],add[v]=add[u],ass[v]=ass[u];
	return v;
} 
int new_node(int k=0) {
	sz[++cnt]=1;
	ass[cnt]=-1;
	sum[cnt]=val[cnt]=k;
	rnd[cnt]=rand();
	return cnt;
}
void pushup(int now) {
	sz[now]=1;
	sum[now]=val[now];
	if(ch[now][0])
		sz[now]+=sz[ch[now][0]],Add(sum[now],sum[ch[now][0]]);
	if(ch[now][1])
		sz[now]+=sz[ch[now][1]],Add(sum[now],sum[ch[now][1]]); 
}
void pushdown(int now) {
	if(rev[now]||add[now]||ass[now]!=-1) {
		if(ch[now][0])ch[now][0]=clone(ch[now][0]);
		if(ch[now][1])ch[now][1]=clone(ch[now][1]);
	}
	if(ass[now]!=-1) {
		if(ch[now][0]) {
			add[ch[now][0]]=0;
			ass[ch[now][0]]=val[ch[now][0]]=ass[now];
			sum[ch[now][0]]=1ll*sz [ch[now][0]]*ass[now]%mod;
		}
		if(ch[now][1]) {
			add[ch[now][1]]=0;
			ass[ch[now][1]]=val[ch[now][1]]=ass[now];
			sum[ch[now][1]]=1ll*sz [ch[now][1]]*ass[now]%mod;
		}
		ass[now]=-1;
	}
	if(add[now]) {
		if(ch[now][0]) {
			Add(add[ch[now][0]],add[now]);
			Add(val[ch[now][0]],add[now]);
			Add(sum[ch[now][0]],1ll*add[now]*sz[ch[now][0]]%mod);
		}
		if(ch[now][1]) {
			Add(add[ch[now][1]],add[now]);
			Add(val[ch[now][1]],add[now]);
			Add(sum[ch[now][1]],1ll*add[now]*sz[ch[now][1]]%mod);
		}
		add[now]=0;
	}
	if(rev[now]) {
		if(ch[now][0])rev[ch[now][0]]^=1;
		if(ch[now][1])rev[ch[now][1]]^=1;
		swap(ch[now][0],ch[now][1]);
		rev[now]=0;
	}
}
int merge(int x,int y) {
//	if(x)pushdown(x);
//	if(y)pushdown(y);
	if(!x||!y)return x|y;
	if(rand()%(sz[x]+sz[y])<sz[x]) {
		pushdown(x);
		x=clone(x);
		ch[x][1]=merge(ch[x][1],y);
		pushup(x);
		return x;
	}
	else {
		pushdown(y);
		y=clone(y);
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void split(int now,int k,int &x,int &y) {
	if(!now) {
		x=y=0;
		return ;
	}
	pushdown(now);
	if(k>sz[ch[now][0]]) {
		x=clone(now);
		split(ch[x][1],k-sz[ch[x][0]]-1,ch[x][1],y);
		pushup(x);
	}
	else {
		y=clone(now);
		split(ch[y][0],k,x,ch[y][0]);
		pushup(y);
	}
}




void reverse(int l,int r) {
	split(root,r,x,z);
	split(x,l-1,x,y);
	y=clone(y);
	rev[y]^=1;
	pushdown(y);
	root=merge(x,merge(y,z));
}
void Swap(int l1,int r1,int l2,int r2) {
	if(l1>l2) { swap(l1,l2);swap(r1,r2); }
	split(root,l1-1,x,y);
	split(y,r1-l1+1,y,z);
	split(z,l2-r1-1,z,zz);
	split(zz,r2-l2+1,zz,zzz);
	// x |l1| y |r1| z |l2| zz |r2| zzz
	root=merge(merge(x,zz),merge(merge(z,y),zzz));
}
void paste(int l1,int r1,int l2,int r2) {
	bool flag=0;
	if(l1>l2) { swap(l1,l2);swap(r1,r2); flag=1;}
	split(root,l1-1,x,y);
	split(y,r1-l1+1,y,z);
	split(z,l2-r1-1,z,zz);
	split(zz,r2-l2+1,zz,zzz);
	if(flag)y=clone(zz);
	else zz=clone(y);
	root=merge(merge(x,y),merge(z,merge(zz,zzz)));
}
void update(int l,int r,int k) { // add
	split(root,r,x,z);
	split(x,l-1,x,y);
	y=clone(y);
	Add(add[y],k);
	Add(val[y],k);
	Add(sum[y],1ll*sz[y]*k%mod);
	pushdown(y);
	root=merge(x,merge(y,z));
}
void change(int l,int r,int k) { //assignment
	split(root,r,x,z);
	split(x,l-1,x,y);
	y=clone(y);
	ass[y]=k;
	val[y]=k;
	sum[y]=1ll*sz[y]*k;
	add[y]=0;
	pushdown(y);
	root=merge(x,merge(y,z));
}
int query(int l,int r) {
	split(root,r,x,z);
	split(x,l-1,x,y);
	LL res=sum[y];
	root=merge(x,merge(y,z));
	return res%mod;
}

void dfs(int u) {
	pushdown(u);
	if(ch[u][0])dfs(ch[u][0]);
	a[++tp]=val[u];
	if(ch[u][1])dfs(ch[u][1]);
}
int build(int l,int r) {
	if(l>r)return 0;
	int u=new_node(a[mid]);
	ch[u][0]=build(l,mid-1);
	ch[u][1]=build(mid+1,r);
	pushup(u);
	return u;
}

int main() {
	srand((unsigned)time(NULL));
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	root=build(1,n);
	while(q--) {
		int op,l1,r1,l2,r2,k;
		scanf("%d%d%d",&op,&l1,&r1);
		if(op==2||op==3)scanf("%d",&k);
		else if(op==4||op==5)scanf("%d%d",&l2,&r2);
		if(op==1) printf("%d\n",query(l1,r1));
		if(op==2) change(l1,r1,k);
		if(op==3) update(l1,r1,k);
		if(op==4) paste(l1,r1,l2,r2);
		if(op==5) Swap(l1,r1,l2,r2);
		if(op==6) reverse(l1,r1);
		if(cnt>3200000) {
			tp=0;
			dfs(root);
			root=cnt=0;
			root=build(1,n);
		}
	}
	tp=0;
	dfs(root);
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]%mod); 
	return 0;
}