bzoj 4320 ShangHai2006 Homework

根号分治 + 根号平衡.

记 $K=3\times 10^5$ ,对于 $\le \sqrt K$ 的模数 $Y$ ,每次加入一个 $X$ 的时候都暴力更新一下它们的答案,就可以 $O(1)$ 回答.

这部分的时间复杂度是 $O(n\sqrt K)$ .

对于 $>\sqrt K$ 的模数 $Y$ ,可知 $\lfloor \frac X Y\rfloor \le \sqrt K$ ,而 $X\bmod Y=X-\lfloor \frac X Y\rfloor\cdot Y$ .

于是每次询问时,可以枚举 $\lfloor \frac X Y\rfloor$ 的值,询问在某段区间 $[L,R]$ 中出现过的最小的 $X$ .

归纳一下,我们需要维护一个集合,要插入 $O(n)$ 个数,查询 $O(n\sqrt K)$ 次某个数的后继.

直接用 set 维护会多一个 log, 考虑根号平衡,实现 $O(\sqrt K)$ 插入, $O(1)$ 询问后继.

对值域分块,对每个位置维护块内的后继,对每个块维护该块右端点的后继即可.

于是这部分的时间复杂度也是 $O(n\sqrt K)$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out = 0, fh = 1;
char jp = getchar();
while ((jp > '9' || jp < '0') && jp != '-')
jp = getchar();
if (jp == '-')
fh = -1, jp = getchar();
while (jp >= '0' && jp <= '9')
out = out * 10 + jp - '0', jp = getchar();
return out * fh;
}
void print(int x)
{
if (x >= 10)
print(x / 10);
putchar('0' + x % 10);
}
void write(int x, char c)
{
print(x);
putchar(c);
}
const int N = 3e5 + 10, S = 550;
int n, m, B, bel[N], lp[S], rp[S], suc[S], inner_suc[N], ans[S];
void upd(int x)
{
for (int y = 1; y <= B; ++y)
ans[y] = min(ans[y], x % y);
for (int i = 1; i < bel[x]; ++i)
suc[i] = min(suc[i], x);
for (int i = lp[bel[x]]; i <= x; ++i)
inner_suc[i] = min(inner_suc[i], x);
}
int query(int y)
{
if (y <= B)
return ans[y];
int res = n + 1;
for (int k = 0; y * k <= n; ++k)
{
int L = y * k, R = y * (k + 1) - 1;
L = max(L, 1);
R = min(R, n);
int x = min(suc[bel[L]], inner_suc[L]);
if (x <= R)
res = min(res, x % y);
}
return res;
}
int main()
{
n = 300000, m = read();
B = sqrt(n);
for (int i = 1; i <= n; ++i)
{
bel[i] = (i - 1) / B + 1;
lp[bel[i]] = (bel[i] - 1) * B + 1;
rp[bel[i]] = bel[i] * B;
suc[bel[i]] = n + 1;
inner_suc[i] = n + 1;
}
rp[bel[n]] = n;
for (int i = 1; i <= B; ++i)
ans[i] = n + 1;
for (int i = 1; i <= m; ++i)
{
char buf[10];
scanf("%s", buf);
if (buf[0] == 'A')
upd(read());
else
write(query(read()), '\n');
}
return 0;
}