LOJ6499 - 「雅礼集训 2018 Day2」颜色

并不会正解,此处讲一个可以过此题(而且跑的飞快)的做法。

考虑直接分块,如果对每个块开个 bitset ,这样合并(如果觉得解释的不是很清楚可以点击阅读全文看完整代码 qwq:

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(int l, int r) {
if (bln[l] == bln[r]) {
for (register int i = l; i <= r; i++)
ans.set(a[i]);
} else {
for (register int i = l; i < fst[bln[l] + 1]; i++)
ans.set(a[i]);
for (register int i = fst[bln[r]]; i <= r; i++)
ans.set(a[i]);
for (register int i = bln[l] + 1; i <= bln[r] - 1; i++)
ans |= f[i];
}
}

如果块大小为 $\sqrt n$ ,那么实际上的复杂度是 $\frac {n ^ 2 \sqrt n}{64} $,复杂度其实和暴力差不多。

Dilute: 我™写了个(假)正解分还和暴力一样。

在不会正解的情况下,显然只能考虑在优化分块上做文章。同学基本都是调整块大小为 $7000$ 左右 + 奇技淫巧的卡常通过,此处讲一个不太一样的做法:

考虑使我们的复杂度变的不正确的部分:

1
2
for (register int i = bln[l] + 1; i <= bln[r] - 1; i++)
ans |= f[i];

由于最多会访问到 $\sqrt n$ 个块,复杂度就不能保证。考虑处理出一个 $pre[i][j]$ 数组,表示std::bitset <N> f[i]std::bitset <N> f[i + j - 1] 的异或和。由于空间限制只有 8MB ,我们只能开约 $480$ 个 std::bitset <N> ,就分成 80 个块,预处理的 $j$ 从 $1$ 到 $8$ 即可。

我们的 txc 哥哥还给了一个非常优秀的常数优化:如果一个数在整个序列里只出现了一次,那么他只要在区间内,对答案的贡献肯定为 $1$(不会因为出现和自己值相同的数而减少)。前缀和处理即可,理论可以少掉一半的常数,Orz.

代码:

最优解被 T 老师抢了也是很快乐呢 qwq。

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
// =================================
// author: memset0
// date: 2018.12.25 12:02:14
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define rep(i, l, r) for (register int i = l; i <= r; i++)
namespace ringo {
typedef long long ll;
typedef unsigned long long ull;
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void maxd(T &a, T b) { if (b > a) a = b; }
template <class T> inline void mind(T &a, T b) { if (b < a) a = b; }
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline T abs(const T &a) { if (a < 0) return -a; return a; }

const int N = 1e5 + 10, M = 59, L = 8;
int n, m, l, r, p, sqn, cnt, p_flag, lastans;
int a[N], bln[N], fst[M + 10], id[M + 10][M + 10];
std::bitset <N> ans, f[478];

void main() {
read(n), read(m), read(p_flag), sqn = n / M + 1;
for (int i = 1; i <= n; i++) read(a[i]);
for (int i = 1; i <= n; i++) {
bln[i] = (i - 1) / sqn + 1;
if (!fst[bln[i]]) fst[bln[i]] = i;
}
fst[bln[n] + 1] = n + 1;
for (int i = 1; i <= bln[n]; i++) {
for (int j = i; j < i + L && j <= bln[n]; j++)
id[i][j] = cnt++;
for (int j = fst[i]; j < fst[i + 1]; j++)
f[id[i][i]].set(a[j]);
}
for (int i = 1; i <= bln[n]; i++)
for (int j = i + 1; j < i + L && j <= bln[n]; j++)
f[id[i][j]] = f[id[i][j - 1]] | f[id[j][j]];
for (int i = 1; i <= m; i++) {
ans.reset(), read(p);
for (int j = 1; j <= p; j++) {
read(l), read(r);
if (p_flag && i != 1) {
l = (l ^ lastans) % n + 1;
r = (r ^ lastans) % n + 1;
if (l > r) std::swap(l, r);
}
if (bln[l] == bln[r]) {
for (int i = l; i <= r; i++) ans.set(a[i]);
} else {
for (int i = l; i < fst[bln[l] + 1]; i++) ans.set(a[i]);
for (int i = fst[bln[r]]; i <= r; i++) ans.set(a[i]);
int bl = bln[l] + 1, br = bln[r] - 1;
while (bl + L - 1 <= br) ans |= f[id[bl][bl + L - 1]], bl += L;
if (bl <= br) ans |= f[id[bl][br]];
}
}
print(lastans = ans.count(), '\n');
}
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×