链接：https://www.luogu.com.cn/problem/P5610
题目描述：给定一个长为\(n\)的序列\(a\)，支持区间为\(d\)倍数的除以\(d\)的操作，以及区间查询和的操作，强制在线。
题解：可以发现颜色均摊。
所以我们就是要求区间为\(d\)倍数是哪一些。我们可以朝着暴力的做法想，将所有点插入至其约数集合，然后查询\([l,r]\)的点即可。
但\(set\)不支持整体建树，所以我们要开\(500000\)个平衡树维护，当然要整体的分治建树。
可以发现只支持平衡树单点删除与查询，所以\(treap\)可以不需要旋转。
当然这题有个更简单的做法，可以用并查集替代平衡树，然后删除就将\(x\)想\(pv_{x}\)合并，这样就可以查到合法元素，然后这样做复杂度显著降低。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
struct node
{
int l,r,data;
};
node tree[20000001];
long long n,top,res,a[500001];
long long c[500001];
int rt[500001];
vector<int>p[500001];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int d)
{
for (;x<=n;x+=lowbit(x))
c[x]+=d;
return;
}
long long sum(int x)
{
res=0;
for (;x>=1;x-=lowbit(x))
res+=c[x];
return res;
}
int new_node(int x)
{
tree[++top].data=x;
return top;
}
int build_tree(int op,int l,int r)
{
if (l>r)
return 0;
int mid=(l+r)/2;
int P=new_node(p[op][mid]);
tree[P].l=build_tree(op,l,mid-1);
tree[P].r=build_tree(op,mid+1,r);
tree[P].data=p[op][mid];
return P;
}
int nxt(int &k)
{
if (tree[k].l)
return nxt(tree[k].l);
int tmp=tree[k].data;
k=tree[k].r;
return tmp;
}
void del(int &k)
{
int tmp;
if (tree[k].r)
{
tmp=nxt(tree[k].r);
tree[k].data=tmp;
}
else
k=tree[k].l;
}
int find(int op,int &k,int l,int r)
{
if (k==0)
return 0;
int tmp;
if (tree[k].data>=l)
{
if (tmp=find(op,tree[k].l,l,r))
return tmp;
if (tree[k].data<=r)
{
if (a[tree[k].data]%op==0)
{
add(tree[k].data,-a[tree[k].data]);
a[tree[k].data]/=op;
add(tree[k].data,a[tree[k].data]);
}
tmp=tree[k].data;
if (a[tree[k].data]%op!=0)
del(k);
return tmp;
}
return 0;
}
else
return find(op,tree[k].r,l,r);
}
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
signed main()
{
long long q,op,l,r,x,tmp,lst,ans=0;
n=read(),q=read();
for (int i=1;i<=n;++i)
{
a[i]=read();
add(i,a[i]);
for (int j=2;j*j<=a[i];++j)
if (a[i]%j==0)
{
p[j].push_back(i);
if (j*j!=a[i])
p[a[i]/j].push_back(i);
}
p[a[i]].push_back(i);
}
for (int i=2;i<=5e5;++i)
rt[i]=build_tree(i,0,p[i].size()-1);
while (q--)
{
op=read(),l=lst=read(),r=read();
l^=ans;
lst^=ans;
r^=ans;
if (op==1)
{
x=read();
x^=ans;
if (x!=1)
while (tmp=find(x,rt[x],lst,r))
lst=tmp+1;
}
else
{
ans=sum(r)-sum(l-1);
printf("%lld\n",ans);
}
}
return 0;
}