rt 只有第3个点RE 98pts，数据在这(只有输入)

代码如下

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<vector>
#include<algorithm>
#define ll long long
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,a[maxn],maxa,lastans;
int rt[maxn*5],q[maxn],tot;
ll t[maxn*2];
vector<int> tool[maxn*5];
struct node
{
	int ch[2],fa,val,si;
}tr[maxn*500];

ll read()
{
	ll num,sign=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')sign=-1;
	num=c-'0';
	while((c=getchar())>='0'&&c<='9')
		num=(num<<1)+(num<<3)+c-'0';
	return num*sign;
}

inline void modify(int x,int val)
{
	for(;x<=n;x+=x&-x)t[x]+=val;
}

inline ll query(int x)
{
	ll res=0;
	for(;x;x-=x&-x)res+=t[x];
	return res;
}

inline void update(int u)
{
	tr[u].si=tr[tr[u].ch[0]].si+tr[tr[u].ch[1]].si+1;
}

inline void rotate(int x)
{
	int y=tr[x].fa;
	int z=tr[y].fa;
	int k=tr[y].ch[1]==x;
	tr[y].ch[k]=tr[x].ch[k^1];
	if(tr[x].ch[k^1])tr[tr[x].ch[k^1]].fa=y;
	tr[x].ch[k^1]=y;
	tr[x].fa=z;
	tr[y].fa=x;
	if(z)tr[z].ch[tr[z].ch[1]==y]=x;
	update(y),update(x);
}

inline void splay(int x,int goal,int id)
{
	while(tr[x].fa!=goal)
	{
		int y=tr[x].fa;
		int z=tr[y].fa;
		if(z!=goal)
			rotate((tr[z].ch[1]==y)^(tr[y].ch[1]==x)?x:y);
		rotate(x);
	}
	if(!goal)rt[id]=x;
}

int find_next(int u,int val)
{
	int res;
	if(!u)return val;
	if(tr[u].val<=val)return find_next(tr[u].ch[1],val);
	else
	{
		res=find_next(tr[u].ch[0],val);
		if(res==val)res=u;
		return res;
	}
}

int find_last(int u,int val)
{
	int res;
	if(!u)return val;
	if(tr[u].val>=val)return find_last(tr[u].ch[0],val);
	else
	{
		res=find_last(tr[u].ch[1],val);
		if(res==val)res=u;
		return res;
	}
}

inline void del(int u,int root)
{
	while(true)
	{
		if(tr[u].ch[0])rotate(tr[u].ch[0]);
		else if(tr[u].ch[1])rotate(tr[u].ch[1]);
		else break;
	}
	tr[tr[u].fa].ch[tr[tr[u].fa].ch[1]==u]=0;
	update(tr[u].fa);
}

inline void dfs(int u,int val)
{
	if(!(a[tr[u].val]%val))modify(tr[u].val,a[tr[u].val]/val-a[tr[u].val]),a[tr[u].val]/=val;
	if(tr[u].ch[0])dfs(tr[u].ch[0],val);
	if(tr[u].ch[1])dfs(tr[u].ch[1],val);
	if(a[tr[u].val]%val)del(u,rt[val]);
	update(u);
}

inline void split(int id,int x,int y,int val)
{
	if(!rt[id])return;
	int l=find_last(rt[id],x);
	int r=find_next(rt[id],y);
	splay(l,0,id),splay(r,l,id);
	if(!tr[r].ch[0])return;
	dfs(tr[r].ch[0],val);
}

void build(int &u,int l,int r,int fa)
{
	if(l>r)return;
	if(!u)u=++tot;
	int mid=(l+r)>>1;
	tr[u].fa=fa,tr[u].val=q[mid];
	build(tr[u].ch[0],l,mid-1,u),build(tr[u].ch[1],mid+1,r,u);
	update(u);
}

int main()
{
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
	{
		a[i]=read(),modify(i,a[i]);
		maxa=max(a[i],maxa);
		for(register int j=1;j*j<=a[i];++j)
			if(a[i]%j==0)
			{
				tool[j].push_back(i);
				if(j*j!=a[i])tool[a[i]/j].push_back(i);
			}
	}
	for(register int i=2;i<maxa;++i)
	{
		int res=(int)tool[i].size();
		for(register int j=0;j<res;++j)q[j+1]=tool[i][j];
		q[0]=-inf,q[res+1]=inf;
		build(rt[i],0,res+1,0);
	}
	ll lastans=0;
	for(register int res,i=1;i<=m;++i)
	{
		ll x,l,r;
		res=read(),l=read(),r=read();
		l^=lastans;
		r^=lastans;
		if(res==1)
		{
			x=read();
			x^=lastans;
			split(x,l,r,x);
		}
		else
		{
			lastans=query(r)-query(l-1);
			printf("%lld\n",lastans);
		}
	}
	return 0;
}

可能有点点长,求大佬没事看看