自动搬运

查看原文

来自洛谷，原作者为

	ppip work work

搬运于2025-08-24 22:17:47，当前版本为作者最后更新于2023-01-29 16:41:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

$O(n\log\log n)$ 做法。要求 practical 的话用平衡树代替 vEB 可以 $O(n\log n)$。

第一步，我们把每场比赛转化成“可能赢的所有人的范围”，显然这是一个区间。

要求出这个区间，我们其实只需要用一个数据结构维护序列，每次来一场比赛的时候查询第 $l$ 个数，然后从它开始删除 $r-l$ 个数（留一个作为胜利者）就行了。这个可以用多种数据结构维护，这里为了复杂度最优使用 vEB。

接下来考虑这样一个结论：一个骑士如果输了某一场比赛，此时我们强行让它晋级继续打（不占用），它也不可能赢。所以我们求一场比赛能不能赢，可以把区间内的所有人都拉出来比。

同时，容易发现，如果迟到参加了某场比赛，那么这场比赛原来的最后一个一定被挤掉。所以我们可以枚举比赛，判断迟到能不能赢，能赢就给比赛对应区间加一，最后对每个点的值取 max 就行了。

判断每场比赛迟到能不能赢，这个可以将能力值序列转化为一个 $01$ 序列，$0$ 表示这个数小于迟到的数，$1$ 反之。对这个序列做一次前缀和，然后判断这个区间（去尾的）是否和为 $0$ 就行了。时空 $O(n)$。

以下是树状数组（代替平衡树）实现前半部分的代码（by @GlaceonVGC）。

#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);
}