题解 P5610 【[Ynoi2013]大学】

FZzzz · 2020-04-14 17:09:13 · 题解

之前我用平衡树写这题，结果时空都被卡常。

然后有队爷跟我说可以用并查集做，今天补了一下。

这个做法超级好写，即使是我的毒瘤码风现在也在洛谷上是最短解。

首先是跟标算一样，用 vector 存下每个树的所有的倍数。

然后删除的时候我们不搞平衡树，我们每个数用一个并查集，删除的时候用并查集缩点。具体来说，就是令每个点所在的集合的根为这个点后面第一个没被删掉的点。

然后就先二分一下第一个需要被删掉的点，往后面跳就行了。

非常好写的代码：

#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
typedef long long ll;
inline ll readint(){
    ll x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=1e5+5,maxa=5e5+5;
int n,m,a[maxn];
vector<int> f[maxa],p[maxa];
int findrt(int f,int x){
    if(x==(int)p[f].size()) return x;
    return p[f][x]==x?x:p[f][x]=findrt(f,p[f][x]);
}
ll c[maxn];
inline int lowbit(int x){
    return x&-x;
}
void modify(int x,ll k){
    while(x<=n){
        c[x]+=k;
        x+=lowbit(x);
    }
}
ll query(int x){
    ll s=0;
    while(x>0){
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    m=readint();
    for(int i=1;i<=n;i++){
        a[i]=readint();
        for(int j=1;j*j<=a[i];j++) if(a[i]%j==0){
            f[j].push_back(i);
            p[j].push_back(p[j].size());
            if(j*j<a[i]){
                f[a[i]/j].push_back(i);
                p[a[i]/j].push_back(p[a[i]/j].size());
            }
        }
        modify(i,a[i]);
    }
    ll lastans=0;
    while(m--){
        int opt=readint();
        if(opt==1){
            int l,r,x;
            l=readint()^lastans;
            r=readint()^lastans;
            x=readint()^lastans;
            if(x==1) continue;
            int u=lower_bound(f[x].begin(),f[x].end(),l)-f[x].begin();
            for(int i=findrt(x,u);i<(int)f[x].size()&&f[x][i]<=r;i=(findrt(x,i+1))){
                if(a[f[x][i]]%x==0){
                    modify(f[x][i],-a[f[x][i]]);
                    modify(f[x][i],a[f[x][i]]/=x);
                }
                if(a[f[x][i]]%x!=0) p[x][i]=i+1;
            }
        }
        else{
            int l,r;
            l=readint()^lastans;
            r=readint()^lastans;
            printf("%lld\n",lastans=query(r)-query(l-1));
        }
    }
    return 0;
}