bzoj 4320 ShangHai2006 Homework

Posted on | Views:

根号分治 + 根号平衡.

记 $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;
}