看似人类智慧，实则数据结构。
[省选联考 2021 A/B 卷] 卡牌游戏
题目描述
Alice 有 \(n\) 张卡牌，第 \(i\)（\(1 \le i \le n\)）张卡牌的正面有数字 \(a_i\)，背面有数字 \(b_i\)，初始时所有卡牌正面朝上。
现在 Alice 可以将不超过 \(m\) 张卡牌翻面，即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 \(n\) 个数字的极差（最大值与最小值的差）尽量小。请你帮 Alice 算一算极差的最小值是多少。
思路
首先，极差只和当前数列的最大最小值有关，所以我们只有翻最大最小值才会更新答案，由于 \(a\) 的单调性，我们很容易发现一个性质：
翻牌只能从最左边开始翻连续的一段，或从最右边翻连续的一段。
这个很容易吧。
然后开始乱搞，想要枚举左段长度然后算右段，这个其实做不到。
再回到极差这个问题，最原始的做法是固定最小值，找最大值最小。
我们分两步考虑。
1.让原本低于最小值的翻上去（左边连续段）
2.原本大于最小值的，不能上翻，如果能下翻且下翻值不低于最小值，需要选（右边连续段）
3.两段之和 \(\le m\)。
如果能枚举最小值，然后快速找到这样一种方案，就解决了。
1很好考虑，用二分查找，2的话，发现必须是右边连续段，所以只要找到最右边第一个不合法的。开一棵线段树，维护当前节点 A. 是否存在上翻 B. \(b_i\) 的最小值，那么就很容易在线段树上二分。
void build(int l, int r, int p) {
if (l == r) {
up[p] = (b[l] >= a[l]);
minb[p] = b[l];
return ;
}
int mid = l + r >> 1;
build(l, mid, ls(p));
build(mid + 1, r, rs(p));
pushup(p);
}
int query(int l, int r, int x, int p) {
if (l == r) return l;
int mid = l + r >> 1;
if (a[mid + 1] > x && !up[rs(p)] && minb[rs(p)] >= x) return query(l, mid, x, ls(p));
else return query(mid + 1, r, x, rs(p));
}
这样算出来后和 \(m-1操作个数\) 比对一下，取最优点，然后维护前缀后缀 \(b_i\) 最大值，更新最大值就好了。
for (int i = n; i >= 1; i--) las[i] = max(las[i + 1], b[i]);
for (int i = 1; i <= n; i++) fro[i] = max(fro[i - 1], b[i]);
for (int x : value) { //value是a与b的值域
int t = m;
if (x < st || x > en) continue; // st,en是保证合法的最小值上下界。
int maxx = 0;
int pos = lower_bound(a + 1, a + 1 + n, x) - a - 1;
if (pos > t) continue;
maxx = fro[pos];
t -= pos;
int f = query(1, n, x, 1);
f = max(f, n - t);
maxx = max(maxx, las[f + 1]);
if (f != pos) maxx = max(maxx, a[f]);
ans = min(ans, maxx - x);
}