by TheBigYellowDuck
包括比赛题以及整场刷了的题。
1336 (Div. 1)
CF1336A Linova and Kingdom
最直接的想法是按照深度从大到小选，然而选一个非叶子节点会使得其子树内所有点的贡献 \(-1\)。那么我们把所有点按照 \(dep_u-sz_u\) 从大到小排序，选前 \(k\) 大的即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
Submission #254423271 - Codeforces
CF1336B Xenia and Colorful Gems
\((x-y)^2+(y-z)^2+(z-x)^2\) 可以看作 \((x-y)^2+(y-z)^2+(x-y+y-z)^2\)。这启发我们，\(x,z\) 和 \(y\) 的差距是唯一需要考虑的事情。
考虑钦定 \(y\) 在哪个集合中，在另两个集合中查找 \(y\) 的前驱和后继更新答案。需要枚举六种大小关系。
时间复杂度 \(\mathcal{O}(n \log n)\)。
Submission #254430161 - Codeforces
CF1336C Kaavi and Magic Spell
把 \(T\) 后面不足 \(n\) 的位补上通配符，可以匹配任何字符。
自然想到区间 dp，设 \(f(l,r)\) 表示用了 \(S[1,r-l+1]\) 匹配了 \(T[l,r]\) 的方案数，转移只需要枚举在开头加还是在结尾加即可。答案是 \(\sum_{i=m}^n f(1,i)\)。
时间复杂度 \(\mathcal{O}(n^2)\)。
Submission #254438692 - Codeforces
1479 (Div. 1)
CF1479A Searching Local Minimum
对于这个直接的要求，是不好做到的。于是我们考虑放宽条件，转而去找 \(a_i>a_j<a_k\)。如果我们能不断缩小范围直至 \(a_{j-1}>a_j<a_{j+1}\)，那么就找到了。
假设我们已经知道了一个区间 \([l,r]\) 满足 \((l,r)\) 之间的数都比 \(\min(a_l,a_r)\) 更小，为了缩小范围，考虑二分 \([l,r]\) 中点 \(m\)，考察 \(a_m\) 与 \(a_{m+1}\) 的大小关系。如果 \(a_m<a_{m+1}\)，那么 \([l,m]\) 就是更小的。否则，\((m,r]\) 也是更小的。于是我们可以二分，只需要 \(\mathcal{O}(\log n)\) 次询问，远远不到 \(100\) 次。
CF1479B1 Painting the Array I
可以直观地想到一个贪心。
维护两个队列存下标，令队尾分别为 \(x,y\)。如果 \(a_x=a_i\) 或者 \(a_y=a_i\) 就扔到另一个队列里即可。细节的问题在于 \(a_x \neq a_i\) 且 \(a_y \neq a_i\)，这时候我们需要斟酌一下怎么放。
考虑维护 \(\text{nxt}(i)\) 表示 \(i\) 后面第一个 \(a_x=a_i\) 的下标 \(x\)。贪心地考虑，如果 \(\text{nxt}(x) < \text{nxt}(y)\)，那么后面可能更有机会通过别的值切断 \(y\)，于是这次机会可以给 \(x\)。可以说明这样是对的。
维护过程中保证两个队列内没有重复元素，最后输出两个队列的大小之和即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1479B2 Painting the Array II
可以用类似地方法贪心。只不过把上一题的策略反过来。
如果 \(a_x=a_i\) 或者 \(a_y=a_i\) 就直接扔进对应的队列里，否则根据 \(\text{nxt}\) 判断，把 \(i\) 扔进 \(\text{nxt}\) 更大的队列里，这样是更劣的。
时间复杂度 \(\mathcal{O}(n)\)。
CF1479C Continuous City
看到 \(32\) 个点，考虑二进制构造。
先考虑构造 \([0,2^k-1]\) 的所有边，那么就是让 \(i\) 号点向后面所有点连 \(2^{i-1}\) 的边，经过这个点就是这一位上取 \(1\)，否则就是不取。那么从任意点到终点的一条路径就对应了一个 \([1,2^k-1]\) 中的值。
因为我们要固定起点，于是建一个超级源点，向每个点连长度为 \(L\) 的边。这样就得到了 \([L,L+2^k-1]\) 中所有的长度，同时每个点都恰好有 \([L,L+2^i-1]\) 所有边恰一条。
然而 \(R\) 不一定恰好为 \(L+2^x-1\)，于是我们再建一个超级汇点，对 \(R-L\) 进行二进制拆分，对于其第 \(i\) 位上的 \(1\)，先让 \(R\leftarrow R- 2^i\)，从表示 \([L,L+2^i-1]\) 的点向汇点连 \(R+1\) 的边。
时间复杂度 \(\mathcal{O}(\log^2 V)\)。
CF1479D Odd Mineral Resource
不难想到异或，只需要把 \((u,v)\) 路径上区间 \([l,r]\) 的颜色全都异或起来，不为 \(0\) 则存在这样的颜色。问题在于异或和为 \(0\) 时不能说明不存在，比如 \(1 \oplus 2 \oplus 3=0\)。
这么做为什么会错？原因在于值域太小了，相撞的概率很大。于是考虑随机赋值，给每个颜色重新标一个编号，这样再相撞的概率大大减小。
现在的问题变成了，静态查询一条路径上在某个区间的颜色的异或和。差分一下，转成只查询到根路径上的答案，用主席树维护即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
1604 (Div. 2)
CF1604A Era
对于每一个 \(a_i>i\)，可以通过在 \(a_i\) 前面插入 \(a_i-i\) 个数把 \(a_i\) 挤到合法的位置上。
容易说明这同时也是最小的操作次数，故答案为 \(\max\limits_{1\leq i\leq n}\{a_i-i\}\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1604B XOR Specia-LIS-t
若序列长度为偶数，则把整个序列都切成长度为 \(1\) 的子序列就满足要求了。
若序列长度为奇数，且存在 \(a_i\leq a_{i+1}\)，那么我们把 \(a_i\) 和 \(a_{i+1}\) 切成一组，其他数都单独分组，答案同样为偶数个 \(1\) 异或起来，满足要求。
若序列长度为奇数且单调递增，则无论怎么切一定有奇数个长度为奇数的序列。这些数的二进制最低位共有奇数个 \(1\)，异或起来一定不为 \(0\)。故不可能合法。
时间复杂度 \(\mathcal{O}(n)\)。
CF1603A Di-visible Confusion
先考虑模拟这个过程。
- 每一次删掉从末尾开始的连续段对答案没有影响，可以先删掉。
- 再考虑此时最后一个能删掉的位置，把它删掉之后会让后面所有数向前挪一位。
重复这样一个过程，会发现其实每一个 \(a_i\) 都会尝试在 \(1,2,3,\cdots,i\) 位置上被删掉。如果不能删空，说明对于所有 \(1\leq k\leq i\) 都有 \((k+1)\mid a_i\)，等价于 \(\mathrm{lcm}(2,3,\cdots,i+1)\mid a_i\)。
预处理 \(\leq 10^9\) 的前缀 \(\mathrm{lcm}\)，逐一判断即可。赛时因为除数为零吃了两发罚时。
时间复杂度 \(\mathcal{O}(n)\)。
CF1603B Moderate Modular Mode
需要一定的数学直觉。
先注意到若 \(n<x\)，则 \(n\bmod x=n>y\bmod n\) 矛盾，从而 \(n\geq x\)。
考虑 \(x\) 和 \(y\) 的大小关系：
- 若 \(x=y\)，则令 \(n=x=y\) 显然成立。
- 若 \(x>y\)，只能 \(n\geq x>y\)。此时 \(n\bmod x=y\)，令 \(n=x+y\) 即成立。
- 若 \(x<y\)，
- 若 \(x<y\leq n\)，则 \(y\bmod n=y>x>n\bmod x\)，不成立。
- 若 \(x\leq n<y\)，考虑 \(z=y-y\bmod x\)。在数轴上找到区间 \([z,y]\) 的中点 \(p=\dfrac{y+z}{2}\)，画一画发现 \(p\bmod x=p-\left\lfloor\dfrac{y}{x}\right\rfloor x=\dfrac{y\bmod x}{2}=y-p=y\bmod p\)，说明此时的 \(p=y-\dfrac{y\bmod x}{2}\) 即为答案。
时间复杂度 \(\mathcal{O}(1)\)。
CF1603C Extreme Extension
先考虑一个确定的序列 \(a\) 怎么算最少的操作次数。可以得到一个贪心策略：从后往前扫，如果 \(a_i > a_{i+1}\) 就尽量把 \(a_i\) 摊平。通过 \(\left\lceil\dfrac{a_i}{a_{i+1}}\right\rceil-1\) 次操作可以将 \(a_i\) 分得尽可能平均。
可以发现，这个过程只与当前序列的最小值有关，于是我们从这个角度设计 dp。
令 \(f(i,x)\) 为有多少个 \(i\) 开头的子串经过分裂后的最小值为 \(x\)。对于 \(a_i\) 的转移，考虑分裂出的份数 \(s=\left\lceil\dfrac{a_i}{a_{i+1}}\right\rceil\)，最小值会变为 \(y=\left\lfloor\dfrac{a_i}{s}\right\rfloor\)，从而 \(f(i+1,x)\to f(i,y)\)。
考虑统计答案，会发现这一次的分裂会在 \(i \times f(i+1,x)\) 个序列中产生贡献，并且分裂了 \(s-1\) 次，从而对答案的贡献为 \(i\times (s-1)\times f(i+1,x)\)。
这样看，时间复杂度 \(\mathcal{O}(nV)\)。然而根据数论分块相关的知识，\(x\) 只有 \(\mathcal{O}(\sqrt{V})\) 种。我们用一个 vector 把所有转移点装起来，就可以做到 \(\mathcal{O}(\sqrt{V})\) 的转移。
时间复杂度 \(\mathcal{O}(n \sqrt{V})\)。
1623 (Div. 2)
CF1623B Game on Ranges
把所有区间按照左端点从小到大为第一关键字，右端点从大到小为第二关键字排序。
这样对于同一个左端点的区间，他们右端点单调递减，每次 Bob 在当前区间内选的位置必然是下一个更短区间的右端点 \(+1\)，直到区间长度 \(=1\)。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1623C Balanced Stone Heaps
最小值最大，容易想到二分答案。
对于当前二分出来的最小值 \(x\)，从前往后放石子不好做，考虑从后往前模拟这个过程。
用一个辅助数组 \(t_i\) 表示当前第 \(i\) 堆石子的个数。由于倒着做是先获得石子再往前给，所以实际过程中至多往前放 \(h_i\) 个，故第 \(i\) 堆最多能往前放 \(\min\{h_i,t_i-x\}\) 个。
过程中如果 \(t_i<x\) 即失败。最后 \(t_1\geq x\) 且 \(t_2\geq x\) 即成立。
时间复杂度 \(\mathcal{O}(n\log h_i)\)。
CF1623D Robot Cleaner Revisit
CF1623E Middle Duplication
1632 (Div. 2)
CF1632A ABC
容易发现如果 \(0\) 或 \(1\) 的出现次数 \(\geq 2\) 则必然会产生回文串。计数即可。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #216559591 - Codeforces
CF1632B Roof Construction
考虑从高位贪心。设 \(2^t<n\leq 2^{t+1}\)，令 \(k=2^t\)，即令 \(k\) 为 \(n-1\) 以内最大的 \(2\) 的幂。
设 \(x,y\) 满足 \(0\leq x<k\leq y<n\)。注意到若 \(x\) 与 \(y\) 相邻，则 \(x\oplus y\) 二进制第 \(k\) 位上一定为 \(1\)，故 \(x\oplus y\geq k\)。所以我们希望把 \(\leq k\) 的数放到一边，把 \(>k\) 的数放到另一边，中间以 \(k\) 作为间隔。
考虑形如 \(n-1,n-2,\cdots,k+1,k,0,1,\cdots,k-1\) 的构造，答案不超过 \(k+1\)，一定是最优的。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #216559752 - Codeforces
CF1632C Strange Test
好像是个错解？但是过了。
注意到 \(a\operatorname{or}b\geq b\)。在进行一次操作三之后就只能让通过不断进行操作二使得 \(a=b\)，故可以推测最优解一定最多只进行一次操作三。
考虑三种情况：
- 不进行操作三，只使用操作一。
- 先不断使用操作二，直到 \(a\operatorname{or}b=b\)，使用一次操作三。
- 先使用 \(i\) 次操作一让 \(a\) 自增 \(i\)，使用一次操作三，再不断使用操作二。
第一种情况可以 \(\mathcal{O}(1)\) 计算答案，后两种情况为 \(\mathcal{O}(b)\)。故最终时间复杂度为 \(\mathcal{O}(b)\)。
Submission #216561825 - Codeforces
CF1632D New Year Concert
通过这个询问的形式，结合样例，可以猜到前 \(i\) 个数的答案可以由前 \(i-1\) 个的答案推得。
考虑固定前 \(i-1\) 个数，只需要考虑加入第 \(i\) 个数时是否需要修改。由于修改可以改成任意数，也就是说只需要考虑 \(i\) 到上一次修改的位置中间这段区间是否合法。
注意到固定右端点 \(r\)，随着左端点 \(l\) 的减小，\(\gcd(a_l,a_{l+1},\cdots,a_r)\) 单调不升，而 \(r-l+1\) 单调递增，故只能存在一个位置 \(l\) 满足 \(\gcd(a_l,a_{l+1},\cdots,a_r)=r-l+1\)。
维护一个指针 \(p\) 表示上一次修改的位置。计算 \(1\sim i\) 的答案，只需要让 \(p\) 向后扫。如果能够找到不合法的区间 \([p,i]\)，就修改 \(a_i\) 并更新答案和 \(p\) 的位置。否则直接继承 \(1\sim i-1\) 的答案。
区间 \(\gcd\) 可以用 ST 表预处理。时间复杂度 \(\mathcal{O}(n\log n\log a_i)\)。
Submission #216562055 - Codeforces
CF1632E1 Distance Tree (easy version)
CF1632E2 Distance Tree (hard version)
1634 (Div. 2)
CF1634A Reverse and Concatenate
注意到 \(s\) 加上其反串之后会变成回文串，而一旦 \(s\) 变成回文串，反串即等于自身，故后续的操作只会生成不断倍长这 \(1\) 种新串。
故当 \(s\) 不是回文串且 \(k\geq 1\) 时，会先生成两个不同的回文串，后续每个串只能生成一种新串，答案为 \(2\)。对于 \(k=0\) 或 \(s\) 本身是回文串的情况，答案为 \(1\)。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #216047910 - Codeforces
CF1634B Fortune Telling
\(x\) 和 \(x+3\) 的关系很松，唯一明显的关系只有奇偶性不同。
考虑异或是二进制下不进位加法，所以异或和加法对于末位的改变效果是一样的。也就是说，对于任意 \(a_i\) 进行加法和异或后的结果奇偶性相同，最后的结果奇偶性是确定的。
恰好 \(x\) 与 \(x+3\) 奇偶性不同，只需要判断最后结果的奇偶性即可。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #216047972 - Codeforces
CF1634C OKEA
不妨先从长度为 \(2\) 的子段考虑，发现任意一行的任意相邻两项奇偶性必须相同才能保证平均数为整数。这样整个数表应该以一行奇数一行偶数的方式填下去。
容易发现对于奇数行 \(1,3,5,\cdots\) 偶数行 \(2,4,6,\cdots\) 填的方法就是对的。只需要保证有偶数行即可。
时间复杂度 \(\mathcal{O}(nk)\)。
Submission #216048765 - Codeforces
CF1634D Finding Zero
输出两个位置，而 \(0\) 是序列唯一的最小值。想到输出的两个位置应该是序列的极值点。
考虑先不断询问 \((1,n,i)\)，找到极差最大的 \(i\)，设为 \(x\)。接着不断询问 \((1,x,i)\)，找到极差最大且编号最大的 \(i\)，设为 \(y\)。经过巨大分讨可以得到一个结论：\(0\) 一定出现在 \(\{a_1,a_{x},a_{y}\}\) 之中。
证明：设 \(M=\max\limits_{i=1}^n\{a_i\}\)。考虑如下情况：
- \(\{a_1,a_n\}=\{0,M\}\)。此时每一次询问 \((1,n,i)\) 都会得到 \(M\)，且满足 \(y=n\)。此时 \(0\) 必然存在于 \(\{a_1,a_y\}\) 之中，结论成立。
- \(\{a_1,a_n\}\) 中只存在 \(0\)。此时 \(a_{x}=M\)。
- 若 \(a_1=0\)，结论成立。此时每一次询问 \((1,x,i)\) 都会得到 \(M\)。
- 若 \(a_n=0\)，则有 \(y=n\)，结论成立。
- \(\{a_1,a_n\}\) 中只存在 \(M\)。此时 \(a_x=0\)，结论成立。
- 若 \(a_1=M\)，此时每一次询问 \((1,x,i)\) 都会得到 \(M\)。
- 若 \(a_n=M\)，则有 \(y=n\)。
- \(\{a_1,a_n\}\) 中不存在 \(0\) 或 \(M\)。画一个表示值域的数轴，可以感性说明 \(a_x\) 和 \(a_y\) 应该分别在数轴的两端。故 \(0\) 必然存在于 \(\{a_x,a_y\}\) 中，结论成立。
证明过程中已经给出了每种情况成立的条件。按照上述方法只需要 \(2n-4\) 次询问，可以通过。
注意交互格式。
Submission #216090646 - Codeforces
（todo）CF1634E Fair Share
CF1634F Fibonacci Additions
非常精妙的一道题。
首先令 \(c_i=a_i-b_i\)，只需要关心 \(c_i\) 是否全部为 \(0\) 即可。
区间加减不难联想到差分。但是不能直接差分，我们需要一个”类差分“使得修改的复杂度降维。
回顾差分的过程，令 \(\Delta x_i=a_i'-a_i\)，可以差分是因为相邻两项的增量 \(\Delta x_i=\Delta x_{i-1}\)。故后一项减前一项正好抵消。
在这个问题中，相邻两项的增量满足 \(\Delta x_i=\Delta x_{i-1}+\Delta x_{i-2}\)，此时想要抵消需要后一项减去前两项。故设计一个”类差分“序列 \(d_i=c_i-c_{i-1}-c_{i-2}\)。这样在区间 \([l,r]\) 加减斐波那契数列的修改就可以转化为在 \(d_l,d_{r+1},d_{r+2}\) 三个单点上的修改。实现了单次修改复杂度的降维。
判断全 \(0\) 加一个计数器即可。时间复杂度 \(\mathcal{O}(n+q)\)。
Submission #216053019 - Codeforces
1665 (Div. 2)
CF1665A GCD vs LCM
一开始想复杂了。
考虑到 \(\text{lcm}\) 是不可控的，于是我们尽量让 \(\text{lcm}\) 更小，直接填两个 \(1\) 进去。剩下的拆成两个互质的数，再拆一个 \(1\) 出来，就可以得到 \((1,n-3,1,1)\)。
时间复杂度 \(\mathcal{O}(1)\)。
CF1665B Array Cloning Technique
我们把一次复制数组的操作称为一次扩展，那么一次扩展将众数的数量翻倍是最优的。记录众数的数量，模拟这个过程即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1665C Tree Infection
容易发现，层与层之间是独立的，每个儿子的子节点都必须要注射过一次。
一个直观的想法是，先给儿子多的人的子节点注射，都注射了一轮之后，剩下的时间转过头去补齐儿子太多没感染完的点。我们只需要精细实现一下这样的过程。
具体来说，先把所有点按照儿子个数排序，那么第一轮注射只需要给所有儿子不为 \(0\) 的点都打上一边。这一轮肯定是从大到小打，因为越早打，后面提供给感染的时间更多。
后面的过程要处理该怎么拉平时间。维护一个堆，将所有点现在的儿子数量加进去，每次取最大值 \(-1\) 后扔回去，统计注射了几次。如果注射次数 \(\geq\) 最大值，说明已经感染完了，过程结束。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1665D GCD Guess
根据辗转相除，\(\gcd(x+a,x+b)=\gcd(x+a,b-a)\)。我们考虑利用 \(b-a\) 做一些事情。
一个直觉，我们选一些素数乘起来得到 \(M\)，如果每次询问能够保证 \(M=b-a\)，那么根据 \(x+a\) 与 \(M\) 的关系就可以构造出模方程，从而 CRT 暴力求解。
直接取 \(M=2\times 7\times 13 \times 17 \times 19 \times 23 \times 29 \times 31\)，这个数在 \([10^9,2\times 10^9]\) 之间，是符合要求的。询问 \(30\) 次 \((i,M+i)\)，这样可以得到 \(d=\gcd(x+i,M)\)。如果 \(d \neq 1\)，说明 \(x+i\) 是某个素数的倍数，也就得到了一个模方程。最后 CRT 合并即可。
CF1665E MinimizOR
结论：\([1,2^k)\) 的数按位或的最小值出现在前 \(k+1\) 小的数两两按位或之中。
证明：考虑数学归纳法。对于 \(k=1\) 成立，对于 \(k>1\)，讨论最高位有几个 \(0\)。
- 若当前最高位存在 \(\geq 2\) 个 \(0\)，则根据贪心策略，这一位为 \(0\)，最小值即为 \(k-1\) 时的最小值。根据归纳假设，最小值在前 \(k\) 小的数中。
- 若当前最高位没有 \(0\)，则这一位只能为 \(1\)，最小值即为 \(k-1\) 时的最小值加上这一位的贡献，根据归纳假设同理可证。
- 若当前最高位恰存在 \(1\) 个 \(0\)，则这一位只能为 \(1\)，类比上面的证明亦可说明。
于是暴力用线段树维护前 \(31\) 小值，时间复杂度 \(\mathcal{O}(q\log^2 V+n \log n \log V)\)。
1677 (Div. 1)
CF1677A Tokitsukaze and Strange Inequality
枚举 \(b,c\) 计算答案，那么只需要统计 \(\sum_{a<b}[p_a<p_c]\) 以及 \(\sum_{d>c}[p_b>p_d]\)，乘起来就是 \(b,c\) 的贡献。
做一个前后缀和即可。时间复杂度 \(\mathcal{O}(n^2)\)。
Submission #252060369 - Codeforces
CF1677B Tokitsukaze and Meeting
考虑对行列拆贡献。
对于一列来说，其中所有的学生都是模 \(m\) 余数相同的，因此其状态不会随着后进入的学生改变。我们可直接开一个桶记录下来每个模 \(m\) 的余数的类是否出现过严肃的学生，如果有，这一列在之后所有状态都会一直产生贡献。
对于一行来说，发现每 \(m\) 个学生进入就会增加一行，并且这 \(m\) 个学生对他们加入之前的队伍不会影响。于是我们再开一个桶，记录模 \(m\) 余 \(i\) 的学生站在每行第一个时的答案。同时记录 \(lst\) 表示其上一个严肃的学生的编号（可能是自己），如果 \(i-lst <m\) 说明这一行有严肃的学生。
最终的答案就是行列加和。时间复杂度 \(\mathcal{O}(nm)\)。
CF1677C Tokitsukaze and Two Colorful Tapes
我们把对位的颜色合并到一起，也就是在 \(a_i,b_i\) 之间连边，会得到一张由若干个环构成的图，现在的问题就变成了，在每个节点上填 \(1 \sim n\)，最大化每条边连接的两个点之差的绝对值之和。
容易想到大小间隔排列，并尽可能地让大减小。然而这样只对偶环有效，对于奇环，在多出来的一个位置上填一个靠中间的数即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1677D Tokitsukaze and Permutations
神秘计数。
首先可以说明，\(v\) 和 \(a\) 是一一对应的关系。因为对于任意一个 \(a\)，显然只能构造出唯一的 \(v\)，而对于任意一个 \(v\)，我们可以从后往前递推来还原 \(a\)。
考虑做一次冒泡的过程，对于 \(v\) 的改变相当于整体向前 shift 了一位，然后 \(v_i \leftarrow \max(v_i-1,0)\)。那么做完 \(k\) 次冒泡之后，\(v\) 的最后 \(k\) 位应该都为 \(0\)。
我们先来判无解。首先 \(v\) 最后 \(k\) 位都应该为 \(0\)，其次要求 \(v_i<i\)。
接下来考虑计数。因为 \(a\) 和 \(v\) 构成双射，所以我们考虑还原初始情况下的 \(v'\)，以此来得到 \(a\)。
对于 \(1 \leq i \leq k\)，\(v_i'\) 可以任取 \([0,i-1]\) 中的数。这一部分的贡献是 \(k!\)。
对于 \(k+1 \leq i \leq n\)，\(v_{i-k}=\max(0,v_{i}'-k)\)。如果 \(v_{i-k}=-1\) 则有 \(i\) 种选法，如果确定只有 \(1\) 种选法，否则 \(v_{i-k}=0\) 则有 \(k+1\) 种选法。
时间复杂度 \(\mathcal{O}(n)\)。
CF1677E Tokitsukaze and Beautiful Subsegments
1729 (Div. 3)
CF1729C Jumping on Tiles
发现当 \(a,b,c\) 单调时，\(|a-b|+|b-c|=|a-c|\)。进而能够得到答案为 \(|S_1-S_n|\)。
中间的落脚点肯定是介于 \(S_1\) 和 \(S_n\) 之间的，全都拿出来排个序就行了。
时间复杂度 \(\mathcal{O}(n\log n)\)。
Submission #176988191 - Codeforces
CF1729D Friends and the Restaurant
不妨令 \(c_i=x_i-y_i\)，这样一组可以一起吃饭的人需要满足 \(\sum c_i\geq 0\)。
贪心地考虑，肯定是希望大配小。并且由于希望组数最多，所以希望尽可能两个人配对。
对 \(c_i\) 升序排序，维护头尾指针 \(l,r\)，对于 \(r\) 找到最小的 \(l\) 使得 \(c_l+c_r\geq 0\)，让 \(l,r\) 配对即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
Submission #176988414 - Codeforces
CF1729E Guess the Cycle Size
神秘题。
注意到很重要的一点，询问 \((a,b)\) 和 \((b,a)\) 可能会得到不同的结果。而如果答案不同，说明整个环已经闭合上了，就得到了答案。
这就给我们一个启发。固定 \(a=1\)，枚举 \(b=2,3,\cdots,26\) 询问 \((a,b)\) 和 \((b,a)\)。由于两种回答是等概率的，这 \(25\) 组询问都问不出来的概率只有 \(2^{-25}\)，可以认为没有。
而一旦 \((a,b)\neq (b,a)\)，答案就是 \((a,b)+(b,a)\)。或者询问 \((1,i)\) 得到了 \(-1\)，答案就是 \(i-1\)。
Submission #176988731 - Codeforces
CF1729F Kirei and the Linear Function
小学都学过，模 \(9\) 的余数可以“乱切求和”。从而 \(v(l,r)\equiv a_l+a_{l+1}+\cdots+a_r\pmod 9\)。这样我们可以直接做前缀和，将长度为 \(w\) 的区间按照模 \(9\) 的余数分类。
对于一次查询，\(v(l,r)\) 已经确定了。考虑枚举 \(v(L_1,L_1+w-1)\) 模 \(9\) 的余数，计算得出 \(v(L_2,L_2+w-1)\) 模 \(9\) 的余数，再确定最小的 \(L_1,L_2\)。
时间复杂度 \(\mathcal{O}(n+m)\)。
Submission #175348303 - Codeforces
CF1729G Cut Substrings
先用字符串哈希把所有匹配位置找出来。设这些位置分别为 \(p_1,p_2,\cdots,p_k\)。
设 \(f(i)\) 表示消除掉前 \(i\) 个位置的最小步数。由于删除字符之后会留空，如果两次出现位置有交，只需要任意删掉一个位置就可以。
进而我们可以得到 \(f(i)\) 能更新的位置 \(j\)。
- \(p_j>p_i+m-1\)。
- 设 \(j_0\) 为最小的 \(j\) 满足 \(p_j>p_i+m-1\)，要求 \(p_j\leq p_{j_0}+m-1\)。否则直接删后面会跳过 \(j_0\) 这一次出现。
采用刷表转移，转移方程为 \(f(j)\leftarrow\min\{f(j),f(i)+1\}\)。在最佳转移点记录方案即可。
注意两个细节：
- dp 初始位置可能有很多个。因为消去第一次出现位置可能有很多方式，要都考虑进来。
- dp 结束位置可能有很多个。原因同理。
时间复杂度 \(\mathcal{O}(nm)\)。
1732 (Div. 2)
CF1732A Bestie
注意到对 \(n\) 和 \(n-1\) 都操作就一定可以满足要求了，所以答案不超过 \(3\)。
-
若只对 \(n\) 进行操作就可以满足，则代价为 \(1\)。
-
若只对 \(n-1\) 进行操作就可以满足，则代价为 \(2\)。
-
若对 \(n\) 和 \(n-1\) 都操作才可以满足，则代价为 \(3\)。
分别把三种情况判断一下就可以了，时间复杂度 \(\mathcal{O}(n)\)。
Submission #181876740 - Codeforces
CF1732B Ugu
翻转 \([l,n]\) 和 \([r+1,n]\) 能够达到翻转 \([l,r]\) 的效果，代价为 \(2\)。
先把开头极长的连续的 \(0\) 删掉，找到后面每一段极长的连续的 \(0\) 用两次操作翻成 \(1\) 即可。
翻 \(0\) 和翻 \(1\) 其实是一样的。考虑每一个 \(1\) 和 \(0\) 的分界处，把前面一段 \(1\) 翻成 \(0\) 和把后面一段 \(0\) 翻成 \(1\) 代价都为 \(1\)。所以只用考虑全都翻成 \(1\) 就可以了。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #181876811 - Codeforces
CF1732C1 Sheikh (Easy version)
考虑异或的性质，容易发现异或可以理解为二进制下不进位加法，从而扩展区间大小一定不会使价值变小，也就是说选的数越多越好。
进而最大价值一定为 \(f(1,n)\)，只需要最小化区间长度。
考虑固定左端点，则扩展右端点时价值是单调不降的。所以可以固定左端点，二分右端点。
时间复杂度 \(\mathcal{O}(n\log n)\)。
Submission #181876435 - Codeforces
CF1732C2 Sheikh (Hard version)
我们已经知道选更多的数价值一定不劣，所以每次询问的最大价值一定是 \(f(L_i,R_i)\)，仍然只需要最小化区间长度。
考虑从区间左右两边删数，删去的数需要满足 \(\sum x=\bigoplus x\)。
由于异或为二进制下不进位加法，所以对于每一个数位，至多只能有一个 \(x\) 在这一位上为 \(1\)。又因为值域 \(w\) 的限制，这样最多只能从左右共删掉 \(\mathcal{O}(\log w)\) 个数，可以暴力枚举。
注意到 \(0\) 是可以随便选的，但是如果左右有大量 \(0\) 会增加枚举的复杂度，所以可以提前把 \(0\) 先删掉，在新序列上枚举。
时间复杂度 \(\mathcal{O}(n+q\log^2w)\)。
Submission #182223267 - Codeforces
CF1732D1 Balance (Easy version)
维护全集 \(S\) 和每个数的 \(\operatorname{mex}\)。
- 添加操作，直接加入到 \(S\) 中。
- 查询操作，贪心地从上一次记录的 \(\text{mex}\) 开始枚举，找到第一个不在集合中的 \(t\times k\)，将其标记为 \(k\) 的 \(\text{mex}\) 并输出。这样做比 \(t\) 从 \(0\) 开始枚举要快很多。
Submission #181876541 - Codeforces
CF1732D2 Balance (Hard version)
在 D1 的基础上加入了删除操作。
考虑 \(x\) 被删除后，只可能作为 \(x\) 的因数的答案。同时，只有当 \(x\) 的某一个小于上一次记录的 \(\text{mex}\) 的倍数被删除时 \(x\) 的答案才会被更新。
对每个数 \(x\) 维护一个集合 \(M(x)\) 记录被删掉的 \(x\) 的倍数。同时维护集合 \(F(x)\) 记录 \(x\) 的因数。只有 \(M(x)\) 中的数可能成为 \(x\) 的答案。
- 添加操作，直接加入到 \(S\) 中。
- 删除操作，从 \(S\) 中删除 \(x\)，对所有 \(y\in F(x)\) 将 \(x\) 加入到 \(M(y)\) 中。
- 查询操作，在 \(M(x)\) 上暴力跳，对所有跳到的点 \(y\) 将 \(x\) 加入到 \(F(y)\) 中。查找 \(y\notin S\) 的最小的 \(y_{\min}\) 作为答案输出，并把过程中所有 \(y\in S\) 从 \(M(x)\) 中删除。
复杂度不会算。感觉是一个均摊 \(\mathcal{O}(q\log w)\)。
Submission #182242051 - Codeforces
1775 (Div. 2)
CF1775A2 Gardener and the Capybaras (hard version)
\(n\leq 2\times 10^5\)，不能暴力了。但是这是 2A，一定有简单的贪心做法。
考虑前三个字符：
- 若为
_a_，则可以将前两个字符单独各分成一段，\([3,n]\) 的字符分成一段。这样无论第三位上是什么，中间一段的字典序一定都是最小的。 - 若为
_ba，同理按上面的方式分组。这样无论第三位上是什么，中间一段的字典序一定都是最大的。 - 若为
abb，则可以将第一个a分成一段，最后一个字符分成一段，\([2,n-1]\) 分成一段。这样无论最后一个字符是什么，中间一段的字典序一定都是最大的。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #215442601 - Codeforces
CF1775B Gardener and the Array
如果恰有一个 \(c_i\) 在第 \(j\) 位上为 \(1\)，那么包含 \(c_i\) 的子序列和不包含 \(c_i\) 的子序列在第 \(j\) 位上必然不相等，两个子序列都必须同时包含 \(c_i\) 或同时不包含 \(c_i\)。也就是说，子序列 \(a\) 和 \(b\) 的选择的不同不能在是否选择 \(c_i\) 上体现出来。
如果对于每一个 \(c_i\) 都存在上述问题，那么 \(a\) 和 \(b\) 就只能相同，故必然失败。
对数位开个桶，枚举 \(c_i\) 的二进制位检查即可。
时间复杂度 \(\mathcal{O}\left(\sum k_i\right)\)。
Submission #215488817 - Codeforces
CF1775C Interesting Sequence
对每一个二进制位 \(j\) 单独考虑：
- 若 \(x\) 的第 \(j\) 位上为 \(1\)， 而 \(n\) 的第 \(j\) 位上为 \(0\)，则必然无解。
- 若 \(x\) 的第 \(j\) 位上为 \(0\)， 而 \(n\) 的第 \(j\) 位上为 \(0\)，则不需要考虑这一位。
- 若 \(x\) 的第 \(j\) 位上为 \(1\)， 而 \(n\) 的第 \(j\) 位上为 \(1\)，则要求 \([n,m]\) 所有数第 \(j\) 位上都为 \(1\)，故 \(m\) 需要小于第 \(j\) 位上为 \(0\) 且大于 \(n\) 的最小整数。
- 若 \(x\) 的第 \(j\) 位上为 \(0\)， 而 \(n\) 的第 \(j\) 位上为 \(1\)，则要求 \([n,m]\) 存在数第 \(j\) 位上为 \(0\)，故 \(m\) 需要大于等于第 \(j\) 位上为 \(0\) 且大于 \(n\) 的最小整数。
求第 \(j\) 位上为 \(0\) 且大于 \(n\) 的最小整数，只需要让 \(n\) 加上 \(2^j\)，并把第 \(0\sim j-1\) 位全部清零即可。
遍历每个数位之后，会自然得到一个 \(m\) 的取值区间。取区间最小值即可。
时间复杂度 \(\mathcal{O}(\log n)\)。
Submission #215810394 - Codeforces
CF1775D Friendly Spiders
直接暴力建图会产生 \(n^2\) 条边，不能接受。
考虑建一些虚点，每个图上的点向其质因数所在虚点连边，这样任意两个点权不互质的点可以通过一个虚点作为中转连通。然后就变成了一个裸的最短路问题。
关于开空间。注意到 \(2\times 3\times 5\times 7\times 9\times 11\times 13\times 17\times 19>3\times 10^5\)，所以只需要建 \(8\) 个虚点，每个点只会向不超过 \(8\) 个虚点连边。加上是无向图，故总边数在 \(16n\) 级别。
时间复杂度 \(\mathcal{O}(n\log n)\)。
Submission #215436105 - Codeforces
CF1775E The Human Equation
非常精妙的一道题。
单点 \(\pm 1\) 或许看着很随便。想到差分也是单点修改，不妨先对 \(a\) 做一遍前缀和，发现修改其实是在前缀和数组上对几段区间 \(\pm 1\)。最终状态是前缀和数组全为 \(0\)。
贪心地想，肯定正数不断 \(-1\) 负数不断 \(+1\) 次数更少，而我们一定可以通过选取某个子序列达到对当前所有正数/负数操作的效果。
那么使得正数全部变成 \(0\) 的最小操作次数即为最大的正数，使得负数全部变成 \(0\) 的最小操作次数即为最小的负数的绝对值。答案就出来了。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #215814125 - Codeforces
1851 (Div. 3)
CF1851B Parity Sort
由于交换操作是在奇数和偶数内部进行，所以奇数偶数所在下标的集合是不会改变的。
对整个序列排序，扫一遍判断下标集合有没有发生变化即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1851C Tiles Comeback
分情况讨论：
- 若 \(c_1=c_n\)，只需要记录整个序列是否有 \(\geq k\) 个 \(c_1\) 出现即可。
- 若 \(c_1\neq c_n\)，记录从前往后第 \(k\) 个 \(c_1\) 出现的位置 \(l\) 和从后往前第 \(k\) 个 \(c_n\) 出现的位置 \(r\)，若 \(l<r\) 说明可以接上，否则失败。
- 若 \(c_1\) 或 \(c_n\) 的出现次数 \(<k\)，必然失败。
时间复杂度 \(\mathcal{O}(n)\)。
CF1851D Prefix Permutation Sums
注意到前缀和序列的差分序列对应 \(1\sim n\) 的一个排列。我们对给定的 \(b\) 序列进行差分，记录没有出现的 \(1\sim n\) 的排列中的数。可能出现以下情况：
- 恰有 \(1\) 个数缺失。此时只有 \(b\) 中缺少 \(1+2+\cdots+n\) 这一项可能还原正确的序列，而这一项必然是前缀和序列的最后一项。其余的情况全部报告无解。
- 恰有 \(2\) 个数缺失。此时只有 \(b\) 的差分中出现的多余项恰为缺失的两项之和时合法。
- 其余情况报告无解。
时间复杂度 \(\mathcal{O}(n)\)。
CF1851E Nastya and Potions
看到这个先想到了这道题。
每个点向自己能合成的点连有向边。由于不会自己直接或间接合成自己，故整张图是一个 DAG。
每个点上维护 \(f(u)\) 表示得到 \(u\) 的最小代价，\(g(u)\) 表示合成 \(u\) 的最小代价。拓扑排序过程中删 \(u\) 的入边时先在 \(g(u)\) 上加，入度为 \(0\) 再令 \(f(u)\leftarrow\min\{f(u),g(u)\}\) 即可。
时间复杂度 \(\mathcal{O}(n+m)\)。
CF1851F Lisa and the Martians
注意到若 \(a_i\) 和 \(a_j\) 在第 \(p\) 位上相同，则可以令 \(x\) 在第 \(p\) 位上与他们相反使答案的第 \(p\) 位为 \(1\)。
考虑从高位贪心。建一棵 01-Trie，插入 \(a_i\) 之前计算对于 \(1\leq j<i\) 所有 \((a_i,a_j)\) 的答案。只需要每一位上尽量向相同的子树内走就可以了。构造 \(x\) 只需要让这一位取反。
时间复杂度 \(\mathcal{O}(nk)\)。
清空数组不要用 memset，把发生修改的位置清零就行了。
1856 (Div. 2)
CF1856C To Become Max
二分答案，考虑判定 \(\max a_i \geq x\) 是否能成立。
钦定 \(a_i=x\)，那么 \(a_{i+1} \geq x-1\)，\(a_{i+2} \geq x-2\) 一直到 \(a_n\) 都有一个下界要求。直接再暴力扫一遍 \([i,n]\) 算出最少要用几次操作，如果存在使用 \(\leq k\) 的操作次数能把 \(a_i\) 调到 \(x\) 就直接对了。
时间复杂度 \(\mathcal{O}(n^2 \log V)\)。
CF1856D More Wrong
给的信息是逆序对，逆序对和最大值有什么关系呢？所以我们要先找一个通过逆序对判定最大值的方法。
设全局最大值的位置在 \(p\)，考虑 \([1,i]\) 的逆序对会怎么变化。
- \([1,p]\) 的逆序对应该等于 \([1,p-1]\) 的逆序对。
- \([1,p+1],[1,p+2],\cdots [1,n]\) 的逆序对相较前一个都至少增加 \(1\)。
综合以上两点不难发现，\(p\) 是最后一个 \([1,p]\) 的逆序对不增加的点。推广到区间上，查找 \([l,r]\) 的最大值只需要扫一遍即可。
这样直接做的代价是 \(1^2+2^2+\cdots+(n-1)^2=\mathcal{O}(n^3)\)。我们还需要优化这个过程。
考虑分治，对于区间 \([l,r]\) 和中点 \(m\)，递归下去求得 \([l,m]\) 的最大值位置 \(p_l\) 和 \((m,r]\) 的最大值位置 \(p_r\)。因为 \(p_r>p_l\)，所以只需要询问 \([l,p_r-1]\) 的逆序对数是否等于 \([l,p_r]\)。如果等于，则 \(p_r\) 为 \([l,r]\) 的最大值，否则 \(p_l\) 为最大值。
考虑代价和，\(T(n)=2T(n/2)+\mathcal{O}(n^2)\)，加上常数算出来应该在 \(4n^2\) 级别，可以通过。
CF1856E1 PermuTree (easy version)
根据直观的贪心去感受，不难发现最优情况应该是将 \(u\) 的子树分成两类，一类的权值全部 \(< a_u\)，另一类的权值全部 \(>a_u\)。这样的贡献形如 \(\sum_{v \in S}sz_v\times \sum_{v\in T}sz_v\)。
不难发现，这其实就是一个背包。我们只需要找出最接近 \(sz_u/2\) 的分拆方法。对于每个点的子树都跑一遍背包，累加到答案中，就可以做到 \(\mathcal{O}(n^2)\)。
CF1856E2 PermuTree (hard version)
这一问中 \(n \leq 10^6\)，暴力背包就不可行了。
考察一下每个子树中的背包过程，可以发现 \(\sum sz_v =sz_u\)，从而本质不同的 \(sz_v\) 只有 \(\mathcal{O}(\sqrt{sz_u})\) 种。
这提示我们一个经典的维护手段，将本质相同的物品压在一起，变成多重背包，再二进制拆分，套上 bitset 优化可以把背包过程做到 \(\mathcal{O}\left(\dfrac{sz_u\sqrt{sz_u}}{w}\right)\)。
然而这个复杂度不一定对，会被一条链卡掉。于是考虑排掉重儿子的贡献，如果重儿子的子树大小超过了 \(u\) 子树大小的一半，那么直接让重儿子一组一定是最优选择。
时间复杂度 \(\mathcal{O}\left(\dfrac{n\sqrt{n}}{w}\right)\)。
这里有一个 trick，bitset 优化的复杂度保证来源于 bitset 的大小，也就是说每轮 dp 我们都需要不同大小的 bitset。于是有一个神秘倍增技巧，就是找最小的 \(2^k \geq sz_u\) 作为 bitset 的大小。
1861 (Edu)
CF1861B Two Binary Strings
注意到一个条件：每个串都是开头为 \(0\) 结尾为 \(1\)，所以最后整个串一定可以形成一个前缀 \(0\) 和一个后缀 \(1\) 的拼接。于是我们找这个分界点即可，即是否存在 \(a_i=b_i=0\) 且 \(a_{i+1}=b_{i+1}=1\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1861C Queries for the Array
观察到，如果一次 \(1\) 合法，则其所有前缀的答案都应该是 \(1\)。如果一次 \(0\) 合法，我们只需要关心其最早一次不满足升序是在什么位置。
考虑用两个指针 \(p,q\) 维护最后一次合法的 \(1\) 位置和最早一次合法的 \(0\) 位置。记录当前序列长度 \(L\)，对四种操作分类讨论：
- 加入。不能知道任何信息，\(L \leftarrow L+1\)。
- 删除。先令 \(L \leftarrow L-1\)。如果 \(L<q\) 说明不满足升序的位置被 pop 掉了，\(q \leftarrow 0\)。如果 \(L<p\) 说明少了一个升序的数，\(p\leftarrow p-1\)。
- \(0\)。如果此时 \([p=L][L \leq 1]=1\) 则不合法，否则如果 \(q=0\) 就更新 \(q=L\)。
- \(1\)。如果此时 \(q \neq 0\) 则不合法，否则更新 \(p=L\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1861D Sorting By Multiplication
先考虑不能乘负数怎么做。对于 \(i\) 依次判断，如果 \(a_i\leq a_{i-1}\) 就给整个后缀 \([i,n]\) 乘上一个数。
现在可以乘负数，于是我们钦定正负的分界 \(i\)。要把 \([1,i]\) 调成负数可以看作调成正数的过程反过来，于是我们扫一遍就可以得到答案。
时间复杂度 \(\mathcal{O}(n)\)。
CF1861E Non-Intersecting Subpermutations
钦定以 \(i\) 结尾的一个段，统计其出现次数，设为 \(f_i\)。
考虑容斥，没有限制的答案为 \(k!\times k^{i-k}\)。也就是 \((i-k,i]\) 填一个 \(1\sim k\) 的排列，前面随便填。因为元素不能重复使用，需要减去 \(j \in (i-k,i-1]\) 已经成了段的情况，从而有转移：
\[f_i=k!\times k^{i-k}-\sum_{j=i-k+1}^{i-1}f_j \times (i-j)! \]统计答案，\(i\) 之后的都随便填，从而有 \((n-i)!\) 种情况。
\[S=\sum_{i=0}^n f_i\times (n-i)! \]时间复杂度 \(\mathcal{O}(nk)\)。
1867 (Div. 2)
Dashboard - Codeforces Round 897 (Div. 2) - Codeforces
提交记录懒得粘过来了。
CF1867A green_gold_dog, array and permutation
考虑大小配对，让大数减小数，这样就能保证的得到的数互不相同了。
用个结构体记一下，排个序就行了。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1867B XOR Palindromes
考虑所有中心对称的数对 \((i,j)\)。如果 \(a_i\neq a_j\) 则必须要在 \(i,j\) 两个点上放恰一个 \(1\) 恰一个 \(0\)。设这样的数对有 \(x\) 个，则答案的下界为 \(x\)，上界为 \(n-x\)。否则，则 \(i,j\) 必须**同时放 \(1\) 或同时放 \(0\)。
由于回文中心的问题，不妨对 \(n\) 的奇偶性进行讨论。
- 当 \(n\) 为奇数，最中心的一位可以随便填，其他数对不改变奇偶性。从而能够构造出 \([x,n-x]\) 的所有答案。
- 当 \(n\) 为偶数，只能构造出 \([x,n-x]\) 中与 \(x\) 奇偶性相同的答案。
时间复杂度 \(\mathcal{O}(n)\)。
CF1867C Salyg1n and the MEX Game
注意到 Bob 拿出来的数需要严格小于 Alice 放进去的数，从而 Alice 可以通过放入更小的数来将 Bob 逼入死局。只需要让 mex 尽量大即可。
考虑第一次加入整个集合的 mex，后面 Bob 拿出来什么就把它填回去。这样答案一定不会变小。同时容易说明如果不这么做，当出现两个数的空缺后，答案一定会变小。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1867D Cyclic Operations
这个操作其实就是让 \(a_{l_i}=l_{i+1}\)，也就是一个环上的轮换。我们让 \(l_i\rightarrow l_{i+1}\) 连边。而操作区间可能有覆盖，意味着可能会把某个环上的一些点拆出来，去参与另一个环。
注意到在任意时刻，每个点的出边都是唯一确定的。所以在若干次操作后，这张图会变成一个基环树森林。而最后的状态相当于 \(i\rightarrow b_i\)，且恰存在一个环。
我们把最终状态的环拿出来，如果环的大小恰为 \(k\) 就是合法的，否则就是不合法的。
时间复杂度 \(\mathcal{O}(n+m)\)。
关于写法。最好先用一遍拓扑排序把不在环上的点先删了，这样能保证正确。
注意特判 \(k=1\)。
CF1867E1 & E2 Salyg1n and Array
当 \(n\bmod k=0\) 时，只需要每次询问连续的长度为 \(k\) 的段就可以得到答案。而当 \(n\bmod k\neq 0\) 时，这么做会剩下长度为 \(n\bmod k\) 的一段。
注意到查询后翻转区间的性质，而 \(n\) 与 \(k\) 均为偶数，说明 \(n\bmod k\) 也为偶数。
考虑先查询最后一段的前一半，也就是以 \(n-\dfrac{n\bmod k}{2}\) 为右端点的一段区间。这样会把这些数翻转到最前面，再查询最后 \(k\) 个数。会发现这样做每个数都恰被查询了奇数次，从而能够得到答案。
只需要 \(\left\lfloor\dfrac{n}{k}\right\rfloor+2\leq 51\) 次询问，可以同时通过 E1 和 E2。
1869 (Div. 2)
Dashboard - Codeforces Round 896 (Div. 2) - Codeforces
CF1869A Make It Zero
首先发现 \(n\) 为偶数时，只需要进行两次 \((1,n)\) 操作就可以将数组清零。
对于 \(n\) 为奇数，先做两次 \((n-1,n)\) 把 \(a_n\) 清零，再做两次 \((1,n-1)\) 就可以将所有数清零。
时间复杂度 \(\mathcal{O}(1)\)。
CF1869B 2D Traveling
曼哈顿距离告诉我们代价不超过一步从 \(a\) 走到 \(b\)。希望答案更小只能借助主要城市。
由于主要城市之间不花费代价，不妨钦定至多经过两个主要城市。预处理所有主要城市到 \(a,b\) 的距离，分别取最小值加起来即可。
时间复杂度 \(\mathcal{O}(n+k)\)。
CF1868A Fill in the Matrix
观察到每一列的 \(\operatorname{mex}\) 不超过 \(n\)，从而最终的答案不超过 \(n+1\)。又因为最多只有 \(m\) 种数，从而最终的答案不超过 \(m\)。只需要构造尽量达到上界即可。
一个自然的想法是按照循环同构的方式排下去。感性理解，循环同构让每一列的元素尽量轮换，从而每一列的 \(\operatorname{mex}\) 更容易出现不同的值，答案就更大。
- 当 \(n\leq m-1\) 时，按照循环同构排 \(n\) 行，答案即为 \(n+1\)。
- 当 \(n>m-1\) 时，按照循环同构排前 \(m-1\) 行，后面所有行都与前面某一行相同。此时每一列都恰少一个互不相同的元素，答案即为 \(m\)。
时间复杂度 \(\mathcal{O}(nm)\)。注意特判只有一列的情况。
有一个小 trick。令 \(a_{i,j}=(i+j-1)\bmod m\) 即可得到一个向前错一位的循环同构。
CF1868B1 Candy Party (Easy Version)
令 \(\overline a=\dfrac{\sum a_i}{n}\)。目标是将所有 \(a_i\) 调整成 \(\overline a\)。记 \(b_i=a_i-\overline a\)。
先讨论 \(b_i>0\) 的情况。对于 \(b_i<0\) 同理。
设每个人给出 \(2^x\) 得到 \(2^y\)，则有 \(b_i=2^x-2^y\)。对于不同 \(x,y\) 容易说明 \(2^x-2^y\) 都互不相同，所以 \(x,y\) 是唯一的。进一步发现，\(2^y=\operatorname{lowbit}(b_i)\)，\(2^x=b_i+2^y\)。
记 \(in_i\) 表示得到 \(2^i\) 的人数，\(out_i\) 表示给出 \(2^i\) 的人数，容易说明合法的必要条件是对于任意 \(i\) 都有 \(in_i=out_i\)。充分性不会证。
时间复杂度 \(\mathcal{O}(n\log a_i)\)。
CF1868B2 Candy Party (Hard Version)
令 \(\overline a=\dfrac{\sum a_i}{n}\)。目标是将所有 \(a_i\) 调整成 \(\overline a\)。记 \(b_i=a_i-\overline a\)。
先讨论 \(b_i>0\) 的情况。对于 \(b_i<0\) 同理。
与 B1 不同的是，此时每个人不一定都会得到一次给出一次。那么当 \(b_i=2^x\) 时，第 \(i\) 个人的情况就不确定了，既可以只给出 \(2^x\)，也可以给出 \(2^{x+1}\) 再得到 \(2^x\)。
我们把这种不确定的 \(x\) 记录下来，先钦定情况为给出 \(2^{x+1}\) 得到 \(2^x\)。如果 \(in_x\neq out_x\)，我们希望可以通过“调整”将其调成正确的。
具体地，将一个「给出 \(2^{x+1}\) 再得到 \(2^x\)」调整为「给出 \(2^x\)」会让 \(in_x\) 和 \(out_x\) 向其平均数靠拢，而会让 \(out_{x+1}\) 减少 \(1\)。如果 \(x\) 不确定的次数够多，就能够调整到 \(in_x=out_x\)。
时间复杂度 \(\mathcal{O}(n\log a_i)\)。
1875 (Div. 2) & 1874 (Div. 1)
CF1874A Jellyfish and Game
显然，每轮操作的人都会用自己手里的最小值换来对方手里的最大值。容易说明交换若干次之后，每一轮只会是全局最大值和全局最小值换来换去。
但是前几轮不一定是这样的。但是我想不清楚前几轮怎么做。那怎么办呢？
考虑模拟前 \(4\) 轮交换，把答案存下来。对于 \(\leq 4\) 次交换直接调用答案，更大的轮数根据先后手调用答案。这样就避免了思考。
时间复杂度 \(\mathcal{O}(n+m)\)。
CF1875C Jellyfish and Green Apple
先判断无解。如果能拆，每一个人的分量都是一堆 \(\dfrac{1}{2^i}\) 相加，那么分母肯定是 \(2\) 的幂次，也即 \(\dfrac{m}{\gcd(n,m)}\) 要为 \(2\) 的幂次。
考虑每一轮的过程：
- \(n\) 个苹果，全部切成两份，得到 \(2n\) 份苹果。
- 每人分得 \(\left\lfloor\dfrac{2n}{m}\right\rfloor\) 份，余下 \(2n\bmod m\) 份。
- 令 \(n\leftarrow 2n\bmod m\)。
由于保证了 \(m\) 为 \(t\times 2^k\)，容易说明这样一定是可以做完的。直接模拟就可以了。
时间复杂度 \(\mathcal{O}(\log m)\)。
CF1875D Jellyfish and Mex
考虑在 \(\text{mex}\) 减到 \(0\) 之前，每次都会找一个 \(x<\text{mex}\) 并将 \(x\) 全部删掉。容易说明这样做是最优的。
进而，由于集合的 \(\text{mex}\) 一定单调不增，我们删去的 \(x\) 也是单调不增的。
考虑利用这件事情设计 dp。令 \(f(i)\) 表示当前 \(\text{mex}=i\) 且没有删任何 \(x<i\) 的最小 \(m\)。记 \(cnt_x\) 为 \(x\) 的出现次数。枚举 \(j<i\) 作为下一次删掉的数转移即可。
\[f(j)\leftarrow\min\{f(j), f(i)+(cnt_j-1)\times i+j\} \]时间复杂度 \(\mathcal{O}(n^2)\)。
Submission #226130410 - Codeforces
CF1874B Jellyfish and Math
trick：看到这种乱七八糟，状态之间很难看出什么关联的题，可以考虑最短路。
CF1874C Jellyfish and EVA
CF1874D Jellyfish and Miku
1883 (Div. 3) & 1887 (Div. 1)
CF1883D In Love
查询是否存在两条线段没有交集只需要判断是否所有线段有公共的交集，如果有就是不存在。
用线段树大力维护所有位置的覆盖次数，只需要做区间加区间最大值。
时间复杂度 \(\mathcal{O}(q \log q)\)。
CF1883E Look Back
考虑计算每个数相较于前一个数要多乘几次 \(2\)，也就是除法下的差分。两次前缀和就可以得到答案。
但是差分可能有负数。负数的意义是，可以少乘几次 \(2\)。但是前缀和不能有负的，所以要对 \(0\) 取 \(\max\)。
时间复杂度 \(\mathcal{O}(n \log V)\)。
CF1883F You Are So Beautiful
观察到一个区间 \([l,r]\) 合法，当且仅当 \(l\) 是 \(a_l\) 最靠左的出现位置，且 \(r\) 是 \(a_r\) 最靠右的出现位置。
维护一个前缀和就可以随便查询了。
时间复杂度 \(\mathcal{O}(n)\)，但是赛时好像写了树状数组，导致多了 \(\log\)。
CF1883G1 & G2 Dances
对于 \(m=1\) 的情况，注意到答案具有单调性，二分 \(k\)，保留 \(a_i\) 中最小的 \(n-k\) 个与 \(b_i\) 中最大的 \(n-k\) 个，对位比较即可。只需要预先排序一次。
时间复杂度 \(\mathcal{O}(n \log n)\)。可以通过 G1。
对于 \(m>1\) 的情况，观察到 \(a_1\) 的变化至多会让答案增加 \(1\)。因为如果 \(a_1\) 太大了，多删一个就好了。
设 \(a_1=1\) 时的答案为 \(x\)，\(a_1=y\) 时的答案为 \(x+1\)，那么 \(y\) 也可以二分出来。
于是得到了一个二分套二分的做法，外层二分 \(y\)，内层二分 \(x\) 即可。
时间复杂度 \(\mathcal{O}(n \log n \log m)\)。可以通过 G2。
CF1887B Time Travel
直观感受，很像一个变种的最短路算法。
仍然令 \(d_u\) 表示走到 \(u\) 的最短时刻，那么 \(u \to v\) 能走当且仅当 \(v\) 在 \(\geq d_u+1\) 的时刻可以通行。设其最小的可以通行时刻为 \(T\)，则有 \(d_v \leftarrow \min(d_v,T)\)。
对每个点向外连的边标记上属于哪个点集，同时对于每个点集标记其在哪些时刻是可以通行的。这样最短路过程中只需要二分最小通行时刻。
时间复杂度 \(\mathcal{O}(n \log n+n \log k)\)。
CF1887C Minimum Array
放在差分序列上考虑，变成单点修改。可以发现，比较原序列的字典序就是在比较差分序列的字典序。
设当前时刻为 \(i\)，动态维护最优时刻 \(t\)。对于 \((t,i]\) 对差分的修改，如果第一个不为零的位置 \(<0\)，那么 \(i\) 的字典序就会比 \(t\) 更小，从而可以更新答案。
于是只需要维护不为 \(0\) 的位置。可以发现被修改的端点只有 \(l\) 和 \(r+1\)，可以通过 set 维护。
时间复杂度 \(\mathcal{O}(n + q \log n)\)。
1884 (Div. 2)
CF1884B Haunted House
调成 \(2^i\) 的倍数就是把 \(i\) 位中的 \(1\) 都换出去。交换一个 \(1\) 可以看作把它和最靠右的一个 \(0\) 交换位置。
这样用一个 std::vector 把所有的 \(0\) 装起来，每次用 \(0\) 就从末尾弹一个即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1884C Medium Design
可以发现，如果一条线段覆盖了当前的最小值位置，那么一定不如不加入这条线段。因为无论它是否覆盖了最大值位置，都不会使得答案变优。
利用这个思想，我们不妨钦定最小值为 \(0\)，那么答案就是覆盖次数的最大值。考虑扫描线，扫到 \(i\) 时钦定 \(i\) 不被覆盖，那么需要撤掉所有覆盖了 \(i\) 位置的线段，同时加入所有 \(r<i\) 的线段。
把所有线段分别按照左右端点排序，端点离散化，用线段树维护区间加区间最大值即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1884D Counting Rhyme
只需要考虑是否有 \(a_k \mid \gcd(a_i,a_j)\)。记 \(f_i=0/1\) 表示 \(i\) 是否有因子在 \(a\) 中出现，那么答案就是
\[\sum_{i=1}^n \sum_{j=i+1}^n [f_{\gcd(a_i,a_j)}=0] \]考虑枚举 \(d\)，只需要计算有多少对 \(\gcd(a_i,a_j)=d\)。记这个数为 \(g_d\)，那么答案就是
\[\sum_{d=1}^V [f_d=0]g_d \]\(f_d\) 可以枚举因数 \(n \ln n\) 做。\(g_d\) 是经典容斥。先求 \(d \mid \gcd(a_i,a_j)\)，再依次减去 \(d\) 倍数的答案。
时间复杂度 \(\mathcal{O}(n \ln n)\)。
1886 (Edu)
CF1886B Fear of the Dark
分类讨论题，讨论清楚了就是容易的了。
如果用一个圆覆盖两个点，那么一个点的要求就是 \(\max\{d(A,O),d(A,P)\}\)。对 \(B\) 同理，取最小值即可。
如果用两个圆，需要讨论 \(A,B\) 分别去覆盖哪个点，同时为了连通，还要对 \(d(A,B)\) 取 \(\max\)。
两种情况的答案取最小值。
时间复杂度 \(\mathcal{O}(1)\)。
CF1886C Decreasing String
可以发现，每一轮删除的字符一定是最小的满足 \(S_i > S_{i+1}\) 的位置 \(i\)。暴力模拟 \(\mathcal{O}(n^2)\)。
考虑优化这个过程。每一轮只删一个字符却还要从头再扫一遍，是十分浪费的。发现删掉字符 \(i\) 之后可能会连锁地导致前面若干个字符被删掉。这个删除过程与单调栈很类似。
考虑用单调栈来优化。每次弹出一个字符相当于删去了这个字符，对应地让 \(pos\) 减少当前串的长度即可。注意实现细节，如果找不到，要删末尾的元素，所以可以手动在末尾加一个很小的字符。
时间复杂度 \(\mathcal{O}(n)\)。
CF1886D Monocarp and the Set
先考虑，对于初始状态的序列，怎么计数。会发现加数是不好处理的，而倒着删数是可以处理的。初始时我们有一个全集 \(\{1,2,3,\cdots,n\}\)，如果当前最后一个字符是 < 则移除最小值，> 则移除最大值，? 则移除非最值的任意一个数。移除最小值和最大值都只有一种方法，而移除非最值的数则有 \(|S|-2\) 种方法。
写成式子大概是 \(\prod (n-i-1)\) 的样子，然而你发现这个东西正着也是一样的，所以就是 \(\prod (i-1)\)。
这样，对于一个确定的序列，已经可以计数了。考虑修改字符的影响，会发现无非就是让一项 \((x-1)\) 和 \(1\) 互相转化。预处理 \([1,n]\) 的逆元就可以做了。
时间复杂度 \(\mathcal{O}(n)\)。
CF1886E I Wanna be the Team Leader
有些程序员可以不去，所以我们把 \(a_i\) 从大到小排序，这样只需要用尽量大的。
观察到，每个任务对应选择的一些程序员，在排完序后的序列上都是一段连续的区间。这一点可以通过交换两组中的人证明。必然有一组的答案变劣，而另一组不变。
考虑一个朴素的状压 dp。设 \(f(i,S)\) 表示是否能用前 \(i\) 个程序员解决集合为 \(S\) 的问题。这个 dp 是简单的，但是效率不高。我们尝试把 \(i\) 这一维去掉。
设 \(f(S)\) 表示解决了集合为 \(S\) 的问题，最少需要用掉 \([1,f(S)]\) 的程序员。为了实现这个转移，我们需要一个数组 \(g(i,j)\) 表示，从 \(j\) 开始的人做掉任务 \(i\)，最少需要选到 \(g(i,j)\)。这样转移可以写成：
\[f(S \cup \{k\}) \leftarrow g(k,f(S)+1) \]只需要预处理 \(g\)。又注意到 \(g(i,j)\) 关于 \(j\) 单调不降，可以双指针。
时间复杂度 \(\mathcal{O}(m2^m+nm+n\log n)\)。
1891 (Div. 2)
CF1891C Smilo and Monsters
可以发现，大招积攒的越多效果越好。最理想的情况是，手动清掉一半，大招清掉剩下的。但是这个是不可能达到的。
这个东西带来一些启发，我们最多通过大招处理掉总和的一半的人，并且越大的 \(a_i\) 清起来效果越好。于是按照 \(a_i\) 从大到小排序，能清掉的就直接清掉。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1891D Suspicious logarithms
打个表可以发现，答案的变化极其缓慢，并且答案的上界很小。
值得注意的是，\(g\) 并不是单调的。所以二分变化点的做法是完全错误的。考虑更朴素一点的做法，因为 \(f(x) \leq 60\) 并且 \(g(x) \leq 10\)，我们考虑枚举并钦定 \(f(x)\) 和 \(g(x)\) 的值。
\(f(x)=k\) 会指向一个区间 \([2^k,2^{k+1}-1]\)，\(g(x)=t\) 会指向一个区间 \([k^t,k^{t+1}-1]\)。这样真正能做出贡献的区间就是 \([2^k,2^{k+1}-1] \cap [k^t,k^{t+1}-1] \cap [L,R]\)，对答案的贡献就是区间长度乘上 \(t\)。
时间复杂度 \(\mathcal{O}(q \log^2 V)\)。
Submission #253872695 - Codeforces
CF1891E Brukhovich and Exams
可以发现，一次操作最多消除两个互质的数对。于是我们先扫一遍，把所有能消两个的都消掉，这样做一定是不劣的。
考虑到 \(1\) 很麻烦，于是我们先考虑 \(1\) 的事情。会发现如果存在形如 \(x111\cdots 11y\) 的情况，那么消掉中间所有的 \(1\) 会带来一次额外的贡献，也就是消掉 \(k\) 个 \(1\) 却消去了 \(k+1\) 个数对。
但是，开头和结尾的连续 \(1\) 是要特判的。如果开头存在 \(111\cdots 11x\)，为了让答案最大化，应该从 \(x\) 的一端从后往前删。同理，对于结尾的 \(x111\cdots11\)，应该从前往后删。
我们把 \(x11\cdots 11y\) 这样的段存起来，按照长度排序并依次选择。这些段都选完了之后，剩下的开头 \(1\) 和结尾 \(1\) 以及零散的点都是等价的，随便选就好了。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1891F A Growing Tree
见过最简单的 2F。
显然对树的形态进行动态修改是很难的，于是我们离线下来，先把最终形态的树建好。
一个点的点权只跟他被加入之后的操作有关，于是我们倒着处理所有操作，对于一次加点操作，直接根据确定掉这个点的答案，后续的修改一律忽略掉即可。dfs 序拍平，树状数组维护差分。
时间复杂度 \(\mathcal{O}(q \log q)\)。
1929 (Div. 2)
CF1929C Sasha and the Casino
感觉挺抽象的题。
因为有 \(x\) 次保底，所以只需要保证在保底及以前一定能回本即可。
设第 \(i\) 次下注 \(a_i\)，那么只需要
\[ka_i>\sum_{j=1}^ia_j \]改写一下就可以得到
\[a_i\geq \left\lfloor\dfrac{1}{k}\sum_{j=1}^{i-1}a_j\right\rfloor+1 \]这是一个递推形式，递推到 \(x+1\) 即可。要求任意时刻下注不超过 \(a\)。
时间复杂度 \(\mathcal{O}(x)\)。
CF1929D Sasha and a Walk in the City
先考虑找一个比较好的判据判定「不存在三个点在一条路径上」这件事情。可以发现，对于任意两个选中的点，如果他们在同一棵子树内，则不能是祖孙关系。
考虑路径拼接类树形 dp。设 \(f(i,j)\) 表示以 \(i\) 为根的子树中，从 \(i\) 向子树内的链至多经过 \(j\) 个被选中的点的方案数。显然有 \(j \in \{0, 1,2\}\)，并且 \(f(i,0)=1\)。
对于 \(f(i,1)\)，其每个儿子 \(j\) 向上发出的链上都不能有超过 \(1\) 个被选中的点，可以任选拼起来，从而这里的转移应该是乘法。
\[f(i,1)=\prod (1+f(j,1)) \]对于 \(f(i,2)\)，如果有两条 \(\geq 2\) 的链拼起来就不合法了，并且选 \(u\) 可以和子树中 \(1\) 的链拼成 \(2\) 的链，从而这里的转移应该是加法。
\[f(i,2)=\sum f(j,1)+f(j,2) \]答案为 \(f(1,0)+f(1,1)+f(1,2)\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1929E Sasha and the Happy Tree Cutting
对于每条边 \(e\) 记 \(w(e)\) 表示 \(e\) 能覆盖到的路径集合，这个东西可以通过树上差分预处理出来。
考虑一个暴力 dp。设 \(f(S)\) 表示覆盖了集合 \(S\) 的路径的最小代价，枚举加入一条边 \(e\) 进行转移。
\[f(S\cup w(e)) \leftarrow \min\{f(S \cup w(e)),f(S)+1\} \]这样是 \(\mathcal{O}(n2^k)\) 的。
我们对 \(k\) 条路径的端点建虚树，那么虚树大小为 \(\mathcal{O}(k)\)，说明本质不同的 \(w(e)\) 只有 \(\mathcal{O}(k)\) 种。
我们只在这些本质不同的 \(w(e)\) 中进行转移，时间复杂度 \(\mathcal{O}(k2^k+n)\)。
CF1929F Sasha and the Wedding Binary Search Tree
对二叉搜索树中序遍历，应该得到一个单调不降的序列。
不妨令 \(a_0=1\)，\(a_{n+1}=C\)。把每个 \(-1\) 构成的连续段提出来，设其长度为 \(k\)，前一个数为 \(L\)，后一个数为 \(R\)，只需要计数长度为 \(k\) 且每个数均在 \([L,R]\) 内的单调不降序列个数。
这是个经典问题。考虑差分，相当于把不超过 \(R-L\) 个 \(1\) 分到 \(k\) 个位置上去，每个位置可以为空。容易通过组合数递推得到答案。
\[\sum_{i=0}^{R-L}\binom{i+k-1}{k-1}=\binom{R-L+k}{k} \]注意到 \(C\) 可能很大，而 \(\sum k \leq n\)，所以我们直接暴力算组合数即可。
时间复杂度 \(\mathcal{O}(n)\)。
1936 (Div. 1)
CF1937B Binary Path
只有一次向下走的机会，因此一条路线一定是在第一行走一段后换到第二行走完。
考虑贪心，每次在右边和下边选一个更小的格子走。如果相同，可以发现向右走优先级比向下走要高，因为向右走后面还有向下调整的机会，所以向右。这样就能得到一条路径。
考虑怎么计算不同的路径数量，只需要算出最早可能的换行位置 \(l\) 和最晚可能的换行位置 \(r\)，答案就是 \((r-l+1)\)。\(r\) 可以从后往前扫，可以换行就往前跳。\(l\) 从前往后扫，处理类似。
时间复杂度 \(\mathcal{O}(n)\)。
Submission #250616582 - Codeforces
CF1936A Bitwise Operation Wizard
可以通过询问 \(x\operatorname{or} x\) 进行比大小的操作，也就是可以找到 \(n-1\)。设其位置在 \(t\)。
注意到，设 \(2^k \leq n-1<2^{k+1}\)，则答案就是 \(2^{k+1}-1\)。因为我们一定要取一个高位，不妨用一个 \(n-1\)，只需要找另一个数的位置。
可以发现，满足异或和为 \(2^{k+1}-1\) 的数对一定也满足或起来为 \(2^{k+1}-1\)，也就是与 \(n-1\) 的或最大。通过询问 \((i,t,j,t)\) 可以找到这些数，设它们构成集合 \(S\)。
现在要异或和最大，也就是与 \(n-1\) 的交集为空，容易发现这个数是 \(S\) 中最小的。再通过询问自己的操作找到最小值即可。
总共需要三轮询问，每轮找最值只需要 \(n-1\) 次，总次数不超过 \(3n-3\)，可以通过。
Submission #250625692 - Codeforces
CF1936B Pinball
双倍经验 CF733E。
通过模拟可以发现，一个球被反弹的次数只与它左边的 > 和右边的 < 有关，称这些位置为关键点。每个关键点会恰好让这个球反弹一次。可以把它理解为弹砖块的游戏，关键点都是砖，会让小球弹回去一次，同时砖块也会被消掉，下次再经过就畅通无阻了。
这件事情告诉我们，只需要对于每个 \(i\) 记录其左右关键点的信息，整个过程就是确定的。
考虑用前缀和统计两类点的信息，这个过程就是在每一对关键点之间折返，如果左边反弹的多那么就会从右边出去，反之同理。每一对之间都会带来形如 \(r_i-l_i\) 的贡献，对于 \(l,r\) 拆开分别用前缀和统计，最后在根据起始方向讨论一下即可。
时间复杂度 \(\mathcal{O}(n)\)。细节可以看提交记录。
CF1936C Pokémon Arena
令 \((i,j)\) 表示使用了 \(i\) 的 \(j\) 属性。
观察到，不会出现先用 \((y,i)\) 击败 \((x,i)\)，再用 \((z,i)\) 击败 \((y,i)\) 的情况。因为这样多付出了 \(c_y\) 的费用，并且提升 \(y\) 和 \(z\) 的能力的费用不小于直接提升 \(z\) 的能力。这件事情告诉我们，\((y,i)\) 击败 \((x,i)\) 需要提升的能力永远是 \(\max(0,a_{y,i}-a_{x,i})\)。
考虑图论模型，把每个人当成点，点权为 \(c_i\)。\((y,i)\) 向 \((x,i)\) 连边的边权为 \(\max(0,a_{y,i}-a_{x,i})\)。点权拆到边上，\(n \to 1\) 的最短路就是答案。
但是这样边数有 \(n^2m\) 条，太多了。考虑对于每一种属性 \(i\)，按照 \(a_{x,i}\) 排序，这样只需要在相邻的点之间连边，走一条链会把中间的点的贡献都抵消掉。
梳理一下建出来的图长什么样子：
- 一共有 \(n\times(m+1)\) 个点，\(n\) 个入点 \(1 \sim n\) 和 \(n\times m\) 个出点。
- 每个入点 \(i\) 向其 \(m\) 个出点连权值为 \(c_i\) 的边表示雇佣费用，反过来连权值 \(0\) 的边。
- \(m\) 个属性对应 \(n\) 个出点，按照 \(a\) 排序，相邻点 \(a_{x,i}\) 向 \(a_{x+1,i}\) 连权值为 \(a_{x+1,i}-a_{x,i}\) 的边表示提升能力的费用， 反过来连权值为 \(0\) 的边。
这样就只有 \(nm\) 条边了，跑 dij 的复杂度为 \(\mathcal{O}(nm \log (nm))\)。
Submission #250642846 - Codeforces