【Ynoi2013】大学/【洛谷P3987】我永远喜欢珂朵莉~
平衡树或并查集
题目大意：
给定一个数列，需要支持以下操作：
- 给定区间和一个数 $x$，将 $x$ 的倍数除以 $x$。
- 区间求和。
题解：
这个题我很早就写过，为什么现在又要写一遍呢？
一个是因为我超喜欢这题的题目名称和题面qwq，另外一个是这题是 [Ynoi2013]D2T1，而那个版本将要缩短时限并加强数据，然后我之前写的那个版本常数大上天了……
顺便帮 lxl 造了几组数据卡掉了一堆暴力和高复杂度算法（例如 $O(nd\log d)$ 的那个做法），并写了 std 因为 lxl 原来那个常数也挺大的……
啊然后这题的做法。
先特判掉 $1$，然后每个数最多被除以 $\log w$ 次。也就是说我们只需要知道每次需要修改哪些数，然后暴力改掉就好了。
$500000$ 内因数最多的数只有 $200$ 个左右，不是很大。考虑对每个因数开一个数据结构，里面按照位置从小到大的顺序，存储所有包含这个因数的数的位置。
然后考虑除以 $k$ 的操作，我们找到 $k$ 这个因数对应的数据结构，在里面把在询问区间里的位置提取出来，然后暴力除掉 $k$。
然后，如果这个数除掉 $k$ 以后，不再是 $k$ 的倍数了，那么就把它从数据结构中永久删除。不然复杂度显然不对啊我每次都让你除以 $k$ 你每次都扫这么多数肯定要没。事实上有一种只存质因数的做法就存在这个问题然后我随手安排掉了。
这样还会有问题，因为你除以 $k$ 以后，可能原来某个因数现在不是它的因数了。那到时候访问到那个因数了，要除掉之前先判一下是不是 $k$ 的倍数就好了，不是的话就直接删了跑路。
至于区间求和，随便搞个树状数组就好了。
好了那么我们用什么数据结构维护这个东西呢。你可以用 set，那你一开始初始化的时候就要用特技否则复杂度就变成 $O(nd\log n)$ 了那你也没了。
手写平衡树是一个选择，因为平衡树的初始化是可以线性的。
还有用 vector 的人才，那个 erase 操作的速度是真的快我不能卡死不过我不信你能进 1s。
然后我写的是并查集。相当于把删掉的点和前面的并起来，存一下每个连通块最左边的点，这个点是真实存在的，其他的都是被删掉的。实际操作的时候，在序列上二分右端点，然后往左跳即可。
这些都不是复杂度瓶颈，瓶颈在于你一开始要插入 $nd$ 个位置。
于是时间复杂度 $O(nd)$。
还是有写平衡树的老哥用玄学剪枝和神仙卡常技巧跑得飞快的啊……自卑了。
对于本题的原数据，最慢的点成功卡进 $600\rm ms$。评测机玄学波动我也很无奈啊
这份代码开不开 O2 速度差别不大。平衡树不厌氧我厌氧
upd 2019/12/4
嗯好现在[Ynoi2013]D2T1放好了，时空缩小并改成了强制在线qwq
Code（强在版本）：
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int M=5e5+5,N=1e5+5;
typedef long long LL;
inline int readint(){
int c=getchar(),d=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())d=d*10+(c^'0');
return d;
}
inline LL readLL(){
int c=getchar();LL d=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())d=d*10+(c^'0');
return d;
}
int a[N],n,m;
LL B[N];
inline void add(int i,int x){for(;i<=n;i+=i&-i)B[i]+=x;}
inline LL ask(int i){LL x=0;for(;i;i&=i-1)x+=B[i];return x;}
int pool[800*N],*NL=pool;
bool vis[M];
struct data{
int*b,n,*L,*fa,*sz,k;
inline void init(int size,int kk){
size+=2;
b=NL,NL+=size;
L=NL,NL+=size;
fa=NL,NL+=size;
sz=NL,NL+=size;
n=0,k=kk,b[0]=0;
}
inline void build(){
for(register int i=0;i<=n;++i)
sz[i]=1,fa[i]=L[i]=i;
}
inline void insert(int v){b[++n]=v;}
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
inline void merge(int x,int y){
if(sz[x]<sz[y])swap(x,y);
sz[x]+=sz[y],fa[y]=x,L[x]=min(L[x],L[y]);
}
void modify(int l,int r){
int rv=upper_bound(b+1,b+n+1,r)-b-1;
for(;b[L[find(rv)]]>=l;){
rv=find(rv);
const int pos=b[L[rv]];
if(a[pos]%k){
merge(rv,find(L[rv]-1));
continue;
}
add(pos,a[pos]/k-a[pos]);
a[pos]/=k;
if(a[pos]%k){
merge(rv,find(L[rv]-1));
continue;
}
rv=L[rv]-1;
}
}
}d[M];
int siz[M],lim,head[M],val[M*20],nxt[M*20],cnt,tot[M];
int main(){
n=readint(),m=readint();
for(int i=1;i<=n;++i)add(i,a[i]=readint()),++tot[a[i]];
lim=*max_element(a+1,a+n+1);
for(int i=2;i<=lim;++i){
for(int j=i;j<=lim;j+=i)
val[++cnt]=i,nxt[cnt]=head[j],head[j]=cnt;
if(tot[i])
for(int j=head[i];j;j=nxt[j])siz[val[j]]+=tot[i];
}
for(int i=2;i<=lim;++i)
if(siz[i])d[i].init(siz[i],i);
for(int i=1;i<=n;++i)
for(int j=head[a[i]];j;j=nxt[j])d[val[j]].insert(i);
LL ans=0;
while(m--){
int op=readint(),l=readLL()^ans,r=readLL()^ans;
if(op==2)printf("%lld\n",ans=ask(r)-ask(l-1));else{
int k=readLL()^ans;
if(k==1||!siz[k])continue;
if(!vis[k])d[k].build(),vis[k]=1;
d[k].modify(l,r);
}
}
return 0;
}