P5610 [Ynoi2013] 大学

谁说平衡树过不了。

思路

思路就简单说了，主要讲一下卡常技巧。

$5 \times 10^5$ 范围内的数约数最多有 $200$ 个约数。于是考虑用平衡树维护。

在 $a_i$ 所有约数所对应的平衡树中插入一个 $i$。然后在 $i$ 这个平衡树中，将 $[l,r]$ 区间 split 出来，就得到了我们需要的这个子树，同时筛掉 $k \nmid a_i$ 的元素。

考虑用树状数组统计答案。直接在 DFS 平衡树的时候，修改答案即可。

接下来是一些卡常技巧。

1. 处理约数不要用 $\Theta(n\sqrt{n})$ 的算法，用埃筛的方式 $\Theta(n \ln n)$ 的算法代替。

2. 因为我们需要保证建树的时候传进去的数值是有序的，否则建树的时候就需要 merge 复杂度是 $\Theta(n \log n)$ 的。所以我们将每一个数的约数都加进一个 vector 里面，然后按照 $1 \sim n$ 的顺序将 $i$ 加入到 $a_i$ 所对应的平衡树里面。同时埃筛的时候只需要处理在数组的元素。

3. 平衡树不要废节点回收，空间没什么优化，时间会慢很多。

4. 平衡树不要把随机的权值丢到结构体里面，在 merge 函数里面随机即可。

Code

#include <bits/stdc++.h>
#define re register
#define ll long long

using namespace std;

mt19937 rnd(random_device{}());
const int N = 1e5 + 10,M = 5e5 + 10,K = 3e7 + 10;
int n,q,rt[M]; ll lst;
int num,arr[N],tmp[N];
vector<int> p[M],v[M];
bool vis[M];

inline int read(){
    int r = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r;
}

struct BIT{
    #define lowbit(x) (x & -x)

    ll tr[N];

    inline void modify(int x,int k){
        for (re int i = x;i <= n;i += lowbit(i)) tr[i] += k;
    }

    inline ll query(int x){
        ll res = 0;
        for (re int i = x;i;i -= lowbit(i)) res += tr[i];
        return res;
    }

    #undef lowbit
}BT;

struct FHQ{
    #define ls(u) (tr[u].l)
    #define rs(u) (tr[u].r)

    int idx;

    struct node{
        int l,r,val;
    }tr[K];

    inline int newnode(int k){
        tr[++idx] = {0,0,k};
        return idx;
    }

    inline void split(int u,int k,int &x,int &y){
        if (!u) return x = y = 0,void();
        if (tr[u].val <= k){
            x = u; split(rs(u),k,rs(u),y);
        }
        else{
            y = u; split(ls(u),k,x,ls(y));
        }
    }

    inline int merge(int x,int y){
        if (!x || !y) return x | y;
        if (rnd() < rnd()) return rs(x) = merge(rs(x),y),x;
        else return ls(y) = merge(x,ls(y)),y;
    }

    inline int build(int l,int r){
        if (l > r) return 0;
        int mid = l + r >> 1;
        int u = newnode(tmp[mid]);
        tr[u].l = build(l,mid - 1); tr[u].r = build(mid + 1,r);
        return u;
    }

    inline void dfs(int u,int k){
        if (ls(u)) dfs(ls(u),k);
        if (u == ls(u) || u == rs(u)) exit(0);
        if (arr[tr[u].val] % k == 0){
            BT.modify(tr[u].val,-arr[tr[u].val]);
            BT.modify(tr[u].val,arr[tr[u].val] /= k);
            if (arr[tr[u].val] % k == 0) tmp[++num] = tr[u].val;
        }
        if (rs(u)) dfs(rs(u),k);
    }

    inline void del(int l,int r,int k){
        int x,y,z;
        split(rt[k],r,x,y); split(x,l - 1,x,z);
        num = 0;
        if (z) dfs(z,k);
        rt[k] = merge(merge(x,build(1,num)),y);
    }

    #undef ls
    #undef rs
}FT;

signed main(){
    n = read(),q = read();
    for (re int i = 1;i <= n;i++){
        vis[arr[i] = read()] = true;
        BT.modify(i,arr[i]);
    }
    for (re int i = 2;i <= 5e5;i++){
        for (re int j = i;j <= 5e5;j += i){
            if (vis[j]) p[j].emplace_back(i);
        }
    }
    for (re int i = 1;i <= n;i++){
        for (auto x:p[arr[i]]) v[x].emplace_back(i);
    }
    for (re int i = 2;i <= 5e5;i++){
        num = 0;
        for (auto x:v[i]) tmp[++num] = x;
        rt[i] = FT.build(1,num);
    }
    while (q--){
        int op,l,r; op = read(),l = read() ^ lst,r = read() ^ lst;
        if (op == 1){
            int k; k = read() ^ lst;
            if (k > 1) FT.del(l,r,k);
        }
        else printf("%lld\n",lst = (BT.query(r) - BT.query(l - 1)));
    }
    return 0;
}