题解：P15992 [PA 2026] 原题加强 2 / Wersja dla profesjonalistów 2

· · 题解

神秘，但是非常好玩！孩子很喜欢！

令跳跃步长为 k，起点为 s。

考虑静态问题，有观察：

考虑随机化，随机取两个数 x, y，枚举 |x - y| 的质因数，随 O(\log_2 P) 次就能以 \frac{1}{P} 的错误率找到答案。

把随机化去掉，考虑对 S 每 4 个一分组，那么对于任意 T \subseteq S，且 |T| \ge \frac{|S|}{2}，拿出一个组 A，并考察 \frac{|A \cap T| (|A \cap T| + 1)}{2}，对这个东西求和，你发现和永远不小于 \frac{S}{4}！于是对每一个组，两两作差并枚举它们的质因数，总共会贡献 \frac{3}{2}|S| \omega(n) 次，也就是最多检查 6 \omega(n) 个质数了！

考虑带修，进行人类智慧：考虑设一个阈值 \alpha = \frac{1}{3}，每次静态的一次性处理 \alpha |S| 个询问。

因为我们带修了，所以 |S'| \in [(1 - \alpha)|S|, (1 + \alpha)|S|]，然后发现 |S' \cap S| \ge (1 - \alpha) |S|。

类似上面的思路，我们按每 \frac{4}{1 - \alpha} = 6 个分一组，还是对刚才那个求和，那么 |S' \cap S| 个数最少也会有 \frac{1 - \alpha}{4}|S| 的贡献。

还是对每个组，两两作差取其质因数，总贡献是 \frac{1}{2}(\frac{4}{1 - \alpha}-1) |S|\omega(n) 次，最后大概是检查 \frac{1}{2}(\frac{4}{1 - \alpha} - 1)\frac{4}{1 - \alpha} \omega(n) = 15\omega(n) 次，完结撒花！

// Think TWICE, code ONCE
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll Read() {
    int sig = 1; ll num = 0; char c = getchar();
    while(!isdigit(c)) { if(c == '-') sig = -1; c = getchar(); }
    while(isdigit(c)) num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
    return num * sig;
}
void Write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) Write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 10000005, M = 1000005;
int n, m, cnt, p[M], c[N];
bitset<N> a, b;
int cntp, prime[N], minp[N], to[N];
set<int> st;
void Get() {
    int i, j;
    for(i = 2; i <= n; i++) {
        if(!b[i]) prime[++cntp] = i, minp[i] = i, to[i] = 1;
        for(j = 1; j <= cntp && prime[j] * i <= n; j++) {
            b[prime[j] * i] = true, minp[prime[j] * i] = prime[j];
            if(i % prime[j] == 0) { to[prime[j] * i] = to[i]; break; }
            to[prime[j] * i] = i;
        }
    }
}
int MEM[N * 6], X;
int *t[140], *ct[140];
int maxn[140], hmaxn[140];
int _plist[M * 6], plist[140], s[M];
int Add(int siz, int x, int y) {
    int i, ans = 0;
    for(i = 0; i < siz; i++) {
        int &val = t[i][x % plist[i]];
        ct[i][val]--, val += y, ct[i][val]++;
        if(ct[i][maxn[i] + 1]) {
            if(maxn[i] == hmaxn[i]) ct[i][hmaxn[i] + 2] = 0, hmaxn[i]++;
            maxn[i]++;
        }
        else if(!ct[i][maxn[i]]) maxn[i]--;
        ans = max(ans, maxn[i]);
        // for(int j = 0; j < ct[i].size(); j++) cerr << ct[i][j] << ' ';
        // cerr << endl;
    }
    return ans;
}
void Solve(int l, int r) {
    int i, j, k, cnts = 0, _cntplist = 0, siz = 0;
    for(auto v : st) s[cnts++] = v;
    for(i = 0; i < cnt; i += 6) for(j = i; j < min(cnt, i + 6); j++) for(k = j + 1; k < min(cnt, i + 6); k++) {
        int x = abs(s[j] - s[k]);
        while(x > 1) {
            if(!b[minp[x]]) b[minp[x]] = true, _plist[_cntplist++] = minp[x];
            c[minp[x]]++, x = to[x];
        }
    }
    for(i = 0; i < _cntplist; i++) {
        int v = _plist[i];
        if(c[v] >= (cnt + 5) / 6) plist[siz++] = v;
        b[v] = c[v] = 0;
    }
    // sort(plist.begin(), plist.end());
    int ans = 0; X = 0;
    for(i = 0; i < siz; i++) {
        t[i] = MEM + X, X += plist[i];
        ct[i] = MEM + X, X += cnt + r - l + 5;
        maxn[i] = hmaxn[i] = 0, ct[i][0] = ct[i][1] = 0;
        for(j = 0; j < plist[i]; j++) t[i][j] = 0;
        ct[i][0] = plist[i];
    }
    for(i = 0; i < cnt; i++) ans = Add(siz, s[i], 1);
    Write(ans), putchar('\n');
    for(i = l + 1; i <= r; i++) {
        if(a[p[i]]) cnt--, st.erase(p[i]), ans = Add(siz, p[i], -1), a[p[i]] = 0;
        else cnt++, st.emplace(p[i]), ans = Add(siz, p[i], 1), a[p[i]] = 1;
        Write(ans), putchar('\n');
    }
}
int main() {
    // freopen("F.in", "r", stdin), freopen("F.out", "w", stdout);
    int i; n = Read(), m = Read(), Get();
    for(i = 1; i <= m; i++) p[i] = Read();       
    for(i = 1; i <= m; i++) {
        if(a[p[i]]) cnt--, st.erase(p[i]), a[p[i]] = 0;
        else cnt++, st.emplace(p[i]), a[p[i]] = 1;
        if(cnt < 3) Write(cnt - (cnt == 2 && (*st.rbegin() - *st.begin()) == 1)), putchar('\n');
        else { int r = min(m, i + cnt / 3); Solve(i, r), i = r; }
    }
}