I. Counter
按时间排序即可，注意可以不清零。
F. Equivalent Rewriting
对于每个位置，把所有有这个位置的操作编号连向这个位置最终的值，做个拓扑排序，看看字典序最大的即可。复杂度 \(\Theta(n+m)\)。
C. Primitive Root
枚举和 \(m\) 的公共前缀，设 \(i\) 位置 \(m\) 是 \(1\) 但是取了 \(0\)，前面的这些数异或 \((p-1) \equiv t \pmod{p}\)。那么剩下 \(0 \sim i - 1\) 这些位置可以任意取，就是 \([0,2^i)\) 模 \(p\) 同余 \((1-t)\)，直接算就行。复杂度 \(\Theta(\log m)\)。
G. Knapsack
把物品按照美丽程度 \(v_i\) 为第一关键字从大到小排序，\(w_i\) 为第二关键字从大到小排序。显然 \(k\) 个免费的物品都是取的相同美丽程度的最大的几个，所以按 \(w_i\) 是从大到小排序。设 \(k\) 个物品取了排序后的 \(p_1 < p_2 < \cdots < p_k\) 这些物品，则 \(1 \sim p_k\) 这些物品肯定都被取走，因为假如 \(t<p_k\) 没被取走，那么把 \(p_k\) 丢掉换成 \(t\) 肯定不劣。那么对后缀做个背包，枚举 \(p_k=i\)，前缀需要的花费是重量前 \(i-k\) 小的重量和。复杂度 \(\Theta(nW+n^2)\)。
A. Cool, It’s Yesterday Four Times More
要验证一个点 \((x,y)\) 是否合法，那就是对于所有其他的 \((x',y')\)，都有一种移动方式使得 \((x,y)\) 没撞墙 \((x',y')\) 撞墙。设一个点 \((x,y)\) 所在的 . 联通块是 \(S_{x,y}\)，那么它只能在这个联通块内运动。考虑不合法的条件，也就是存在 \((x',y')\) 使得 \(S_{x',y'}\) 在和 \(S_{x,y}\) 以 \((x',y')\) 和 \((x,y)\) 两点重合的方式平移后 \(S_{x',y'}\) 完全覆盖 \(S_{x,y}\)。
所以，对于一个联通块 \(S\)，若存在联通块 \(S'\) 使得 \(S'\) 能以某种平移方式完全覆盖 \(S\)，则 \(S\) 里的点都不合法，否则都合法。那么对于 \(S\) 种每个点，随便找个点 \((x,y)\) 作为中心点，然后对于每个点 \((a,b)\)，枚举其他空的位置 \((c,d)\)，然后将 \(cnt_{c+(x-a),d+(y-b)}\) 加 \(1\)，若不存在 \(cnt_{i,j}((i,j) \neq (x,y)) = |S|\)，则 \(S\) 合法。
复杂度 \(\Theta(n^2m^2)\)。
L. Elevator
把所有物品按照 \(f\) 从大到小排序取，把物品分成 \(w=1,2\) 的两组，分别为序列 \(a,b\)。显然同一组内是从大到小取的，而都能从大到小取是因为若一次取了个 \(b_i,b_j\)，第二次取了 \(a_k\)，并且 \(b_i < a_k < b_j\)，把 \(a_k\) 和 \(b_i\) 交换总不劣。那么做个双指针就行，细节问题上注意有时候背包放到 \(k-1\) 时可以额外拿一个 \(w=1\) 的物品。
复杂度 \(\Theta(n\log n)\)。
M. Trapping Rain Water
注意到前缀 \(\max\) 和后缀 \(\max\) 一定会出现一个交点 \(i\)，使得 \(\forall j<i,pre_j < suf_j \land \forall j\ge i,pre_j \ge suf_j\)，那么答案就是 \(\sum\limits_{j=1}^{i-1} suf_j + \sum\limits_{j=i}^n pre_j-\sum\limits_{j=1}^n a_j\)。 \(pre_i,suf_i\) 可以利用颜色段维护，也可以用线段树二分+区间覆盖维护，然后二分求出交点即可。复杂度 \(\Theta(n\log n)\)。
D. Red Black Tree
考虑朴素 dp，设 \(f_{u,i}\) 为 \(u\) 子树合法且 \(u\) 到每个叶子长度有 \(i\) 个黑色，\(g_{u,0/1}\) 为 \(u\) 变成 \(0/1\) 的代价。显然有转移 \(f_{u,i} = \min\limits_{j=\{0,1\}}(g_{u,j} + \sum\limits_{v \in to(u)} f_{v,i-j})\)。
考虑转移是一个 \(\min+\) 卷积，且 \(g_u\) 是凸的，所以 \(f_u\) 也是凸的。那套路地维护 \(f_{u,0}\) 和它的单调不降差分数组。对于 \(\sum\limits_{v \in to(u)} f_{v,i}\) 可以直接暴力合并，剩下子树内最大深度最小的那个，复杂度参考长链剖分，为 \(\Theta(n)\)。然后是和 \(g_u\) 合并时，差分后 \(g_{u,1}=\pm 1\)，根据闵可夫斯基和，合并时找到 \(f_u\) 差分数组中第一个大于它的位置前面插入即可，直接用 multiset 维护可以 \(\Theta(n\log n)\)。但是考虑到值域只有 \(\pm 1\)，所以可以把差分数组拆成正数从大到小的 vector 数组，负数从小到大的 vector 数组，还有 \(0\) 的个数，每次插入直接在对应号的最后 push_back 即可。复杂度 \(\Theta(n)\)。
标签：11,Contest,复杂度,Nanjing,从大到,物品,Theta,排序 From： https://www.cnblogs.com/MiniLong/p/18442481