十一月算法竞赛选题（一）

[[ slider_text ]]

[[ item.c ]]

十一月算法竞赛选题（一）

发布时间 2025-11-13 作者：秋千月 来源：算法小站

## Codeforces Round 882 (Div. 2)
### D
**[D. Professor Higashikata](https://codeforces.com/contest/1847/problem/D)**
给定一个长度为`n`的`01 串`$$s$$，对$$s$$的一次操作，定义为选择两个不同的整数$$i, j$$
并且交换字符$$s_i, s_j$$

给定$$m$$个字符串$$t_1, t_2, \cdots, t_m$$，其中$$t_i = s[l_i, r_i]$$，表示子串
定义$$t(s) = t_1 + t_2 + \cdots + t_m$$，即按顺序将$$t_i$$连接起来

有$$q$$次对字符串的更新，第$$i$$次更新中，把$$s(x_i)$$取反，每次更新后，回答
最少需要多少次操作才能使得$$t(s)$$字典序最大

**算法分析**

> 初步发现，因为字符串只有`0 and 1`，字典序最大，就是把所有的`1`都放在前面
但问题是，我们需要的是$$t(s)$$字典序最大，这也不难，$$t_i$$看作有**时间戳**$$i$$
即$$[l_i, r_i]$$都有**最早的时间戳**$$i$$，如果之前某些点已经有了时间戳了，忽略这些点
然后对$$1\sim n$$按时间戳排序，`1`放在前面即可

这个怎么快速地实现呢？可以用一个`set`来维护**所有还没有被放置时间戳的下标**
如果一个下标被放置了时间戳，那么就从`set`中删去
对于$$t_i, i \in [1, m]$$，考虑区间$$[l_i, r_i]$$，那么我们从`set`中找到第一个$$\geqslant l_i$$的下标`it`
```bash
全局维护时间戳

while (*it <= r[i]):
	rk[*it] = ++时间戳，删除 *it
	it = it 在平衡树中的后继
```
这样就可以维护好每个位置的时间戳，时间戳越小的，越要放`1`

> 考虑修改和查询

可以用数据结构维护，把每个下标按照**时间戳**从小到大排序，构成`ord[...]`
根据`ord[...]`序列来构建线段树，如果某个下标未曾出现在$$t(s)$$中，时间戳设为$$+\infty$$

那么维护每次修改完，$$s$$中出现了几个`1`，假设有`k`个
修改的次数，就是查询`ord[1...k]`**前缀中`0`的个数`cnt`**，就是答案

修改呢？将`s[x]`取反？那么对应的是**单点修改**，`x`下标的时间戳是`tim[x]`
那么就对应`ord[  tim[x]  ]`处的**单点修改**，线段树维护的是**区间内`0`的个数**

> 坑点

比较坑的地方是，问题要求**区间（前缀）中`0`的个数**，还涉及到值修改操作
所以线段树**叶子结点**维护二元组`(val, cnt) = (这个位置具体的值， 这个位置 0 的个数)`
区间合并的时候，并不关心`val`的值是多少，`cnt`的值左右两半加起来即可

### F
**[F. The Boss's Identity](https://codeforces.com/contest/1847/problem/F)**
给定长度为$$n$$的序列，`a[1...n]`，前$$n$$个数是已知的，就是$$a_i$$
而对于$$i > n$$，我们有
```math
a_i = (a_{i-n} \mid a_{i-n+1})
```
现在给你`q`个询问，每个询问关联一个正整数$$v$$，找到最小的下标$$i$$
使得$$a_i > v$$，不存在输出`-1`

**算法分析**
```bash
1轮：(a[1] | a[2])    (a[2] | a[3])   ......   (a[n-1] | a[n])
2轮：(a[1] | a[2] | a[3]) ....

O(n^2)轮：(a[1] | a[2] | a[3] | ... | a[n])
```
不难发现，当$$i \geqslant O(n^2)$$之后，$$a_i = a_1 \mid a_2 \cdots \mid a_n$$

> 下面尝试找规律，考虑下标关系
![](/media/content_img/cf882-f.png)

发现这是从下标$$i$$开始，`[i, i+len-1]`的**环形子区间的 or**，区间长度从小到大
可以用** ST 表**预处理出$$f(i, len)$$，表示`[i, i+len-1]`这些数`or`在一起是多少？

那么我们对每个询问，要回答的就是，**需要找到满足条件的，环形区间的左端点**

> 所有出现的数，观察下标，是$$(i, len)$$，即从$$i$$开始，长度为$$len$$的环形子区间
区间长度从小到大

那么我们要定位$$> x$$的$$a[?]$$下标，不难想到
先二分区间长度，得到初步的**左端点**范围`[l, r]`
然后再继续在`[l, r]`上二分，找到满足条件的点

> 先来看二分区间长度，注意到`or`操作，左端点固定的情况下，最多只有$$O(\log V)$$个不同的数
所以一共有$$O(n \log V)$$个不同的区间，我们只需要把能够产生新的不同的异或值的，最小区间维护出来即可

于是可以按照**区间长度**来分类
开一个桶，`vec[ 出现新数所需要的最小区间 len ] = { (i, x) = (左端点， 区间 or 的值) } `

注意到，当固定区间左端点的时候，`区间 or`的值的大小，是随着区间长度单调增的
另外只有$$O(\log V)$$次会出现新的数，可以枚举$$O(n\log V)$$个数，情况大致如下
```bash
左端点固定，右端点最多只会产生 O(log V) 个不同的值

[i ....] = {x, x, ..., x,   y, y, ..., y,   z, z, ...., z}

用一个指针 lst 维护上一次出现新数 x，所在的最后的位置
while (lst + 1 <= i + n - 1):
	[i, lst+1] or 起来，一定是新的数 y
	[i ... ?] = {y, y, y, ...}，可能 [i...?] or 起来都是 y，不会出现新的数
	
	? 到底是多少呢？至少是 lst+1，最多可能是 i+n-1，二分出这个位置 ? = pos
	
	vec[(lst+1) - i + 1] = (i, y), then lst = pos
```

> 经过预处理之后，就可以二分出区间长度，我们可以知道在这个长度下，可能出现的最大值$$x$$是多少
以及对应的左端点在哪里

1.对询问离线，并且按照`v`从小到大排序

2.**枚举可能的区间长度**$$i$$，找到这个区间长度下，有新的数出现的左端点，也可以求出这个新的数可能是多少
在`vec[i]`这个桶里面，找到$$(j, x)$$，可以用线段树维护`max`，单点修改`tree[j] -> x`
表示说，`[j, j+i-1]`这个长度区间内，`or`起来的数的值是`x`

3.按`v`值从小到大考虑每个询问，假设当前枚举的区间长度是$$i$$，所有这个长度的区间
他们的数`or`起来最大是多少呢？`tree[1] = mx`，线段树根节点就是`or`起来会出现最大的数
**只有满足`mx > qry[k].v`**，这个询问`k`才会被考虑，区间长度从小到大考虑的时候
候选的询问`id = k`也一定是从小到大的，会被考虑的询问构成了一个区间，这可以用双指针维护

4.对会被考虑的询问$$p \in$$`[会被考虑的候选区间]`，那么要知道对应回原序列的位置是多少？
根据上面的图，前面有$$base = (n-1) \cdot (i-1)$$个数，若$$i \neq 1$$，`base += 1`
（加上的`1`，是因为序列长度`= 1`的时候，会多出来一个单独的数$$n$$）

接下来，比如`i = 5`，那么`i = 5`这一行（看上面的图），**最前面的位置**，是从`45612`开始的
也就是左端点形如
```bash
(?...n12) --->  (n12...)
```
其中`? = l = n+3-i`，根据下标`[?...n]`，**二分出第一个满足值 > v 的位置`p`**
限制条件是`[?...p-1]`的最大值$$\leqslant v$$
但是`[?...p]`的最大值$$> v$$，`p`即为所求，很典型的**线段树二分**

映射回原序列的位置，`base + p - ? + 1`，如果能找到这样的位置，直接输出即可

5.如果上面没找到呢？那么左端点就是从`1`开始，`[1....(n+3-i)-1]`
同样线段树二分出满足的位置$$p$$，映射回原序列，`base + (n-(n+3-i)+1) + p`

#### 算法实现
```bash
void solve(int cas) {
	int n, q;
	cin >> n >> q;

int N = 2 * n;
	vector<int> a(N+1, 0);

for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = n+1, j = 1; i <= N; i++) a[i] = a[j++];

using pint = pair<int, int>;
	vector<pint> qry;

for (int i = 1; i <= q; i++) {
		int v;
		cin >> v;
		qry.emplace_back(v, i);
	}

sort(qry.begin(), qry.end());

// debug(a);
	RMQ<int> rmq(a, N);

vector<vector<pint> > vec(n+5);

for (int i = 1; i <= n; i++) {
		int lst = i - 1;

while (lst+1 <= i+n-1) {
			// {x, x, ..., x,  y}
			int l = lst+1, r = i+n-1, x = rmq.qry(i, l);

while (l < r) {
				int mid = (l + r + 1) >> 1;
				if (rmq.qry(i, mid) == x) l = mid;
				else r = mid - 1;
			}

int R = l, len = lst+1 - i+1;
			vec[len].emplace_back(i, x);
			lst = R;
		}
	}
	
	// debug(vec);

segtree<int, op> tr(vector<int>(n+1, 0), n);

vector<i64> ans(q+5, -1);

int j = 0;
	for (int len = 1; len <= n; len++) {
		for (auto [i, x] : vec[len]) tr.change(i, x);

int k = j;
		while (j < qry.size() && qry[j].first < tr.query(1, tr._n))	j++;

// [k, j)
		for (int i = k; i < j; i++) {
			auto [v, id] = qry[i];

int l = n+2 - len+1, r = n, pos = -1;
			i64 base = 1LL * (n - 1) * (len - 1);
			if (len != 1) base++;

value = v;
			if (l <= r) {
				pos = tr.max_right<f>(l, r);
			}
			if (pos != -1) {
				i64 at = base + (pos - (n+3-len) + 1);
				ans[id] = at;
				continue;
			}
			
			pos = -1;
			l = 1, r = min(n+2-len, n);
			pos = tr.max_right<f>(l, r);

if (pos != -1) {
				i64 at = base + max(0, n - (n+3-len) + 1) + pos;
				ans[id] = at;
			}
		}

for (auto [i, x] : vec[len]) tr.change(i, 0);
	}

for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
```

## EPIC Institute of Technology Round Summer 2024
### D
**[D. World is Mine](https://codeforces.com/contest/1987/problem/D)**
有`n`块蛋糕，第`i`块蛋糕的美味值是$$a_i$$，现在 Alice 和 Bob 轮流吃蛋糕，Alice 先手
Alice 回合，任意吃蛋糕，前提是吃的蛋糕的美味度严格$$>$$之前吃的美味度的最大值
Bob 回合，任意吃蛋糕
现在$$x$$表示 Alice 吃掉的蛋糕数量，Alice 希望最大化$$x$$，Bob 希望最小化$$x$$
双方都采取最优策略，问最终 Alice 能吃多少个蛋糕

**算法分析**
如果按蛋糕的美味度，**从小到大排序**，Alice 的决策相对固定，就是从左往右吃
而 Bob 要尽可能破坏这个过程，吃掉一些美味度大的蛋糕

如果所有蛋糕美味度都不尽相同，那么答案很显然就是$$\lceil \dfrac{n}{2} \rceil$$
现在就是考虑，比如美味度是$$x$$的蛋糕，有$$c_x$$个，那么`Bob`要破坏这个蛋糕
至少要**留有$$\geqslant c_x$$的余地**，前面几轮都专门吃$$x$$这块蛋糕，吃$$c_x$$次

> 针对**留有余地**的情况，我们可以**摊还分析**

就是如果需要**留有余地**，$$\geqslant c_x$$，那么可以看作，**前面至少要跳过$$\geqslant c_x$$轮**
（跳过的意思就是这一轮不吃蛋糕）（实际上也是吃的，只不过吃的是之后的$$c_x$$）

于是可以设计$$dp(i, e)$$，表示当前 Alice 考虑蛋糕`i`，而`Bob`跳过的轮数是$$e$$，此时最少能吃的蛋糕数

**根据势能分析**
可以看作，阻止 Alice 吃蛋糕，需要消耗能量，$$e \to e - c_x$$
而不管不顾 Alice 吃蛋糕，相当于留有更多的余地，能量增加，$$e \to e + 1$$

**根据`Bob`跳不跳过当前回合**来做决策
1.跳过当前回合，那么 Alice 能顺利吃到蛋糕，$$\min dp(i, e) + 1 \to dp(i+1, e+1)$$
2.不跳过当前回合，让`Alice`吃不到当前的蛋糕，$$\min dp(i, e) \to dp(i+1, e - c(a[i]))$$
其中$$c(a[i])$$表示当前美味度的蛋糕的数量

## Codeforces Global Round 25
### D
**[D. Buying Jewels](https://codeforces.com/contest/1951/problem/D)**
Alice 有$$n$$枚硬币，想去 Bob 的珠宝店购物，Bob 最多可以有`60`个摊位，每个摊位有无限数量的珠宝
每个摊位的每件珠宝的价格可以任意设置$$1 \sim 10^{18}$$

Alice 是贪心购买，他会先去第一个摊位，尽可能多的购买珠宝，然后去第二个，直到最后一个
现在需要你帮助 Bob 设计珠宝摊位的数量，以及每个摊位的价格，使得 Alice 恰好买到$$k$$件珠宝
或者报告不可能

**算法分析**
首先判断几种简单情况
如果$$n < K$$显然无解
如果$$n = K$$呢，那么设一个摊位就好了，价格是$$1$$
如果$$n \bmod K = 0$$呢，设一个摊位，价格是$$n / K$$

下面只需要考虑$$n > K$$的情况，研究样例发现
**情况1**
如果$$K < n < 2K$$，**那么你第一个摊位价格设置成`1`**是不合适的
因为这样的话，你买到的数量就一定是$$n$$，而$$n > K$$

所以第一个摊位的价格只能是`2`，这样一定是形如$$n = 2? + 1$$
因为根据贪心地买到不能买为止，剩下的$$\bmod 2 = \\{0, 1\\}$$，而$$\bmod 2 = 0$$的情况不可能
（因为这样实际上就买走了`n`件，而$$n > K$$，不符合）
另一方面，要恰好$$K$$件，所以$$? + 1 = K$$，$$n = 2(K-1) + 1 = 2K - 1$$
只有这样，才能够满足，`2`个摊位，分别定价`2 1`

**情况2**
如果$$n > 2K$$，同样由于第一个摊位的价格必须$$> 1$$，这种情况下
第一个摊位的价格一定是$$\geqslant 2$$的，在此基础上，我们可以让**定价尽可能大**
**大到只能买一件商品为止**
这样第二个摊位定价为`1`，买完剩下的，这样可以吗？

这样的话，设第一个摊位定价是$$?$$，那么$$? \cdot 1 + 1 \cdot (K - 1) = n$$
从而$$? = n - K + 1$$

而$$2(n - K + 1) > n$$，所以这样定价的话，第一个摊位一定只能买一件商品
（这是显然的，$$2(n - K + 1) - n = (n - 2K) + 1 > 0$$恒成立）

这样可以定价`(n-K+1, 1)`

### E
**[E. No Palindromes](https://codeforces.com/contest/1951/problem/E)**
给定一个小写字符组成的字符串$$s$$，需要把字符串划分成若干子串，使得每个子串都不是回文串
求方案

**算法分析**
> 考虑简单的情况

如果原串就不是回文串，那么不要划分，直接输出，如果原串是形如`aa...a`，仅有一个字符
那么也不行，直接输出

**回文串很基本却又不太容易被注意到的性质**
如果`len = 偶数`，所有字符的出现次数都是**偶数**
如果`len = 奇数`，有且仅有一个字符出现次数是奇数，并且这个奇数次出现的字符，一定是**回文中心**

那么，怎么构造一个串，使得它**一定不是**回文串呢？
1.只要$$\geqslant 2$$个字符出现次数是**奇数**，那么就一定不是回文串
2.串的长度是**偶数**，但是却有$$\geqslant 1$$个字符出现次数是**奇数**（只要有出现次数是奇数的字符就不行）

> 考虑稍微复杂一点的情况，只有两个字符，不妨设为`A, B`

**以下讨论**，都是建立在一整个串是回文的基础上
**情形一**，`len = 偶数`
```bash
在前缀中找到第一个 B 的位置
case 1:
A....B | B....A
left  以 A 开头，B 结尾，一定不是回文
right 以 B 开头，A 结尾，也一定不是回文
只要在前缀中找到这样的位置，就做完了

case 2:
(AA....B) | (A...B...A)
1）若 right 非回文，做完了
2）若 right 回文，right 一定有 B 出现的次数是奇数，B 是回文中心，且 right 长度是奇数
那这个时候，right 形如 (AA...) B (...AA)
right[0]，将 right 的第一个字符 A 移动到 left 末尾会是什么情况呢？
此时 right 的长度是偶数，而 B 出现的次数是奇数，这样 (AA...B A) | (...B ... A) 的划分
能够保证 right 一定不是回文

left 呢？B 出现的次数是奇数（我们在第一次出现 B 时候就做了划分），如果是回文只能是奇回文
并且回文中心的字符一定是 B，而 B 在靠后的位置，只要非 ABA，那么一定不是回文
而 ABA 这种情况是不会出现的，如果出现的话，一定一开始是 (A B) | (A...B...A)
这样的话原串的长度是奇数了，我们假定原串的 len = 偶数，矛盾
```

**情形二**，`len = 奇数`
有一些情况是明显不存在合法划分的，之前我们已经知道了`ABA`这种结构是不能划分的
```bash
AAA...A B A...AAA
ABABABA...BA
这两种结构都是不行的
```
考虑具体的情形
```bash
A 是回文中心，A 的个数是奇数，B 的个数是偶数

case 1:
A... A ...A
找到第一个 B，(A...B) (A...A)
如果 right 的长度是偶数，那么 B 的个数是奇数，肯定不是回文，做完了
如果 right 的长度是奇数，那么意味着 left 的长度是偶数，right 又有奇数个 B，B 是回文中心
这时候仿照之前的做法，把 right 的第一个 A 移动到 left 中，这样 right 长度是偶数，却有奇数个 B
而 left (A...BA) 又一定不是回文，且长度是奇数

case 2:
B... A ...B
在前缀中找到第一个 A
(B...A) (A...B)，那么就做完了

下面只考虑
left = (B...A)
right = (B...B) 的情况

case 2.1:
right 的长度为奇数
因为 left 中只有 1 个 A，A 的总个数是奇数，所以 right 中 A 的个数是偶数
那么 right 如果是回文串（如果不是回文，直接做完了），A 的个数是偶数，B 的个数是奇数
并且回文中心一定是 B
right = (B...B...B)
而根据之前 case1 的讨论，这样的形式一定还能继续划分成两个非回文串

继续划分的话
1) right = (B...A) (A...B)，同样找到第一个 A 所在的位置，right1 中只有 1 个 A
这种情况，(left + right1) (right2) 都是非回文的，满足条件
2) right = (B...AB) (right2)，根据 case1 的分析，right2 的长度是偶数，这意味着
考虑 (left + right1) (right2)，right2 中有偶数个 A，偶数个 B
那么 left + right1 中就应该有奇数个 A，而根据我们之前的做法，left 中只有 1 个 A
right1 中也只有 1 个 A，所以 left + right1 中仅有 2 个 A，矛盾的
所以这种情况，也可以在前缀找到一个划分点，使得 left，right 均为非回文

case 2.2:
right 的长度是偶数
找到第一个 A 所在的位置，left = (B...A), right = (B...B)
注意到 left 仅有一个 A，那么 right 中 A 的个数是偶数，又因为 right 的长度是偶数
从而推出 right 中 A, B 均为偶数
根据 len = 奇数的情形，形如 right = B...B 并且长度为偶数，一定存在非回文的划分

更进一步地
right = B...B，再在其中找到第一个 A 出现的位置
right = right1 + right2 = (B...A) + (?...B)
不难发现，left + right1 一定不是回文的，并且 A 的个数 = 2，那么 right2 中 A 的个数是奇数
也就是说，right2 如果是回文，就一定是奇数回文，并且以 A 作为回文中心
形如 (B...A...B)

发现没？又是一个关于 B...A....B 的子结构
对于这样的子结构，可以不挺地找到第一个 A 所在的位置，形如 (B...A)，并和前缀合并
总能完成
```

> 如果有$$\geqslant 3$$个字符出现了呢？

**情形一** `len = 偶数`
```bash
case 1:
A...CC...A
考虑在 CC 中间断开，A...C | C...A，这样 left 和 right 都一定不是回文

case 2:
A...C ..中间隔着其他数.. C...A
可以调整断开的位置，使得 (A...C..?) | (?...C...A)
left 和 right 都有奇数个 C，另外可以调整断开的位置，使得 left 和 right 都有奇数个 B/A
这一定可以做到，因为串的长度是偶数，一定可以拆成两个奇数相加的形式
这样 left 和 right 都有至少 2 个字符，出现次数为奇数，一定不是回文
```

**情形二** `len = 奇数`
```bash
case 1:
A....A....A
其中 A 出现次数是奇数，B, C 为偶数

那么考虑一定存在出现的第一个 B 和 第一个 C，存在划分
A...B...B..C | (right)

case 1.1:
A...B...B..C | (C....A)，那么做完了
case 1.2:
A...B...B..C | (A ? .... A)，right 如果是回文串的话，一定是这种情况
首先，right 中一定有奇数个 C
如果 right 中 A 的个数已经是奇数个，那么做完了，right 一定不是回文串
否则的话，移动分割点，(A...B...C A) | (?...A)，这样 right 有奇数个 A, C 一定不是回文
而 left 呢？(A...B...C A) 一定不是回文串，也做完了

case 2:
A...B...A
其中 B 出现的次数是奇数，A, C 出现次数是偶数
那么同样依次找第一次出现的 B 和 C

case 2.1:
A...B...C | C....A，那么做完了

case 2.2:
A...B...C | (A....A)，right 如果仍然是回文的话
首先，right 中 C 的个数一定是奇数个，如果 A 的个数也是奇数个，那么 right 一定不是回文
否则，可以通过移动分割点，A...B...C A | (....A)，使得 right 中 A, C 出现的个数都是奇数、
left 形如 A...B...C A 一定就不是回文，做完了
```

### F
**[F. Inversion Composition](https://codeforces.com/contest/1951/problem/F)**
给定一个长度为`n`的排列`p`，再给你一个非负整数`K`，你需要构造一个排列`q`
使得$$inv(q) + inv(q \cdot p) = K$$，其中`inv`表示排列逆序对的个数，$$q \cdot p(i) = x$$
实际上是对于`i`，`q[ p[i] ] = x`

**算法分析**
> 原来的问题很抽象，考虑具体的$$1 \leqslant x < y \leqslant n$$，能贡献多少逆序对

![](/media/content_img/global25-F.png)

> 进一步分析

可以发现，对于$$1 \leqslant x < y \leqslant n$$来说
如果$$pos_x > pos_y$$，不论`q[x], q[y]`相对大小关系是怎么样的，**不管怎么样，对答案的贡献都是`1`**
所以可以先统计关于`pos[...]`数组，满足$$1 \leqslant x < y \leqslant n, pos_x > pos_y$$的$$(x, y)$$对数
即统计`pos[...]`序列的逆序对`inv0`

> 这样，我们只需要考虑$$x < y, pos_x < pos_y$$的这样一组位置$$(x, y)$$

如果$$1 \leqslant x < y \leqslant n, pos_x < pos_y$$
若$$q_x < q_y$$，贡献是`0`，$$q_x > q_y$$，贡献是`2`
那么有几对$$(x, y)$$，满足$$x < y, q_x > q_y$$呢？答案是$$k \leftarrow \dfrac{k-inv0}{2}$$

> 于是问题转化成，`for x`，找到满足$$x < y$$并且$$pos_x < pos_y$$的$$y$$
恰好有$$k$$个$$y$$，满足$$q_x > q_y$$
剩下的$$x < y$$并且$$pos_x < pos_y$$的位置，必须满足$$q_x < q_y$$
上面的条件是硬性要满足的，剩下的就是$$x < y, pos_x > pos_y$$的$$y$$，最后放，可以任意放

下面考虑具体的构造，对于$$1 \leqslant x < y \leqslant n$$，可以从小到大`for x`

1) 统计满足`> x`的，并且值域在$$[pos_x+1, \cdots)$$的数有多少个，这个也很简单
树状数组维护，算完之后就把`pos[x]`这个位置的数给删掉即可，假设说统计出来有`cnt`个
这些位置是**限制位置**

2) 如果$$cnt \leqslant K$$，限制位置条件是，$$y > x, q_x > q_y$$
只要$$q_x$$填上**尽量大**的数，这几个限制位置的约束条件都可以满足
而`y > x`的，不满足限制的位置是$$pos_y < pos_x$$，这些位置随便放什么数并不影响
所以从大到小构造，令`q[x] = 当前最大的数，当前最大数 -= 1`即可，$$K -= cnt$$

3) 如果$$cnt > K$$，那么限制位置**不能都满足**$$y > x, q_x > q_y$$
此时只能有$$K$$个满足$$q_x > q_y$$，另外$$d = cnt - K$$必须强制$$q_x < q_y$$
这个时候$$q_x$$显然就不能放当前最大的数了
```bash
[... d个 <q[x] 的数 ...] < [... K 个 >q[x] 的数 ...]
```
那么这个时候实际上可以一次性放完
从`for y = n downto x+1，放 K 个数`，`q[y] = 当前最大的数`，从后往前，从大到小了放
放完之后，放`q[x]`

接着，如果`y > x`，考虑第二个限制，如果仍有`pos[x] < pos[y]`，需要放上`[... d 个 <q[x] 的数...]`
也是从后往前放

最后，`for y = n downto x+1`，考虑$$pos_x > pos_y$$的`y`，把没放上的位置都给放上
这样就构造完了，整个的构造过程是$$O(n)$$的

### H
**[H. Thanos Snap](https://codeforces.com/contest/1951/problem/H)**
给定一个长度为$$2^k$$的序列`a`，一开始是关于$$[1, 2^k]$$的一个排列，Alice 和 Bob 轮流玩游戏
一开始被给定一个值$$t \in [1, k]$$，然后游戏进行`t`轮，你需要输出`t = 1...k`时，两人都采取最优策略
游戏的得分是多少

每一轮游戏
Alice 可以什么都不做，或者交换序列`a`中，任意两个不同元素的位置
Bob 可以选择`a`的左半部分，或者右半部分，将其删除

实际上，就相当于从线段树的第`0`层走到第`t - 1`层，问 Alice 的得分
游戏的得分定义为，操作结束后，**序列`a`的最大值**

**算法分析**
![](/media/content_img/global24-H.png)

> 不难想到，可以二分答案，假设二分出来的最大值是$$x$$，有什么限制？

考虑**[D. World is Mine](https://codeforces.com/contest/1987/problem/D)**
和这个问题差不多，考虑**有什么限制**，并且为了满足限制，**需要预留多少次的操作？**

首先考虑限制，假设说到了`t 层`，有`1`个$$\geqslant x$$的数，那么在`t-1`层，左右两边
至少都要有一个$$\geqslant x$$的数

在第`t 轮`，$$t = [0, \cdots)$$线段树递归的终点是第`t`层，假设说当前递归到了第$$d$$层
那么当前区间内，$$\geqslant x$$的数**至少要有**$$2^{t - d}$$个

这个不妨让我们想到了中位数的处理方法，$$\geqslant x$$的数用`1`表示，$$< x$$的数用`0`表示
问题转化成，在`t 轮`，当前递归到线段树的第`d`层，那么节点表示的区间`1 的个数`**至少**$$\geqslant 2^{t - d}$$

> 考虑需要预留多少次操作？

自底向上考虑，假设说现在在叶子结点`t 层`，如果当前区间内已经有$$\geqslant 1$$个`1`
那么不需要任何操作，否则需要预留`1`次操作，将其他地方的`1`给交换过来

> 考虑子节点向父节点的回溯

对于节点`u`，首先要保证`ls(u), rs(u)`都要满足相关的限制，`left, right`两个部分都需要有$$\geqslant x$$的数
用$$dp(u)$$表示在$$u$$这个节点预留了多少次的操作？

**从叶子结点自底向上**
不妨设`u`所在的层数是`d`，记`dp(u)`表示从根节点走到`u`所在的层（`[0, d-1]`层）
必须累计多少次交换操作

很显然，我们希望`dp[1] = 0`，这样就成功了，并且往儿子走，需要的交换操作要么不变，要么会增加
首先有转移$$dp(u) = dp(ls) + dp(rs) - 1$$，因为在`d`这一层，`ls, rs`的限制都必须满足的
所以往儿子走，必须要有`dp(ls) + dp(rs)`这么多操作，另外，`-1`是因为有一次操作，可以在`u`结点这一层给耗费掉

其次有限制$$dp(u) = \max(0, 2^{t-d} - [u\text{ 所表示的区间有几个 1}])$$
综上所述
```math
\displaystyle
dp(u) = \max(0, 2^{t-d} - (u\text{ 所表示的区间有几个 1}), dp_{ls}+dp_{rs}-1)
```

> 细节！

因为至少会操作一次，所以$$t$$最少也要在第`1`层，`for t = [1...K]`，而不是从`0`开始

## 2025 ICPC 武汉
### H
**[H. 还原数组](https://qoj.ac/contest/2568/problem/14726)**
交互题，给你一个长度为`n`的序列，数是两两不同的，但不知道每个数具体值是多少
你可以最多询问$$2n - 2$$次，每次询问`? c`，`c`由你自己确定
交互会返回一个值`res`，它的值是$$\max(a_i \oplus c)$$，现在要你确定`a`

**算法分析**
> 首先用`0`可以确定出`maxv`，用`11....1`可以确定出`minv`

那么这样分析，可以考虑有一种子问题的结构
从**高位往低位**考虑，**第一个**`maxv, minv`二进制下不同的位，假设说是`p`
```bash
mx:  x x x 1 ? ? ? ?
mn:  x x x 0 ? ? ? ?
```
那么首先，从最高位到`p+1`位，前缀`mn, mx`都是一样的
说明`[mn, mx]`区间内所有的数前缀都是`prefix`，`c`要怎么选呢？
很显然如果`prefix[i] = 0`，那么`c[i] = 1`，否则`c[i] = 0`，这样查询之后
因为交互器返回的是**最大值**，才可以保证得到的数**前缀跟`[mn, mx]`的前缀保持一致**

> 接下来考虑`a[...]`中第`p`位，有没有数的值是`1`

如果有，那么一定形如
```bash
mx:    x x x 1 [...最大后缀...]
?:       x x x 1 [...最小后缀...]
```
如果存在的话，那么接下来只需要找到`[p-1...0]`这几位构成的**后缀最小值和后缀最大值即可**
而后缀最大值，就是`mx`，我们已经找到了
后缀最小值呢？那就是`[p-1...0] = 111...1`
我们查询`mn = { ask: c | ( (1<<p)-1 ) }`即可，更新`now_mn`

然后`dfs(now_mn, mx)`，这样第一个不同的位至少就是`p-1`了，继续往下`dfs`
这样处理完，就会把尽可能高位填`1`的数都找到了

> 对称地，考虑`a[...]`第`p`位，有没有数的值是`0`

```bash
?:     x x x 0 [...最大后缀...]
mn:  x x x 0 [...最小后缀...]
```
很显然现在第`p`位填上了`0`，这个时候`pre |= (1 << p)`
最小后缀，我们已经找到了，就是`mn`对应的后缀
最大后缀怎么找呢？`[p-1...0] = 00...0`，更新`now_mx = { ask:  pre }`
然后`dfs(mn, now_mx)`即可

上一篇：十月算法竞赛选题（一）下一篇：十一月算法竞赛选题（二）

看完文章有啥想法