P5610 [Ynoi2013] 大学题解

zzx0102 · 2023-10-04 16:44:04 · 题解

谁告诉你这题不能 vector 了？

首先，一个数 a 除以一个 >1 的数，除 \log_2 a 次一定会变成 1。

考虑对每个数的倍数位置存 vector，这样每次删数遍历 vector。

于是考虑花神游历各国的套路，考虑用并查集删数。

最后，x=1 时不要执行。

上述都是废话。

卡常技巧：

快读用 getchar_unlocked，输出同理。
每个位置存 vector 用调和级数。
注意到存 vector 的因数不要用根号的筛法，直接用调和级数筛。
然后不要 #define int long long。
单点修区间和用树状数组，而非线段树。

总复杂度 \mathcal{O}(n\log n\log a)。

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define pc putchar_unlocked
int read() {
    int x = 0; char ch = gc();
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = gc();
    return x;
}
void write(long long x) {
    if(x > 9) write(x / 10);
    pc(x % 10 + '0');
}
const int N = 100010, M = 500010, K = 7e6 + 10; vector<int> nxt[M], g[M], c[M]; int q, sz[M];
int a[N]; long long tr[N], n, Q;
void init() {
    for(int i = 1; i <= q; i++) {
        for(int j = i; j <= q; j += i) {
            for(int k: c[j]) {
                g[i].push_back(k); nxt[i].push_back(sz[i]); sz[i]++;
            }
        }
        if(g[i].empty()) continue;
        for(int j = 1, siz = g[i].size(); j < siz; j++) if(g[i][j - 1] > g[i][j]) {stable_sort(g[i].begin(), g[i].end()); break;}
    }
}
int find(int f, int x) {
//  cout << nxt[f][x] << '\n';
    return nxt[f][x] == x || x >= sz[f] ? x : nxt[f][x] = find(f, nxt[f][x]);
}
void add(int x, int k) {for(; x <= n; x += x & -x) tr[x] += k;}
long long ask(int x) {long long sum = 0; for(; x; x &= x - 1) sum += tr[x]; return sum;}
void del(int x, int l, int r) {
    int u = lower_bound(g[x].begin(), g[x].end(), l) - g[x].begin();
    int siz = g[x].size();
    for(int i = find(x, u); i < siz && g[x][i] <= r; i = find(x, i + 1)) {
//      cout << i << '\n';
        if(a[g[x][i]] % x == 0) {
//          cout << g[x][i] << '\n';
            int t = a[g[x][i]] / x; add(g[x][i], t - a[g[x][i]]); a[g[x][i]] = t;
        }
        if(a[g[x][i]] % x) nxt[x][i] = i + 1;
    }
}
signed main() {
    n = read(), Q = read(); for(int i = 1; i <= n; i++) a[i] = read(), c[a[i]].push_back(i), add(i, a[i]), q = max(q, a[i]); init(); // cout << idx << '\n';
    long long lst = 0;
    while(Q--) {
        int o, x, y; o = read(), x = read(), y = read(); x ^= lst, y ^= lst;
        if(o == 1) {
            int k; k = read(); k ^= lst;
            if(k > 1 && !g[k].empty()) del(k, x, y);
        }
        else write(lst = ask(y) - ask(x - 1)), pc('\n');
    }
    return 0;
}

最大点 438ms。

P5610 [Ynoi2013] 大学 题解

上述都是废话。

P5610 [Ynoi2013] 大学题解