题解 P5610 【[Ynoi2013]大学】

Sol1 · 2020-05-02 21:39:58 · 题解

update：时限缩短了之后进行了一波极限卡常，现在又能过了。

如果题解界面的 latex 坏掉了可以点进博客查看~

一个很神奇的 trick，写篇题解总结一下。

首先我们发现一个性质，就是每一个数最多被除 O\left(\log n\right) 次就会变成 1，所以只要能够做到只处理需要修改的位置的修改就可以做到一个正确的复杂度。

所以这个复杂度瓶颈实际上是在于如何快速找到需要修改的位置。

我们发现每一个数的约数个数大约是 O(\sqrt[3] a) 的，所以我们对于每一个数 i 用一个数据结构来维护所有 i 的倍数。

我们来看需要支持什么操作：

• 查询一个数的值；
• 计算 \text{lower\_bound}；
• 删除；

你当然可以用平衡树，但是太慢了。

我们考虑对每一个位置维护一个指针指向它之后的第一个没有被删除的元素，初始的时候显然都指向自己。

如果我们要删除第 i 个元素，那么它的指针的新位置肯定是 i+1 的指针指向的位置（如果是最后一个元素那么就是空）；这个可以感性理解一下。

查询和 \text{lower\_bound} 的时候就直接访问指针就好。

显然我们可以用一个并查集来维护这些指针，这样上述三个操作都能做到 O(\alpha(n))\approx O(1)。

这样因为上述操作总共最多进行 O(n\log n) 次，所以这一部分的复杂度就是 O(n\log n)，同时并查集的常数也很小。

那么这道题就做完了~

然后你自信满满地写了一遍交上去发现全 T 一分没有……

那么就开始优化！

\text{Step 1}

你发现暴力分解约数是 O(n\sqrt a) 而非 O(n\sqrt [3] a)，会导致复杂度为 O(n\sqrt a+n\log n)，于是改为筛子预处理因数。

复杂度下降至 O(n\sqrt[3]a+a\log a+n\log n)。

\text{Step 2}

预处理因数时，不要用 vector 保存因数，自己写一个邻接表。

\text{Step 3}

发现每一个位置的下标数组和并查集数组的大小是固定的。

所以保存下标和并查集的时候不需要使用 vector，可以自己开一个内存池，用指针来模拟数组。

\text{Step 4}

发现每一个位置的下标数组和并查集数组的大小是可以快速求出来的，所以可以直接求出来，少遍历一遍链表，就能少一大堆 Cache Miss。

\text{Step 5}

二分内存池的大小，开太大会耗费时间导致 TLE，开小了会 RE，开得合适就可以 AC。

我二分到 2.5\times 10^7 就 AC 了。

最终时间复杂度 O(n\sqrt[3]a+a\log a+n\log n)，空间复杂度 O(n\sqrt[3]a)。

内存池的写法参考代码：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline long long qread() {
    register char c = getchar();
    register long long x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline long long Abs(const long long& x) {return (x > 0 ? x : -x);}
inline long long Max(const long long& x, const long long& y) {return (x > y ? x : y);}
inline long long Min(const long long& x, const long long& y) {return (x < y ? x : y);}

int a[100005], n, m;
long long c[100005];
int poolvc[25000005], poolfa[25000005], cntvc[500005], cntfa[500005], cnta[500005];
int *vc[500005], *fa[500005];
struct Node {
    int val, nxt;
    Node() {
        nxt = -1;
    }
};
int hd[500005], pnt;
Node nd[10000005];

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

inline void Update(int i, long long x) {
    for (register int j = i;j <= n;j += Lowbit(j)) c[j] += x;
}

inline long long Query(int i) {
    register long long ans = 0;
    for (register int j = i;j >= 1;j -= Lowbit(j)) ans += c[j];
    return ans;
}

inline void Add(int x, int v) {
    nd[++pnt].val = v;
    nd[pnt].nxt = hd[x];
    hd[x] = pnt;
}

inline void Read() {
    n = qread(); m = qread();
    for (register int i = 1;i <= n;i++) Update(i, a[i] = qread());
}

inline void Prefix() {
    for (register int i = 1;i <= n;i++) cnta[a[i]]++;
    memset(hd, -1, sizeof(hd));
    register int maxd = 0;
    for (register int i = 1;i <= 500000;i++) {
        for (register int j = i;j <= 500000;j += i) {
            Add(j, i);
            cntvc[i] += cnta[j];
            cntfa[i] += cnta[j];
        }
        maxd = Max(maxd, cntvc[i]);
    }
    int vcAllocTop = 0, faAllocTop = 0;
    for (register int i = 1;i <= 500000;i++) {
        vc[i] = poolvc + vcAllocTop;
        fa[i] = poolfa + faAllocTop;
        vcAllocTop += cntvc[i] + 3;
        faAllocTop += cntfa[i] + 3;
    }
    memset(cntvc, 0, sizeof(cntvc));
    memset(cntfa, 0, sizeof(cntfa));
    for (register int i = 1;i <= n;i++) {
        for (register int j = hd[a[i]];~j;j = nd[j].nxt) {
            vc[nd[j].val][cntvc[nd[j].val]] = i;
            fa[nd[j].val][cntfa[nd[j].val]] = cntfa[nd[j].val];
            cntvc[nd[j].val]++;
            cntfa[nd[j].val]++;
            //vc[nd[j].val].push_back(i);
            //fa[nd[j].val].push_back(fa[nd[j].val].size());
        }
    }
}

inline int GetRoot(int i, int v) {
    if (v == cntfa[i] || v == fa[i][v]) return v;
    return fa[i][v] = GetRoot(i, fa[i][v]);
}

inline void Modify(int l, int r, int x) {
    register int pnt = GetRoot(x, lower_bound(vc[x], vc[x] + cntvc[x], l) - vc[x]);
    while (pnt < cntvc[x] && vc[x][pnt] <= r) {
        if (a[vc[x][pnt]] % x == 0) {
            Update(vc[x][pnt], a[vc[x][pnt]] / x - a[vc[x][pnt]]);
            a[vc[x][pnt]] /= x;
        }
        if (a[vc[x][pnt]] % x) fa[x][pnt] = pnt + 1;
        pnt = GetRoot(x, pnt + 1);
    }
}

inline void Solve() {
    register long long ans = 0;
    while (m--) {
        register long long opt = qread(), l = qread() ^ ans, r = qread() ^ ans;
        if (opt == 1) {
            register long long x = qread() ^ ans;
            if (x == 1) continue;
            Modify(l, r, x);
        } else {
            ans = Query(r) - Query(l - 1);
            printf("%lld\n", ans);
        }
    }
}

int main() {
    Read();
    Prefix();
    Solve();
    #ifndef ONLINE_JUDGE
    while (1);
    #endif
    return 0;
}