CF1329D Dreamoon Likes Strings
将原序列中 \(s_i=s_{i+1}\) 的位置拿出来，记这些位置的集合为 \(S\)。
考虑我们选择 \(S\) 相邻两个数，并且删除中间这一段会产生什么影响。如果两边的数不同，那么这两个位置都会在 \(S\) 中消失，否则，会在 \(S\) 中新加入一个为这个数的位置。
我们总是希望能将对应的数不同的位置放在一起操作，容易发现，一个下界是 \(\max(\frac{|S|}{2},\max(S))\)，其中 \(\max(S)\) 表示 \(S\) 中出现次数最多的数的出现次数。
这个下界也是容易取到的：我们维护一个栈，栈内存还没操作的 \(S\) 中的位置。从小到大将 \(S\) 中的位置加入，如果当前栈顶和下一个所对应的数不同，并且没有数的出现次数大于一半或者这两个位置所对应的数是出现次数最多的，就操作这两个位置。这样就取到了下界。
CF1876F Indefinite Clownfish
首先，因为两个序列平均值相同，所以一定会有同样的元素。
不妨假设两个同样的元素位置是 \(x,y\)，其中 \(x\) 是上升序列中的，\(y\) 是下降序列中的，并且 \(x>y\)。
若 \(x,y\) 有一个是两个序列中的最后一个元素，则可以调整最后一个元素使其在这个值中是相邻的。
否则，考虑 \(x\) 在上升序列中的前一个元素 \(x'\)，\(y\) 在下降序列的后一个元素 \(y'\)。若 \(x'>y'\)，归纳下去，否则，则可以贪心地调整成 \(x',y'\) 相邻。因此，一定有一对相邻的相同值点。
我们枚举这对点是什么，然后考虑其向左和向右最小延伸的长度。一个值得注意的事情是，一个合法的选取方式需要满足两个序列开头的差恰好为 \(\frac{k}{2}-1\)，结尾的差也是如此，这样向左和向右最小延伸的长度就是独立的，就是两边分别跳到差为 \(\frac{k}{2}-1\)，写个倍增就可以做到 \(O(n\log ^2n)\) 了，需要分讨一下中间相同值的点是谁取到的。
为了满足上面假设的东西，需要将序列 reverse 和值 reverse 都再做一遍。
CF1586I Omkar and Mosaic
假设 \((1,1)\) 位置是 G，那么 \((1,2)\) 和 \((2,1)\) 肯定是 G。
考虑 \((2,3)\) 位置和 \((3,2)\) 位置，如果 \((2,2)\) 位置填了 G，那么这两个位置只能填 R。如果 \((2,2)\) 填了 R，这两个位置也只能填 R。因此这条斜线上就是交替的。
然后考虑 \((2,2)\) 位置，发现这个位置可以填 R 也可以填 G，但是如果填了 G，\((1,3)\) 和 \((3,1)\) 就得填 R。如果填了 R，\((1,3)\) 和 \((3,1)\) 就得填 G。这样 \((1,4)\) 和 \((4,1)\) 就得和 \((1,3)\) 和 \((3,1)\) 相同。然后又会产生对角线上的交替。
最后的等价类图大概长这样（贺的）：
就可以 \(O(n^2)\) 做了。
AGC053E More Peaks More Fun
不妨假设 \(A_i<B_i\)，我们先来考虑合法的放置方案数有多少，然后再去重。
注意到在一对来自同一个集合的元素中至多有一个峰，并且只要出现 \(B_i,A_i,A_j,B_j\) 这样的结构峰的数量就不会超过 \(n-2\)，因此整一个摆放的形态只能是形如 \(A_1,B_1,A_2,B_2\dots A_i,B_i,B_{i+1},A_{i+1} \dots B_n,A_n\) 的形式，并且对于前半部分，要求 \(B_i>A_{i+1}\)。对于后半部分，要求 \(A_i<B_{i+1}\)。
考虑插入法来计算这个事情，按照 \(B_i\) 的值从大到小插入。容易发现插入之后不会改变原来的合法性。一个 \(B_i\) 只能插入在一个 \(j\) 满足 \(B_j>B_i\) 并且 \(A_j<B_i\) 的旁边，具体哪边视 \(j\) 的插入情况定，或者以任意形态插在中间。记 \(t_i=\sum\limits_{j}[A_j<B_i\and B_i<B_j]\)，则合法的方案数为 \(\prod (t_i+2)\)。
然后我们考虑加点限制以达到只计算合法的排列数的目的。假设其是有 \(A_i,B_i,B_{i+1},A_{i+1}\) 这种形态的，如果没有方案数为 \(\prod(t_i+1)\)。不妨假设 \(i\) 为最后一个分界点，则需要满足 \(A_{i+1}>B_i\)。我们枚举 \(i,j\) 满足 \(B_i<A_j\) 来表示中间两个数是什么，则对于每个 \(k\)，其贡献分三类：
- \(B_k>B_j\)：\(t_k+2\)，其可以任意插入。
- \(B_i<B_k<B_j\)：\(t_k+1\)，其只能在中间的一侧插入。
- \(B_k<B_i\)：\(t_k\)，其不能往中间插入。
容易拆开贡献用前缀和计算，时间复杂度瓶颈在于求 \(t_i\) 的 \(O(n\log n)\)。
AGC048E Strange Relation
官方题解可以教你怎么比较自然（？）地想到最后一步。
但是如果你事先知道做法足够厉害，你可以尝试一下倒着构造这个序列。
考虑每次在序列头上插入一个数，对后面造成的影响。因为后面已经确定了大小关系，而插入一个数又只是对一段后缀 \(+T\)，所以不会改变相对顺序。
而最终我们需要最大化 \(x_i\) 的字典序，而我们加入一个 \(x\) 的时候，可以对所有 \(A_i+x_iT>x-T\) 的 \(x_i\) 都加上 \(1\)，并且后面加的越多，前面就加的越多，因此加入一个数之后对序列的变化是唯一的。
于是就可以设 \(dp_{i,j,k,p}\) 表示从后往前到了第 \(i\) 个数，在第 \(j\) 个位置插入的是序列 \(B_j\) 的第 \(k\) 个数，已经加了 \(p\) 次的方案数，转移是平凡的，容易 two-pointers 优化到 \(O(n^2k^2)\)。
CF223E Planar Graph
这个题有点牛的。
我们考虑平面上怎么判定一个点是否在一个多边形内：从这个点开始引一条射线，用“进入多边形的次数”减去“出多边形的次数”即为这个点是否在多边形内。
我们发现，在一般情况下所使用的射线是为了容易计算几何，而实际上任意一条向无穷延伸的连续曲线都是可以的。
而在这个题里我们不妨让其沿着已有的边走。考虑一棵生成树，以一个极值点为根，钦定每个点向其父亲走，走到根为止，则我们需要求的就是“从内部走到边界上的次数”减去“从边界上走到内部的次数”。
这样我们只需要考虑多边形上逆时针三个点围成的一个角被经过了多少次，而经过这个角的是中间那个点出边极角序上一段连续的区间，可以二分+预处理前缀和解决，我偷懒直接 find 过了（
CF1466I The Riddle of the Sphinx
有点牛大了。
记当前有 \(n\) 个数，数位长度为 \(m\)。
考虑维护一个栈，初始的时候栈内只有第一个数，并且我们问出第一个数的第一位。
然后考虑每次加入的一个数，设栈内有 \(len\) 个数。若加入的这个数在最高 \(len\) 位就大于栈顶了，就把栈顶扔了，如果小于栈顶，就把这个数扔了，否则放到栈里面去，并且把 \(len+1\) 位问出来。
然后最后我们得到了可能是最大值的一个栈，再把这个栈倒着像上面问一遍，最后栈内的数前 $len $ 位全部相同。这样就变成一个 \(len\) 个数， \(m-len\) 位的子问题了。
记 \(f(n,m)\) 表示 \(n\) 个数，\(m\) 位需要几步，有 \(f(n,m)=5n+f(len,m-len)\)，可以发现这东西至多是 \(5(n+m)\) 的了。
然后考虑优化。我们可以略微修改一下栈的定义，我们维护前 \(i\) 个最高位表示第 \(i\) 个数的最高 \(i\) 位不超过这个值，而不要求恰好等于。这样不影响最大值，但是正着和反着都可以少一次，就可以做到 \(3(n+m)\) 步了。
AGC050E Three Traffic Lights
记 \(m_i=g_i+r_i\)，首先可以转化为有多少 \(x_1,x_2,x_3\) 满足存在 \(t\bmod m_i=x_i\)，然后将答案乘上 \(\frac{m_1m_2m_3}{\operatorname{lcm}(m_1,m_2,m_3)}\) 即可。
对每个质数 \(p\)，记 \(m_i\) 中 \(p\) 的次数为 \(a_i\)，则对于 \(i\not=j\)，要满足 \(x_i\equiv x_j \pmod{p^{\min(a_i,a_j)}}\)，因此，对于最大的 \(a\)，可以将其不断减少直至与中位数相同，不会影响答案。考虑这样减少有什么好处，一个好处是，三个 \(m\) 可以被表示为 \(m_1=gab,m_2=gac,m_3=gbc\) 的形式，并且 \(a,b,c\) 两两互质。
列出答案的式子，是：
\[\sum\limits_{t=0}^{gabc-1} \prod\limits_{0\leq i\leq 2} (\lfloor\frac{g_i}{m_i}\rfloor+[t\bmod m_i<g_i\bmod m_i]) \]考虑将贡献拆开，最困难的部分显然是：
\[\sum\limits_{t=0}^{gabc-1} \prod\limits_{0\leq i\leq 2} [t\bmod m_i<g_i\bmod m_i] \]不妨设 \(m_1\leq m_2\leq m_3\)，一个观察是，对于 \(m_2\) 和 \(m_3\) ，其合法的 \(t\) 对应的区间是只有 \(b\) 个和 \(a\) 个的。而我们又有 \(c\geq b,gbc\leq 2\times 10^{12}\)，因此 \(c\leq \sqrt{2\times 10^{12}}\)。对于 \(c\) 同理。
所以暴力做 \(m\) 大的两个，最后一个直接计算即可。时间复杂度 \(O(\sqrt V)\)。
AGC057F Reflection
比较厉害的题。
首先这个只和中位数位置和两边的长度有关，而两边的长度是一个类似欧几里得的过程，所以可以预见的，在进行若干次操作之前，不同层的状态肯定不一样，在辗转相减到 \(\gcd\) 以后，两边的长度就一个是 \(0\) 一个是 \(\gcd\) 了。
记 \((a,b,c)\) 三元组为中位数是 \(b\)，左边长度是 \(a\)，右边长度是 \(b\) 。方便起见可以设 \(\gcd(a,c)=1\)，初始的时候 \(b=0\)。
我们先来考虑到最后 \((0,b,1)\) 和 \((1,b,0)\) 这两种有几个。一次变化相当于让 \(a+c\) 减去 \(a,c\) 中较小的，并且 \(b\) 可以向正或向负走 \(c\)。不难归纳说明，所有 \(b\in[-a-c,a+c]\) 都可以走到，并且根据奇偶性走到 \((0,b,1)\) 还是 \((1,b,0)\)。
然后考虑对于之前的每一层统计答案。在一层中， \(a\) 与 \(c\) 的集合是固定的，具体是哪个在前面取决于上一次 \(b\) 是 \(+c\) 还是 \(-c\)。
设 \(f_{i}\) 表示经过 \(i\) 次操作以后，当前层有多少节点。对于 \(c\) 相同的那些层，开始的 \(f\) 会不断变成一个，两个，三个，对于 \(c\) 不同的层，会重置。
但是这样是错的，两个节点会跨越层撞在一起。考虑在某一层，往两边走了 \(-u\) 和 \(+u\)，然后接下来 \(-u\) 不断 \(+v\)，\(+u\) 不断 \(-v\)，将 \(v\) 做完之后两边都是 \(u\bmod v\)，然后再做一次就会撞到。特判 \(u=v=1\) 的情况以后我们需要再设一个状态 \(g_i\) 表示重复的节点有多少个，然后在层之间转移即可。
可以证明只有这一种撞法，时间复杂度 \(O(T\log a)\)。
标签：LHF,位置,submission,选讲,len,ATCF,leq,序列,考虑 From： https://www.cnblogs.com/275307894a/p/18147476