[Ynoi2013] 大学 题解 DSU

· · 题解

题目传送门

题意

Sol

真就卡常 最后改成指针才行

考虑一个数的因数个数不超过 2\sqrt{a_i}，不妨对每个因数开链表，记录其倍数位置。

考虑每个数最多能被操作 \log{a_i} 次，我们每次暴力修改链表就行了。

区间和可以写个 BIT，毕竟常数小。（

总复杂度 O(n\sqrt{a_i}+n\log n\log {a_i})。

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back

using namespace std;
typedef long long ll;

template <typename T> void rd(T &x){
    int fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(ll x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}

// ---------- IO ---------- //

const int N=5e5+5;
int n,m,a[N];
vector<int> f[N],fa[N];

ll sum[N],ans;

inline int lowbit(int x){return x&(-x);}

inline void add(int x,ll k){
    while(x<=n) sum[x]+=k,x+=lowbit(x);
}

inline ll query(int x){
    ll s=0;
    while(x) s+=sum[x],x-=lowbit(x);
    return s;
}

// ---------- BIT ---------- //

inline int found(int pos,int x){
    if(x>=fa[pos].size()) return x;
    return fa[pos][x]==x?fa[pos][x]:fa[pos][x]=found(pos,fa[pos][x]);
}

// ---------- DSU ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);
    for(re i=1;i<=n;++i){
        rd(a[i]);add(i,a[i]);
        for(re j=1;j*j<=a[i];++j)
            if(a[i]%j==0){
                f[j].pb(i);fa[j].pb(fa[j].size());
                if(j*j!=a[i]) f[a[i]/j].pb(i),fa[a[i]/j].pb(fa[a[i]/j].size());
            }
    }
    int op,l,r,x;
    for(re i=1;i<=m;++i){
        rd(op);rd(l);rd(r);l^=ans;r^=ans;
        if(op==1){
            rd(x);x^=ans;
            if(x==1) continue;
            int st=lower_bound(f[x].begin(),f[x].end(),l)-f[x].begin();
            for(re j=found(x,st);j<f[x].size()&&f[x][j]<=r;j=found(x,j+1)){
                if(a[f[x][j]]%x==0) add(f[x][j],a[f[x][j]]/x-a[f[x][j]]),a[f[x][j]]/=x;
                if(a[f[x][j]]%x!=0) fa[x][j]=found(x,j+1);
            }
        }
        else wr(ans=query(r)-query(l-1)),puts("");
    }
    return 0;
}

// ---------- Main ---------- //

然后你就发现被卡常了

预计得分 62。

我们考虑卡常。（

把数组全部改成指针即可。（

注意细节，不要 <= 写成 <。（

会 RE 飞。（

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back
#define lb lower_bound
#define ub upper_bound

using namespace std;
typedef long long ll;

template <typename T> void rd(T &x){
    int fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(ll x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}

// ---------- IO ---------- //

const int N=5e5+5;
int n,m,a[N],cnt[N],maxn,*p[N],node[N*505],*tp=node;

ll sum[N],ans;

inline int ma(int x,int y){return x<y?y:x;}

inline void add(int x,ll k){
    while(x<=n) sum[x]+=k,x+=x&(-x);
}

inline ll query(int x){
    ll s=0;
    while(x) s+=sum[x],x^=x&(-x);
    return s;
}

// ---------- BIT ---------- //

struct DSU{
    int *fa;
    inline void init(int n){for(re i=0;i<n;++i) fa[i]=i;}
    inline int found(int x){return fa[x]==x?x:fa[x]=found(fa[x]);}
}nxt[N];

// ---------- DSU ---------- //

inline void modify(int l,int r,int x){
    l=lb(p[x],p[x]+cnt[x],l)-p[x];
    r=ub(p[x],p[x]+cnt[x],r)-p[x]-1;
    if(l>r) return ;
    for(re nw=nxt[x].found(l);nw<=r;nw=nxt[x].found(nw+1)){
        int t=p[x][nw];
        if(a[t]%x==0) add(t,a[t]/x-a[t]),a[t]/=x;
        if(nw>=r) break;
        if(a[t]%x) nxt[x].fa[nw]=nxt[x].found(nw+1);
    }
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);
    for(re i=1;i<=n;++i){
        rd(a[i]);add(i,a[i]);
        cnt[a[i]]++;maxn=ma(maxn,a[i]);
    }
    for(re i=1;i<=maxn;++i)
        for(re j=i+i;j<=maxn;j+=i) cnt[i]+=cnt[j];
    for(re i=1;i<=maxn+1;++i)
        if(cnt[i]){
            p[i]=tp;tp+=cnt[i];
            nxt[i].fa=tp;nxt[i].init(cnt[i]);
            tp+=cnt[i];cnt[i]=0;
        }
    for(re i=1;i<=n;++i){
        for(re j=1;j*j<=a[i];++j)
            if(a[i]%j==0){
                p[j][cnt[j]++]=i;
                if(j*j!=a[i]) p[a[i]/j][cnt[a[i]/j]++]=i;
            }
    }
    int op,l,r,x;
    for(re i=1;i<=m;++i){
        rd(op);rd(l);rd(r);l^=ans;r^=ans;
        if(op==1){
            rd(x);x^=ans;
            if(x==1) continue;
            modify(l,r,x);
        }
        else wr(ans=query(r)-query(l-1)),puts("");
    }
    return 0;
}

// ---------- Main ---------- //