P6138 [IOI2012] 骑马比武竞赛 题解
ppip
·
·
题解
题目传送门
第一步，我们把每场比赛转化成“可能赢的所有人的范围”，显然这是一个区间。
要求出这个区间，我们其实只需要用一个数据结构维护序列，每次来一场比赛的时候查询第 $l$ 个数，然后从它开始删除 $r-l$ 个数（留一个作为胜利者）就行了。这个可以用多种数据结构维护，这里为了复杂度最优使用 vEB。
接下来考虑这样一个结论：一个骑士如果输了某一场比赛，此时我们强行让它晋级继续打（不占用），它也不可能赢。所以我们求一场比赛能不能赢，可以把区间内的所有人都拉出来比。
同时，容易发现，如果迟到参加了某场比赛，那么这场比赛原来的最后一个一定被挤掉。所以我们可以枚举比赛，判断迟到能不能赢，能赢就给比赛对应区间加一，最后对每个点的值取 max 就行了。
判断每场比赛迟到能不能赢，这个可以将能力值序列转化为一个 $01$ 序列，$0$ 表示这个数小于迟到的数，$1$ 反之。对这个序列做一次前缀和，然后判断这个区间（去尾的）是否和为 $0$ 就行了。时空 $O(n)$。
以下是树状数组（代替平衡树）实现前半部分的代码（by @GlaceonVGC）。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, c, x, N, a, s[100001], l, r, v[100001], p, C[100001];
void mod(int p) {
while (p < n) {
C[p]--;
p += p & -p;
}
}
int ask(int p) {
int res = 0, sum = 0;
for (int i = N; i >= 0; i--) {
if (res + (1 << i) < n && C[res + (1 << i)] + sum < p) {
res += (1 << i);
sum += C[res];
}
}
return res + 1;
}
int main() {
scanf("%d%d%d", &n, &c, &x);
N = 32 - __builtin_clz(n);
for (int i = 1; i < n; i++) {
scanf("%d", &a);
s[i] = s[i - 1] + (a > x);
C[i] = i & -i;
}
while (c--) {
scanf("%d%d", &l, &r);
int L = l ? ask(l) : 0, R = ask(r + 1) - 1;
for (int i = l + 1; i <= r; i++) {
mod(ask(l + 1));
}
if (s[L] == s[R]) {
v[L]++;
v[R + 1]--;
}
}
for (int i = 1; i <= n; i++) {
v[i] += v[i - 1];
if (v[i] > v[p]) {
p = i;
}
}
printf("%d\n", p);
}
```