E. Level Up
Monocarp is playing a computer game. He starts the game being level $1$. He is about to fight $n$ monsters, in order from $1$ to $n$. The level of the $i$-th monster is $a_i$.
For each monster in the given order, Monocarp's encounter goes as follows:
- if Monocarp's level is strictly higher than the monster's level, the monster flees (runs away);
- otherwise, Monocarp fights the monster.
After every $k$-th fight with a monster (fleeing monsters do not count), Monocarp's level increases by $1$. So, his level becomes $2$ after $k$ monsters he fights, $3$ after $2k$ monsters, $4$ after $3k$ monsters, and so on.
You need to process $q$ queries of the following form:
- $i~x$: will Monocarp fight the $i$-th monster (or will this monster flee) if the parameter $k$ is equal to $x$?
Input
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of monsters and the number of queries.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the levels of the monsters.
In the $j$-th of the following $q$ lines, two integers $i$ and $x$ ($1 \le i, x \le n$) — the index of the monster and the number of fights required for a level up in the $j$-th query.
Output
For each query, output "YES", if Monocarp will fight the $i$-th monster in this query, and "NO", if the $i$-th monster flees.
Examples
Input
4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4Output
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YESInput
7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1Output
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
解题思路
一开始写了个可持久化线段树的做法，结果赛时 T 麻了。
由于 $\sum\limits_{i=1}^{n}{\frac{n}{i}} \approx n \log{n}$，对询问按照 $k$ 值分类进行离线处理。枚举每个 $k \, (1 \leq k \leq n)$，当 $k$ 固定后，显然最多会提升 $\left\lfloor \frac{n}{k} \right\rfloor$ 个等级，我们把每个等级对应的区间 $[l,r]$ 找出来（在该区间内恰好击败 $k$ 个怪物），对于下标 $i$ 在该区间的询问直接判断 $a_i$ 是否大于等于为当前的等级即可。
假设当前的等级为 $\text{rk}$，对应的区间的左端点为 $l$，如何快速找到右端点 $r$，使得恰好击败第 $r$ 个怪兽后升级？本质就是找到使得 $a_l \sim a_r$ 中恰好有 $k$ 个 $a_i \geq \text{rk}$ 的最小的 $r$。显然可以二分出 $r$，对于二分点 $m$ 就是查询区间 $[l, m]$ 内大于等于 $\text{rk}$ 的元素数量。在不涉及修改的情况下，查询任意区间某个范围内的元素数量可以用可持久化线段树来实现。
上述做法的时间复杂度是 $O\left(n \log^3{n}\right)$，如果直接实现的话大概率会 Time limit exceeded on test 51。本质就是常数太大了，对于某个 $k$ 其计算量大概为 $O\left(\frac{n}{k} \log^2{n}\right)$ 级别，直接暴力做的话为 $O(n)$。而暴力更快的情况是 $n < \frac{n}{k} \log^2{n} \Rightarrow k < \log^2{n}$，即当 $k < \log^2{n}$ 时还不如直接暴力来得快。所以需要在实现时设置一个阈值 $M$，当 $k < M$ 时直接跑暴力找右端点 $r$；当 $k \geq M$ 时则执行上述做法。这里的 $M$ 设成 $\log^2{n}$ 或 $\sqrt{n}$ 都可以。
AC 代码如下，时间复杂度为 $O\left(q\log{q} + n \log^3{n}\right)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, M = 450;
int a[N];
vector<array<int, 2>> q[N];
bool ans[N];
struct Node {
int l, r, s;
}tr[N * 20];
int root[N], idx;
int modify(int u, int l, int r, int x) {
int v = ++idx;
tr[v] = tr[u];
if (l == r) {
tr[v].s++;
}
else {
int mid = l + r >> 1;
if (x <= mid) tr[v].l = modify(tr[u].l, l, mid, x);
else tr[v].r = modify(tr[u].r, mid + 1, r, x);
tr[v].s = tr[tr[v].l].s + tr[tr[v].r].s;
}
return v;
}
int query(int u, int v, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) return tr[u].s - tr[v].s;
int mid = l + r >> 1;
if (qr <= mid) return query(tr[u].l, tr[v].l, l, mid, ql, qr);
if (ql >= mid + 1) return query(tr[u].r, tr[v].r, mid + 1, r, ql, qr);
return query(tr[u].l, tr[v].l, l, mid, ql, qr) + query(tr[u].r, tr[v].r, mid + 1, r, ql, qr);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int mx = *max_element(a + 1, a + n + 1);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
q[y].push_back({x, i});
}
for (int i = 1; i <= n; i++) {
root[i] = modify(root[i - 1], 1, mx, a[i]);
}
for (int i = 1; i <= n; i++) {
sort(q[i].begin(), q[i].end(), greater<array<int, 2>>());
for (int j = 1, k = 1; j <= n; j++, k++) {
if (q[i].empty() || k > mx) break;
if (i < M) {
int c = 0;
while (j <= n && c < i) {
c += a[j++] >= k;
}
j--;
}
else {
int l = j, r = n;
while (l < r) {
int mid = l + r >> 1;
if (query(root[mid], root[j - 1], 1, mx, k, mx) >= i) r = mid;
else l = mid + 1;
}
j = l;
}
while (!q[i].empty() && q[i].back()[0] <= j) {
ans[q[i].back()[1]] = a[q[i].back()[0]] >= k;
q[i].pop_back();
}
}
}
for (int i = 0; i < m; i++) {
cout << (ans[i] ? "YES" : "NO") << '\n';
}
return 0;
}还有一种根号分治的做法。上述做法之所以会用到可持久化线段树，是因为我们不可能预处理出大于等于某个值前缀和，时间和空间复杂度都是 $O\left(n^2\right)$。现在设置阈值 $M = \sqrt{n}$，与上述一样，当 $k < M$ 时直接跑暴力，该部分的时间复杂度为 $O(n \sqrt{n})$。对于 $k \geq M$ 的部分，显然最多能提升 $O(\sqrt{n})$ 个等级，因此我们先分别预处理出大于等于 $1 \sim \sqrt{n}$ 的前缀和，对于每个 $k$ 同样是二分出右端点 $r$，但对于二分点 $m$ 就换成前缀和用 $O(1)$ 的时间查询区间 $[l, m]$ 内大于等于 $\text{rk}$ 的元素数量。该部分的时间复杂度为 $O\left(n \log^2{n}\right)$，空间复杂度为 $O(n \sqrt{n})$。
AC 代码如下，时间复杂度为 $O\left(q\log{q} + n\sqrt{n} + n\log^2{n}\right)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5, M = 450;
int a[N];
int s[M][N];
vector<array<int, 2>> q[N];
bool ans[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int mx = *max_element(a + 1, a + n + 1);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
q[y].push_back({x, i});
}
for (int i = 1; i < M; i++) {
for (int j = 1; j <= n; j++) {
s[i][j] = s[i][j - 1] + (a[j] >= i);
}
}
for (int i = 1; i <= n; i++) {
sort(q[i].begin(), q[i].end(), greater<array<int, 2>>());
for (int j = 1, k = 1; j <= n; j++, k++) {
if (q[i].empty() || k > mx) break;
if (i < M) {
int c = 0;
while (j <= n && c < i) {
c += a[j++] >= k;
}
j--;
}
else {
int l = j, r = n;
while (l < r) {
int mid = l + r >> 1;
if (s[k][mid] - s[k][j - 1] >= i) r = mid;
else l = mid + 1;
}
j = l;
}
while (!q[i].empty() && q[i].back()[0] <= j) {
ans[q[i].back()[1]] = a[q[i].back()[0]] >= k;
q[i].pop_back();
}
}
}
for (int i = 0; i < m; i++) {
cout << (ans[i] ? "YES" : "NO") << '\n';
}
return 0;
}
参考资料
Educational Codeforces Round 168 [Rated for Div. 2]：https://codeforces.com/blog/entry/132049
标签：log,Level,int,NO,mid,Up,YES,monster From： https://www.cnblogs.com/onlyblues/p/18334209