题解 P5610 【[Ynoi2013]大学】

· · 题解

首先我们观察到一个数最多被除 \log a 次

所以这又是一道花神套路题

具体说，对 \forall x，用并查集维护 a_i 中 x 的倍数，每次修改时二分找到 l 的位置，然后用并查集往后跳，如果发现除完以后已经不是 x 的倍数了就把这个点从并查集中删除（即将这个点和下一个点合并）即可。

复杂度为 O(n\sqrt a+n\log a)。

被卡常的代码：（相信凭借各位高超的卡常能力一定可以AC）

#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
struct IO_Tp {
    const static ll _I_Buffer_Size = 2 << 22;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;

    const static ll _O_Buffer_Size = 2 << 22;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res) {
        ll f=1;
        while (!isdigit(*_I_pos)&&(*_I_pos)!='-') ++_I_pos;
        if(*_I_pos=='-')f=-1,++_I_pos;
        res = *_I_pos++ - '0';
        while (isdigit(*_I_pos)) res = res * 10 + (*_I_pos++ - '0');
        res*=f;
        return *this;
    }

    IO_Tp &operator<<(ll n) {
        if(n<0)*_O_pos++='-',n=-n;
        static char _buf[10];
        char *_pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf) *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch) {
        *_O_pos++ = ch;
        return *this;
    }
} IO;

const ll N=100005,A=500005;
int n,m,a[N];
ll bit[N];
void update(int id,int x){for(;id<=n;id+=id&-id)bit[id]+=x;}
ll sum(int id){ll ret=0;for(;id;id-=id&-id)ret+=bit[id];return ret;}
vector<int>f[A],id[A];
int find(int k,int x){return x==id[k].size()||x==id[k][x]?x:id[k][x]=find(k,id[k][x]);}
int main(){
    IO>>n>>m;
    for(int i=1;i<=n;++i)IO>>a[i],update(i,a[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j*j<=a[i];++j)if(a[i]%j==0){
            f[j].push_back(i);
            id[j].push_back(id[j].size());
            if(j*j!=a[i]){
                f[a[i]/j].push_back(i);
                id[a[i]/j].push_back(id[a[i]/j].size());
            } 
        }
    for(ll lastans=0;m--;){
        int op,l,r,x;
        IO>>op;
        if(op==1){
            IO>>l>>r>>x;
            l^=lastans,r^=lastans,x^=lastans;
            if(x==1)continue;
            int L=lower_bound(f[x].begin(),f[x].end(),l)-f[x].begin();
            for(int i=find(x,L),v;i<f[x].size()&&f[x][i]<=r;i=find(x,i+1)){
                if(a[f[x][i]]%x==0)v=a[f[x][i]]/x,update(f[x][i],v-a[f[x][i]]),a[f[x][i]]=v;
                else v=1;
                id[x][i]=(v%x!=0?find(x,i+1):id[x][i]);
            }
        }else{
            IO>>l>>r;
            l^=lastans,r^=lastans;
            lastans=sum(r)-sum(l-1);
            IO<<lastans<<'\n';
        } 
    }
    return 0;
}