题解：P12128 [蓝桥杯 2024 省 B 第二场] 质数变革

· · 题解

更好的阅读体验

很显然，这道题根本不需要根号分治，直接离线存下来一起修改就行。

我就来讲一下这道题为什么不用根号分治复杂度是对的吧。

如何暴力

显然可以把每次修改看做排名 +x 或 -x 的操作，又因为这些修改的方式只有 n 种可能，我们可以用一个数组 c 存下所有 k 的修改，最后再一次性统计答案。

写成代码是这样的：

记录修改：

for(int i = 1, x, k, op; i <= q; i ++) {
    in(op, k, x);
    x = (op == 1 ? -x : x);
    c[k] += x;
}

最后统计：

for(int i = 1; i <= n; i ++) 
    if(c[i]) for(int j = i; j <= n; j += i) sm[j] += c[i];

这样写复杂度是对的，而且是很好的复杂度，大概是 O(n\ln n)。

为什么？

考虑对于一个数字 i，它导致第二层循环跑几次？显然是 \lfloor \frac ni \rfloor 次，列成算式，总次数就是 \sum _{i = 1} ^{n} \lfloor \frac ni \rfloor 次，感性证明一下，原式（往坏里想，也就是去掉向下取整）可以变成 n\sum _{i = 1} ^{n} \frac 1i，后面的东西是调和级数，是 \ln n 级别的，所以复杂度是上面的东西。

然后我们还可以发现对于一个质数，它的排名变化了就是变化了，而如果是一个合数，如果变化它的排名就只是把它变成相邻的质数，大概可以理解成如果第一次修改一个合数是让它的排名加一，就相当于是浪费了一次排名加一的机会让这个数变成了加一的那个质数，所以我们还要记录每个数第一次修改的方向。在记录修改的部分改改就行。

写成代码是这样的：

for(int i = 1, x, k, op; i <= q; i ++) {
    in(op, k, x);
    x = (op == 1 ? -x : x);
    c[k] += x;
    if(!vis[k]) 
        for(int i = k; i <= n; i += k) !fis[i] ? fis[i] = op : 0; 
    vis[k] = 1;
}

发现每一个 k 都只对它出现的第一次记录，复杂度仍如上所言，是 O(n\ln n)。

再然后我们有了如上的东西，就可以快速的再写一个线性筛筛素数，在里面记录每一个数离它最近的两个质数。

再然后分讨一下，就可以输出答案了。

总复杂度 O(V + n\ln n)。

// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
using namespace std;

#define getc() getchar_unlocked()
#define putc(a) putchar_unlocked(a)
#define en_ putc('\n')
#define e_ putc(' ')

using pii = pair<int, int>;

template<class T> inline T in() { 
    T n = 0; char p = getc();
    while(p < '-') p = getc();
    bool f = p == '-' ? p = getc() : 0;
    do n = n * 10 + (p ^ 48), p = getc();
    while(isdigit(p));
    return f ? -n : n;
}
template<class T> inline T in(T &a) { return a = in<T>(); }
template<class T, class ... Args> inline void in(T &t, Args&... args) { in(t), in(args...); }

template<class T> inline void out(T n) {
    if(n < 0) putc('-'), n = -n;
    if(n > 9) out(n / 10);
    putc(n % 10 + '0');
}

template<class T1, class T2> T1 max(T1 a, T2 b) { return a > b ? a : a = b;}
template<class T1, class T2> T1 min(T1 a, T2 b) { return a < b ? a : a = b;}

constexpr int N = 2e5 + 10;

int c[N];
bool vis[N];
int sm[N];

int n, q;

int a[N], cnp, l[1000010], r[1000010];

int pri[N];
bool is[1000010]; // 表示不是质数

inline void line() { // 线性筛板子
    for(int i = 2; i <= 1000000; i ++) {
        if(!is[i]) pri[++ cnp] = i;
        l[i] = cnp, r[i] = cnp + 1; // 记录第一个大于或小于等于的质数下标
        for(int j = 1; i * pri[j] <= 1000000 and j <= cnp; j ++) { 
            is[pri[j] * i] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

int fis[N];

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in.ru", "r", stdin);
        freopen("out.ru", "w", stdout);
    #endif

    in(n, q);

    for(int i = 1; i <= n; i ++) in(a[i]);

    for(int i = 1, x, k, op; i <= q; i ++) {
        in(op, k, x);
        x = (op == 1 ? -x : x);
        c[k] += x;
        if(!vis[k]) // 记录第一次
            for(int i = k; i <= n; i += k) !fis[i] ? fis[i] = op : 0; 
        vis[k] = 1;
    }

    for(int i = 1; i <= n; i ++) 
        if(c[i]) for(int j = i; j <= n; j += i) sm[j] += c[i]; // 求出总排名变换数

    line();
    is[1] = 1;  // 注意这三行特例
    r[1] = 1;
    for(int i = 1000000; !r[i]; i --) r[i] = 123123123;

    for(int i = 1; i <= n; i ++) {
        if(fis[i]) {
            int t;
            if(is[a[i]]) {
                if(fis[i] == 1) t = sm[i] + 1 + l[a[i]];
                if(fis[i] == 2) t = sm[i] - 1 + r[a[i]];
            }
            else t = sm[i] + l[a[i]];

            if(t <= 0) out(0);
            else if(t > cnp) out(1);
            else out(pri[t]);
        }
        else out(a[i]); 
        e_;
    }
}   
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~