luogu P3987 我永远喜欢珂朵莉~

又是一道毒瘤数据结构。。。

传送门

这题的思路有点像总统选举那个题，对每个因子建棵平衡树，维护能被它整除的数的位置。

除的时候在这个因子的平衡树上暴力dfs这个区间，模拟题目描述

如果区间中一个数被除了后不能整除这个因子，就把他删除。

之后单点修改可以用树状数组。

以及一些许许多多的细节。。。

比如可以只对询问出现的因子建平衡树，所以可以离线把一个因子的倍数位置放到一个vector里之后一块建

比如建树一定要用build而不是暴力insert，因为这题好像有1e7+个节点。

再比如不能在dfs的时候直接删除，那样破坏树的结构，所以要把删除的数放到一个栈里。

平衡树空间3e7似乎很稳。

关于内存池：没多大必要，如果要用内存池就得在询问的时候建树。。。

用的splay，在一个luogu特别卡的晚上跑到了约11900s，然而第二天早上怎么卡常都没有之前快了。

#include<vector>
#include<cstdio>
#include<iostream>
#define ll long long
#define re register
using namespace std;
inline char gc(){
    static char buf[1<<23],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++;
}
inline int init(){
    re char c=gc();re int a=0,w=1;
    while((c<'0'||c>'9')&&c-'-')c=gc();
    if(c=='-')w=-w,c=gc();
    while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+(c^48),c=gc();
    return a*w;
}
inline void pc(re char c,re int p=0){
    static char buf[1<<23],*p1=buf;
    if(p){fwrite(buf,1,p1-buf,stdout);return ;}
    *p1++=c;
    if(p1==buf+(1<<23))fwrite(buf,1,1<<23,stdout),p1=buf;
}
void write(re ll x){
    if(x>9)write(x/10);
    pc(x%10+'0');
}
inline char getc(){
    char c=gc();
    while(!isupper(c)) c=gc();
    return c;
}
struct tree{
    int num,val,fa,ch[2];
}t[50260817];
struct ques{
    int x,p,l,r;
}q[100001];
ll c[100001];
int a[100001],cut[500001],n,tot,m,o[500001],maxn;
vector<int> num[500001];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){while (x<=n) c[x]+=y,x+=lowbit(x);}
inline ll query(int x){ll num=0;while (x) num+=c[x],x-=lowbit(x);return num;}
struct Splay{
    int rt;
    inline void rotate(int x){
        int y=t[x].fa,z=t[y].fa,f=(t[y].ch[1]==x);
        t[x].fa=z; t[z].ch[t[z].ch[1]==y]=x;
        t[t[x].ch[f^1]].fa=y; t[y].ch[f]=t[x].ch[f^1];
        t[x].ch[f^1]=y; t[y].fa=x;
    }
    inline void splay(int x,int goal){
        int y,z;
        while (t[x].fa!=goal){
            y=t[x].fa,z=t[y].fa;
            if (z!=goal)
                if ((t[y].ch[1]==x)^(t[z].ch[1]==y)) rotate(x); else rotate(y);
            rotate(x);
            }
        if (!goal) rt=x;
    }
//	inline void ins(int x,int z){
//		int u=rt; printf("%d %d %d\n",x,z,rt);
//		while (t[u].ch[x>t[u].val]) u=t[u].ch[x>t[u].val];
//		int y=++tot;
//		t[u].ch[x>t[u].val]=y; t[y].num=z;
//		t[y].val=x; t[y].fa=u; splay(y,0);
//	}
    inline void find(int x){
        int u=rt;
        while (t[u].val!=x&&t[u].ch[x>t[u].val]) u=t[u].ch[x>t[u].val];
        splay(u,0);
    }
    inline int nex(int x,int f){
        find(x);
        if (t[rt].val<=x&&!f) return rt;
        if (t[rt].val>=x&&f) return rt;
        int y=t[rt].ch[f];
        while (t[y].ch[f^1]) y=t[y].ch[f^1];
        return y;
    }
    inline void del(int x){
        int u=nex(x-1,0),v=nex(x+1,1);
        splay(u,0); splay(v,u);
        t[v].ch[0]=0; t[t[v].ch[0]].fa=0;
    }
    void dfs(int x){
        if (t[x].ch[0]) dfs(t[x].ch[0]);
        if (t[x].ch[1]) dfs(t[x].ch[1]);
        int u=t[x].val;
        if (a[u]%t[x].num==0){
            int z=a[u]/t[x].num;
            add(u,z-a[u]); a[u]=z;
        }
        else{
            cut[++cut[0]]=u; return;
        }
    }
    inline void arrange(int l,int r){
        int u=nex(l-1,0),v=nex(r+1,1);
        splay(u,0); splay(v,u);
        if (t[v].ch[0])
            dfs(t[v].ch[0]);
        for (int i=1; i<=cut[0]; i++) del(cut[i]);
        cut[0]=0;
    }	
    inline void print(int x){
        if (t[x].ch[0]) print(t[x].ch[0]);
        printf("id:%d num:%d val:%d fa:%d ch0:%d ch1:%d\n"
            ,x,t[x].num,t[x].val,t[x].fa,t[x].ch[0],t[x].ch[1]);
        if (t[x].ch[1]) print(t[x].ch[1]);
    }
    inline void debug(){print(rt);}
    inline int build(int l,int r,int fa,int x){
        if (l>r) return 0;
        int y=++tot,mid=(l+r)>>1;
        t[y].val=num[x][mid];
        t[y].fa=fa; t[y].num=x;
        t[y].ch[0]=build(l,mid-1,y,x);
        t[y].ch[1]=build(mid+1,r,y,x);
        return y;
    }
}sp[500001];
int main(){
    n=init(),m=init();
    for (int i=1; i<=n; i++){
        a[i]=init();
        add(i,a[i]); maxn=max(maxn,a[i]);
    }
    for (int i=1; i<=m; i++){
        q[i].p=init(),q[i].l=init(),q[i].r=init();
        if (q[i].p==1){
            q[i].x=init();
            if (q[i].x>maxn) continue;
            if (q[i].x!=1) o[q[i].x]=1;
        }
    }
    for (int i=1; i<=maxn; i++){
        if (o[i]) num[i].push_back(-2e9);
//		if (o[i]) sp[i].ins(-2e9,i),sp[i].ins(2e9,i);
//		sp[i].debug();
    }
    for (int i=1; i<=n; i++){
        for (int j=1; j*j<=a[i]; j++){
            if (a[i]%j!=0) continue;
            if (!a[i]) continue;
            if (o[j]) num[j].push_back(i);
            if (a[i]/j!=j&&o[a[i]/j]) num[a[i]/j].push_back(i);
        }
    }
    for (int i=1; i<=maxn; i++){
        if (o[i]){
            num[i].push_back(2e9);
            sp[i].rt=sp[i].build(0,num[i].size()-1,0,i);
        }
    }
    // sp[8].debug();
    for (int i=1; i<=m; i++){
        if (q[i].p==1){
            if (q[i].x==1) continue;
            if (q[i].x>maxn) continue;
            sp[q[i].x].arrange(q[i].l,q[i].r);
        }
        else write(query(q[i].r)-query(q[i].l-1)),pc('\n');
    }
    pc(' ',1);
    return 0;
}