\(CF1839E\) Decreasing Game
考虑两个数的情况。显然，若两数不等，先手胜；否则，后手胜。
不妨直接猜结论 : 如果能找出一个集合，使得集合中元素的和恰为总和的一半， 则后手胜； 否则先手胜。
充分性很显然，每次先手选择一个数，后手只要在另一个集合中也选一个数即可。 这样两个集合减少的值相同；
需要证明的是如果找不出这样一个集合，那么是否经过若干次操作后，仍然找不出。
若一次操作两人分别选择了 \(x\) 和 \(y\) 且 \(x \leq y\), 假设经过这次操作后可以找出一个集合，使得其元素和为总和一半，其中 \(y - x\) 所在集合的其他数总和为 \(s1\),
另一个集合总和为 \(s2\)，即 \((y - x) + s1 = s2\)， 移项后发现 \(y + s1 = x + s2\)， 矛盾。
因此结论是成立的。
用动态规划求解一个背包问题即可。
时间复杂度 \(O(N ^ 3)\)
\(CF1748E\)
首先发现，一个序列合法当且仅当大小关系和原序列一致。
建出笛卡尔树后解一个简单的动态规划 , 即可。
时间复杂度 \(O(NM)\)
\(CF1858E\)
不妨考虑如果不支持回退怎么做。
考虑这些 \(+\) 和 \(-\) 的操作其实可以抽象为一个树形结构。 对于每个点而言，根到其路径上的数可以还原原序列是什么样子。
假设上次操作结束后所在的点为 \(u\), 如果添加一个数， 那么新建一个点 \(v\) 作为 \(u\) 的儿子即可。如果将序列长度减少 \(k\), 那么相当于往父亲方向跳了 \(k\) 次。
所以可以通过倍增实现求 \(k\) 级祖先。
而如果有回退怎么办呢？直接维护一个栈，栈里存储每次操作后当前点的位置。 每次回退弹出栈顶即可。
现在唯一的问题是如何求答案？
最简单的方式是将所有询问离线， 用一次 \(DFS\) 可以很方便求出每个点到根路径上不同的数的个数。
这样做可以轻松通过 \(E1\), 而无法通过 \(E2\), 因为 \(E2\) 强制在线。
不难发现这个祖先-后代的关系其实可以用可持久化线段树维护。 对于每个添加操作，只需要在线段树上查一查，看看能不能产生贡献即可。
这样做时间复杂度是 \(O(NlogN)\) 的， 足够通过本题。
然而我们有更优秀的线性做法 :
考虑一个数对答案有贡献，当且仅当它首次出现。
维护一个长度为 \(n\) 的数组 \(a\)， 和一个长度为 \(N\) 的数组 \(A\) 其中 \(n \leq N\)，并且 \(\forall i \leq n, a_{i} = A_{i}\)。另外记 \(occ_{i}\) 表示 \(i\) 这个数第一次
出现是在什么位置。我们只需要保证对于每个 \(a_{i}\)，\(occ_{a_{i}}\) 的值是正确的。
如果新添加一个数 \(x\)，如果 \(occ_{x} > n\) 或者 \(a_{occ_{x}} \neq x\)，那么可以更新 \(occ_{x}\) 的值，并将答案加一。
如果将序列长度减少 \(k\)， 那么直接将 \(n\) 减去 \(k\) 。
对于回退操作， 我们像刚才描述的一样， 用堆栈记录更新操作。 每次取栈顶即可。
而对于求答案， 维护一个数组 \(ans\)， 要求的就是 \(ans_{n}\)
时间复杂度 \(O(N)\)
放一下代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MN = 2e6 + 5;
struct node {
int *x, val;
node(int *x, int val) : x(x), val(val) {}
} ;
int foo[MN], ans[MN], a[MN], tim;
char c[2];
stack < vector < node > > s;
int main() {
int q; scanf("%d", &q);
while (q--) {
scanf("%s", c);
if (c[0] == '+') {
vector < node > cng;
int x; scanf("%d", &x);
if (foo[x] > tim || a[foo[x]] != x) {
cng.emplace_back(node(&foo[x], foo[x]));
foo[x] = tim + 1;
cng.emplace_back(node(&ans[tim + 1], ans[tim + 1]));
ans[tim + 1] = ans[tim] + 1;
} else {
cng.emplace_back(node(&ans[tim + 1], ans[tim + 1]));
ans[tim + 1] = ans[tim];
}
cng.emplace_back(node(&a[tim + 1], a[tim + 1]));
a[tim + 1] = x;
cng.emplace_back(node(&tim, tim));
++tim;
s.push(cng);
} else if (c[0] == '-') {
vector < node > cng;
int x; scanf("%d", &x);
cng.emplace_back(node(&tim, tim));
tim -= x;
s.push(cng);
} else if (c[0] == '!') {
vector < node > v = s.top(); s.pop();
for (node e : v)
*e.x = e.val;
} else {
printf("%d\n", ans[tim]);
fflush(stdout);
}
}
return 0;
}