Loj 6723 教科书般的亵渎

Posted on | Views:

整除分块 + 树状数组.

先考虑给定一个伤害值 $d$ ,如何计算施放了多少次亵渎.

将每个随从生命值 $x$ 换成需要被攻击的次数,即 $\lfloor \frac{x-1}{d}\rfloor +1$ ,就可以把 $d$ 看作 $1$ ,即每次造成 $1$ 点伤害.

那么施放的次数就是最大的 $x$ ,使得 $1,2,3,\dots, x$ 作为生命值在随从中都出现过,再加上 $1$ .

考虑对于每个 $d$ 都直接维护出答案,询问时利用树状数组查询 $[L,R]$ 内的区间和.

每加入一个数 $x$ 的时候,对它整除分块,它对一段区间 $[L,R]$ 的贡献都是加入了一个数 $k$ .

对每个 $k$ 用 set 维护它在哪些位置是作为最大的 $x$ ,将 $[L,R]$ 内 $k-1$ 作为最大的 $x$ 的位置全部更新一遍.答案.

由于只有增加数字的操作,所以对于每个位置 $d$ ,更新次数不会超过 $\frac {n}{d}$ .

时间复杂度 $O(n\log^2n+n\sqrt n)$ .

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//%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)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1e5 + 10;
int n, m, bucket[N];
struct FenwickTree
{
	int lowbit(int x)
	{
		return x & (-x);
	}
	int bit[N];
	int add(int x, int c)
	{
		for (; x <= n; x += lowbit(x))
			bit[x] += c;
	}
	int sum(int x)
	{
		int s = 0;
		for (; x; x -= lowbit(x))
			s += bit[x];
		return s;
	}
	int query(int l, int r)
	{
		return sum(r) - sum(l - 1);
	}
} Buc, Ans;
int ans[N];
set<int> st[N];
int solve(int d)
{
	Ans.add(d, -ans[d]);
	while ("WLLAKIOI")
	{
		int l = d * ans[d] + 1, r = l + d - 1;
		l = min(l, n + 1), r = min(r, n);
		int cnt = Buc.query(l, r);
		if (cnt)
			++ans[d];
		else
			break;
	}
	Ans.add(d, ans[d]);
	st[ans[d]].insert(d);
}
void upd(int l, int r, int k)
{
	auto first = st[k].lower_bound(l);
	auto last = st[k].upper_bound(r);
	for (auto it = first; it != last; it = st[k].erase(it))
		solve(*it);
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; ++i)
		st[0].insert(i);
	while (m--)
	{
		int op = read();
		if (op == 1)
		{
			int x = read() - 1;
			if (bucket[x])
				continue;
			bucket[x] = 1;
			Buc.add(x + 1, 1);
			for (int l = 1, r; l <= x; l = r + 1)
			{
				int k = x / l;
				r = x / k;
				upd(l, r, k);
			}
			upd(x + 1, n, 0);
		}
		else
		{
			int L = read(), R = read();
			write(Ans.query(L, R) + R - L + 1, '\n');
		}
	}
	return 0;
}