yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P5610 [Ynoi2013] 大学

发表于 分类于

P5610 [Ynoi2013] 大学

卡了一晚上常数才卡过去。

题面

题目链接

解法

一共只有 $O(n \log a)$ 次有效的除法操作。

对于每个因数 $i$，维护其倍数的下标集合 $S_i$，即 $\forall j \in S_i, \, i \mid a_j$。

为了快速找到需要操作的数，不妨对于集合中每个数维护下一个还能进行操作的数，可以用并查集维护。

于是这题的基本做法就形成了：首先预处理出每个因数的集合 $S_i$（需要用调和级数的方法扫出来），建立并查集，对修改操作暴力跳并查集，单点修改区间查询直接上树状数组。时间复杂度 $O(n \log a \log n + m d(a) \alpha(n))$。

卡常

首先要注意对于 $x=1$ 直接跳过，不然整个复杂度都假掉了。然后你获得了 $26pts$ 的好成绩。

然后我们发现用 vector 储存每个数出现的位置和并查集非常浪费而且常数极大，所以改为手写内存池+链式前向星，开大概 $2.5\times 10^7$ 就够了。然后你获得了 $46pts$ 的好成绩。

接下来发现如果用链式前向星就会增加很多不连续的内存访问。所以先将 $a$ 数组复制并排序，这样每个数的出现位置就是连续的了，就不需要链式前向星再储存每个数的出现位置了。然后你获得了 $48pts$ 的好成绩。

考虑此算法的复杂度瓶颈在何处，自然是每次访问并查集都需要进行的取模操作，以此判断是否还能操作。而取模操作很慢。这时我突发奇想把判断 a[i] % x == 0 换成 a[i] >= x && a[i] % x == 0，a[i] % x != 0 换成 a[i] < x || a[i] % x != 0，然后就获得了 $98pts$ 的好成绩。

最后的 $2pts$，如果已经判断过这个数不能操作了，就修改并查集。也就是说：

1
2
3
4
if (a[k] >= x && a[k] % x == 0) {
    int t = a[k]; a[k] /= x; add(k, a[k] - t);
    (a[k] < x || a[k] % x != 0) && (fa[x][p] = getfa(x, p + 1));
}

后面加上

1
2
3
else {
    fa[x][p] = getfa(x, p + 1);
}

于是就快乐地 AC 啦！

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * @file:           P5610.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P5610
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
namespace fastio {
const int MAXBUF = 1 << 20;
char buf[MAXBUF], *p1 = buf, *p2 = buf;
char pbuf[MAXBUF], *pp = pbuf;
inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), *p1++; }
inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
};  // namespace fastio
using namespace fastio;
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getc(); double tmp = 1;
    for (; !isdigit(ch); ch = getc()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putc('-'), x = -x;
    if (x > 9) write(x / 10);
    putc((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
const int MAXN = 1e5 + 10;
const int MAXM = 5e5 + 10;
const int MAXP = 2.5e7 + 10;
const int INF = 0x3f3f3f3f;
int n, m, q, a[MAXN], b[MAXN], cnt[MAXM], fr[MAXM], bk[MAXM], num[MAXM];
int pool_id[MAXP], pool_fa[MAXP], *cur_id, *cur_fa, *id[MAXM], *fa[MAXM];
bool vis[MAXM]; ll c[MAXN];
inline int getfa(int k, int x) { return !fa[k][x] ? x : fa[k][x] = getfa(k, fa[k][x]); }
inline void add(int i, int v) { for (; i <= n; i += (i & -i)) c[i] += v; }
inline ll sum(int i) { ll s = 0; for (; i; i -= (i & -i)) s += c[i]; return s; }
bool m_ed;
signed main() {
    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1048576);
    read(n), read(q), m = 5e5;
    for (int i = 1; i <= n; ++i) read(a[i]), b[i] = i, ++num[a[i]];
    sort(b + 1, b + n + 1, [&](int x, int y) { return a[x] < a[y] || (a[x] == a[y] && x < y); });
    for (int i = 1; i <= n; ++i) (a[b[i]] != a[b[i - 1]]) && (fr[a[b[i]]] = i), bk[a[b[i]]] = i;
    cur_id = pool_id, cur_fa = pool_fa;
    for (int i = 1; i <= n; ++i) add(i, a[i]);
    ll ans = 0;
    while (q--) {
        int op; ll l, r, x;
        if (read(op) == 1) {
            read(l), read(r), read(x);
            l ^= ans, r ^= ans, x ^= ans;
            if (x == 1) continue;
            if (!vis[x]) {
                bool sorted = 1;
                id[x] = cur_id, fa[x] = cur_fa;
                for (int j = x; j <= m; j += x)
                    if (num[j]) {
                        copy(b + fr[j], b + bk[j] + 1, id[x] + cnt[x] + 1);
                        if (cnt[x] && id[x][cnt[x]] > id[x][cnt[x] + 1]) sorted = 0;
                        cnt[x] += num[j];
                    }
                id[x][cnt[x] + 1] = n + 1;
                if (!sorted) sort(id[x] + 1, id[x] + cnt[x] + 1);
                cur_id += cnt[x] + 1, cur_fa += cnt[x] + 1, vis[x] = 1;
            }
            if (!cnt[x]) continue;
            int p = lower_bound(id[x] + 1, id[x] + cnt[x] + 2, l) - id[x];
            for (; id[x][p = getfa(x, p)] <= r; ++p) {
                int k = id[x][p];
                if (a[k] >= x && a[k] % x == 0) {
                    int t = a[k]; a[k] /= x; add(k, a[k] - t);
                    (a[k] < x || a[k] % x != 0) && (fa[x][p] = getfa(x, p + 1));
                } else {
                    fa[x][p] = getfa(x, p + 1);
                }
            }
        } else {
            read(l), read(r);
            l ^= ans, r ^= ans;
            ans = sum(r) - sum(l - 1);
            write(ans), putc('\n');
        }
    }
    return print_final(), 0;
}