D1
A. stones
这是一个典题。但是不知道在哪/kx
B. tree
树，有一个函数序列$f(u)=v$，其中$v$是$u$向某个给定点移动一步得到的点，每次求区间复合的点值。$n\leq 10^5$，5s。
分块先。零散部分容易线性。
同时移动所有答案，考虑复合一个函数会发生什么。可能会有两个答案相撞，这玩意看起来就很有均摊。缩起直链用块状链表维护即可。复杂度$O(n\sqrt{n})$。
但是块状链表太扯淡了，主要问题是我们需要快速分裂一条边，注意到只有$O(\sqrt{n})$个函数，所以我们可以直接把它们拿出来作为finger。
C. seq
序列$a$和置换$p$，如果$a_{i+1}=p_{a_i}$就在$i,i+1$之间连一条边，支持$a$的单点修改，或者给区间和$x$，求区间最大的存在某个$a_i=x$的连通块。$n\leq 10^6$，8s。
包含$x$比较见鬼。根号分治一下容易$\sqrt{n\operatorname{polylog}(n)}$。
置换是有意义的。考虑我们把同一个置换环重编号成连续的一段，然后把每个数画到平面上，那么问题就是查经过某条横线段的某种斜线的最长长度了，这里边界不完整的段大概是好做的。直接维护答案，修改的时候是两个$O(1)$个矩形加减。这个感觉就不是很好做啊。
然后比较厉害，考虑我们把一个段都挂到左端点去，那么问题变成插入竖线，删除竖线，求和一条横线交的竖线的最大权值。直接树套树即可。当然可以离线分治砍砍常数。
支配对
编号区间虚树点数
一个点在虚树上，当且仅当它在查询区间中，或者查询区间包含两个点在它的不同子树中。
如果有三个点$i<j<k$，$i,j$在不同子树中，$j,k$在不同子树中，那么$i,k$就被支配了。
对子树启发式合并，在小的里面枚举一个，大的里面查它的编号前驱后继。复杂度$O(n\log n)$。
Ynoi2006 rldcot
也就是改成查类似于虚树上的不同深度个数的东西。
2-side矩形数颜色。容易做到$O(n\sqrt{n})$。
考虑枚举一个颜色，也就是深度，把查询放到平面上，问题是给这些矩形的并$+1$。这里是左上2-side矩形所以很容易求并，单调栈即可。
Ynoi2003 铃原露露
也就是求有多少子区间对lca是封闭的。
考虑找到使子区间不合法的对。考虑如果$u,v$的lca是$w$。如果$u<w<v$，那么$u,v$就被$u,w;v,w$支配了。如果$u<v<w$，只需要取最大的$u$。如果$w<u<v$，还是只需要取最大的$u$。启发式合并即可。然后又求矩形并了。线段树维护区间最小值，区间最小值个数，区间最小值$=0$时个数的历史和。
cf765 F. Souvenirs
典。
codechef minxor
差不多做/mgx
Ynoi2004 rpmtdq
边分治，那么dis就被拆成两个东西的和啦。考虑一对$(i,k)$，如果$i$到分治中心的距离$d$比$k$更小，那么左侧到分治中心距离$\leq d$且在$[i,k]$中的点都不会和$k$贡献，因为它们到$i$的距离不超过$2d$，$>d$的。
杂题
Ynoi2002 Optimal Ordered Problem Solver
也就是2-side矩形向一个side贴。
发现所有修改过的点会贴在所有修改的包络线上。平衡树维护就好了。
劲爆的是可以一边改一边矩形数点。考虑左下2-side矩形，如果它在包络线下答案是0，否则我们把它差分成所有点减去一个上1-side，一个右1-side，再加上一个右上2-side矩形。前两个可以维护，第三个只包含没有被改过的点。
D2
A. a
数最小环个数。$O(nm)$。
在直径处统计，问题是最短路计数。
B. b
小写字母串，每次查一个区间最长的形如$xyxyxyxy…$的串的长度。$n\leq 1.5\times 10^6,q\leq 10^5$，3s。
枚举$x,y$。差分，求出每个后缀的答案，但是发现我们不知道$[l,r]$中匹配的最后一个字符是$x$还是$y$。
结论是，从$y$往左找到第一个$x$或$y$，那么匹配的最后一个字符必然是它。比如如果它是$x$，那么它到$r$不能有$y$，因此如果最后匹配$y$，这个$y$必然在它前面，所以其实可以继续匹配它。
复杂度$O(n\Sigma+q\Sigma^2)$。
C. c
排列，每个位置还有一个颜色，每次给$l,r$，求有多少个值都在$[l,r]$且端点同色的区间。$n,q\leq 5\times 10^5$，4s，线性空间。
发现排列是$1,…,n$时这是小z的袜子。所以考虑根号。
对颜色出现次数根号分治，小的部分只有$O(n\sqrt{n})$对，把$(\min,\max)$拍到平面上，可以根号平衡一下数点。为了卡空间，比如我们扫$\max$，数据结构维护$\min$，那么建立大根笛卡尔树，从下往上扫，启发式合并一个hash table就可以得到所有的对。峰哥好像有些简单做法，但是这个大概并不难写，因为我场上居然写出来了。
大的部分，注意到如果没有颜色的限制可以直接回滚莫队，对每种颜色分开做，把别的颜色缩起来复杂度就是对的。这部分据说非常难写。
总复杂度$O(n\sqrt{n})$。
不过好像没有出成线性空间，直接分常数轮跑就好了。
倍增值域分块
处理$>x$的$-x$一类的问题。
大概是，如果值域上顺序变了，我们让势能减少一些。
cf702 F. T-Shirts
据说可以一个$\log$。
先考虑俩，这玩意和取膜比较相似，从大到小考虑，每次买连续的一段，那么这一段结束的时候必然折半。线段树维护即可。
或者考虑扫序列，数据结构维护所有查询，那么问题就是$\geq x$的$-x$并答案$+1$，$x$是递减的。倍增值域分块，掉块则爆力重插，就是俩$\log$啦。
劲爆做法是，倒着扫，维护每个钱数的答案，那么如果现在扫到了$x$，把$<x$的复制出来接在前面，$\geq x$的打$+1$标记，可持久化平衡树即可。复杂度$O(n\log v)$。
Ynoi2007 rgxsxrs
classic。直接倍增值域分块，每个块开个线段树维护序列，只需要区间min以找到是否需要掉块。
但是据说是线性空间，所以需要平衡树，压缩trie或者底层爆力。不知道后两个哪个更快。
Ynoi er 2022 堕天作战
注意到$x\geq 0$。每个数如果$<x$又$-x$，就变得$<0$了，此后它总会$-x$，所以找到小的数爆力，大的数和rgxsxrs一样做即可。
cf1515 I. Phoenix and Diamonds
t-shirts的第一个做法仍然适用。
可以用倍增值域分块重新描述它，如果我们在某块中取不了，那么一直取小块中最大的直到掉块。如果在某块中能取，那么一下就会掉块。
ioi2021 地牢游戏
如果我们赢了同一块中的某个敌人，必然直接进入下一块，否则对于每个块前缀认为其中的都能赢，其外的都不能赢，这么搞一个数据结构，然后每次一直跳直到进入下一块或者赢了这一块中的某个。这是个基环树，树的部分剖一剖，环的部分直接做即可。或者这里倍增会简单一些。为了知道何时赢这一块中的某个，维护最小的初始值使得会赢这一块中的某个。
把倍增值域分块改成更大的进制以卡常。/kx
杂题
图穷匕见。
meta hacker cup 22 final D
树，边权是小写字母，每次给一个点和一个字典序，从这个点开始每次走字典序最小的邻边，并删掉这条边，求最后停在哪个点。
剖先，问题是我们要找到沿重链连续向上或向下走的长度，这给出一些 一个字符比另一个字符小 的限制，二分即可。压位以砍一个$\Sigma$，复杂度$O(n\Sigma\log^2 n)$。换个静态lct就好啦!
或者直接lct，就不需要处理向上走了/fendou
D3
赢了。但是没完全赢/cf
A. i universal cup ukraine G. Graph Problem With Small n
B. bad
C. computer
四路并行计算前缀字符串hash，最小化操作次数，不能差分。具体一点，有$n$个字符串，每次操作是给出四个三元组，每个称为$a_i,b_i,c_i$吧，对每个执行$t_i=a_i+b_i$，然后对每个执行$c_i=t_i$。
可以想到一个$\frac{1}{2}n$次的做法，我们两个一块，每次操作做下一块块内的前缀和，并让这一块加上这一块的前一个。不过这只用了三路。
可以想到一个$\frac{7}{16}$的做法，我们三个一块，还是每次把一块加上这一块的前一个。
注意到前者块内做的比块间快，后者块间做的比块内快。平衡一下，一个两个的块，一个三个的块，可以做到$\frac{2}{5}$。
可以发现下界在$\frac{2}{5}$附近。如果某组操作让$k$个位置变对了，那么我们之前至少要$k-1$次额外的操作，爆力枚举让$1,2,3,4$个位置变对的操作组数，可以发现它是$\frac{2}{5}$略小一点。
那么问题就是如何卡常啦!
杂题。
ec final 22 Magic
考虑一个间隔有贡献，当且仅当以它左边作为右端点的区间或以它右边作为左端点的区间
xx open cup gp of moscow Hidden Graph
考虑不停删掉度数$\leq k$的点，然后我们就发现了一个$k+1$染色。
考虑每次加入一个点，找到它到前面所有邻边，那么既然可以$O(m)$地找到一个$k+1$染色，我们找到这$k+1$个独立集，然后每次和一个独立集查，如果有边，就必然是和这个新点的连边啦。这样最多会有$n(k+1)$次查不到，整张图有$nk$条边，刚刚好。
xx open cup gp of moscow Graph Coloring
也就是每个点的入边和出边的颜色集合不交，并且每条边起点的出边和终点的入边颜色集合有交。我们只钦点入边，出边是入边的补，那么问题变成没有一个集合包含另一个。这是一个可比图最大独立集，跑最长反链即可。或者直接选择所有大小为$7$的子集。
xxii open cup gp of bytedance Graph Operation
结论是度数对应相等就行啦。显然这是必要的。考虑随便找到一个点$u$，我们现在希望把它的邻接点$v$换成$w$，也就是说$w$现在不和$u$邻接。如果$w$和某个$t$邻接，而$u$最后不邻接$t$，那么操作一次就好了。劲爆事情是，显然操作可逆，我们同时在正图和反图上做，那么只用这个必然可以让$u$在两边的邻接点相同。
考虑如果正图不能操作，那么$u$邻接所有$w$的邻接点。如果反图不能操作，那么$w$邻接$u$的所有邻接点。因为$u$邻接$w$而$w$不邻接$w$，$u$的邻接点和$w$的邻接点不完全相同，所以正图上$u$的邻接点比$w$的邻接点多，对称的，反图上$u$的邻接点又比$w$的邻接点少，这就与度数对应相等矛盾了。
使用bitset优化找$t$的过程。
qoj141 8染色
考虑二染色是可以做的，那么我们发四组，就可以做到$2n$个bit。
劲爆事情是，如果一个点度数$<8$，我们可以直接删掉它，最后染邻接点没出现的颜色即可，那么这样做完之后每个点度数$\geq 8$，也就是说点数不超过$\frac{m}{4}$了。这就赢了。
discover sigapore 19 by moscow workshops D5 300iq contest Good Coloring
问号构造。考虑钦点从编号小的颜色走到编号大的，那么跑一个dag最长路，显然每层是一个独立集，也就是说取这些层就得到了一个染色。
moscow workshops icpc programming camp 19 D2 Colored Graph
问号构造。考虑随便找一个哈密顿回路，如果所有边同色就结束了，否则必然存在一个点的两条邻边颜色不同，删掉它递归下去，最后必然可以加回来。
ec final 22 Rectangle
如果三条线同方向。直接线段树优化dp。但是直接枚举中间那条就是线性啦。
如果三条线不同方向。找到和另两条不同方向的那条，枚举它在哪，问题是支持插入删除，求用两个点覆盖所有区间的方案数。
考虑往平面上画，那么
ec final 22 Map
gcj 22 final Wonderland Chase
考虑如果所有点至少是二度，那么A必胜，因为他可以等B走到一个邻接点，然后走到另一个。这里重边视为一条。
剥掉所有一度点，它们形成若干树。B的策略是走到树根拦截A，A的策略是走到树根。如果B更快，那么A会尽可能往上走，然后走到子树中最深的点，否则A赢。
D4
A. grandmaster
有$n$个向量，构造一个方案，选两个切成两段(可以切出实数，第二次可以选第一次切出来的)，然后分成两组使得和相等。$n\leq 10^5$。
B. toptree
树，点权，求对于所有边集的子集，每个连通块$\min$的和的和。$n\leq 10^5$。
考虑一个点何时贡献，从大到小加点，那么我们要做一个几乎是 包含某个点的连通块个数 的dp，lct ddp即可。
但是这个做法太复杂啦!考虑直接dp，设$dp(u,i)$表示$u$子树，$\min$为$i$的连通块的贡献和，转移就是min卷积，可以线段树合并。统计答案只需要全局求和。
C. circle
环，你可以选择一个$i$，做操作$a_{i-1},a_i,a_{i+1}\leftarrow a_{i-1}+a_i,-a_i,a_{i+1}+a_i$，求最小的操作次数使得所有数$\geq 0$。多测，$\sum n\leq 3\times 10^6$。
这个操作比较经典，前缀和一下就变成交换两项了。但是这是环，所以开头和结尾会很奇怪。
考虑强行扔掉开头结尾，我们做一个无限长的前缀和$p_i=p_{i-1}+a_{i\bmod{n}}$，这里面每个数都是未定义的但是我们仍然可以考虑大小关系，可以发现原序列合法当且仅当这个前缀和递增，并且此时操作彻底变成交换相邻两项了。我们不能对无限长的序列求逆序对数，但是可以对每个位置定义后面比它小的数的个数$r_i$，因为原序列的总和，设为$s$，必须是正的(负的必然误无解，$0$有解当且仅当全$0$)，所以我们知道每个$r$必然有限。
考虑操作$i$之后$r$会如何变化，$\bmod{n}=i-1,i$位置的$p$会交换，现在只考虑$i-1,i$两个位置，那么$r_{i-1},r_i$也交换了，如果$p_{i-1}<p_i$那么$r_{i-1}$会增加$1$，$p_{i-1}>p_i$那么$r_{i-1}$会减少$1$。
于是问题是我们要求$r_1,…,r_n$。$r_i=\sum\limits_{p_j<p_i}[i<j]+\lfloor\frac{p_i-p_j-1}{s}\rfloor$。那个$[i<j]$就是个逆序对数，问题是$[p_j<p_i]\lfloor\frac{p_i-p_j-1}{s}\rfloor$的和。
考虑把$\lfloor\frac{}{s}\rfloor$扔掉，我们扔掉之后全部加起来，减去$p_i-p_j-1\bmod{s}$，然后除一个$s$。中间那个东西就是$p_i-1\bmod{s}-p_j\bmod{s}+[p_j\bmod{s}>p_i-1\bmod{s}]s$，于是这是一个二维偏序。赢了。
cco20 D2 Shopping Plans
收录于 未归类问题。
discover singapore 19 D5 Equal MEX
考虑如果有一个$0$，那么每一段都要有一个$0$。
如果还有一个$1$，那么每一段都要有一个$1$，因为每一段已经都有一个$0$了。
所以所有段的mex是相等的，都等于全局mex。直接dp即可。
xx open cup gp of moscow Joining Points
不交就非常好对吧!
注意到每个颜色必须画恰好一个弧，所以我们不可能画超过$n$个弧，所以dp，只需要记最大值及其方案数。
问题是这是环，可以枚举随便一个颜色选了哪个弧，然后从它断开dp。
cts22 D1 独立集问题
如果全正，可以发现我们只需要抛弃一个最小的。但是这个没啥用。
如果有负数。考虑如果对一个点进行了一次操作之后，又进行了一次，效果就是把它取负了。于是被操作产生的数在最后的贡献必然可以是正的。大力dp，状压父边两侧有没有选，如果选了谁先谁后之类的即可。
xxii open cup gp of yuquan The Profiteer
固定一个端点，另一个端点是一个前缀。
分治。问题是如何$O(nk)$求一个。直接二分，如果向左递归，那么右边都不会涨价，如果向右递归，那么左边都会涨价，所以我们只需要加入$O(n)$个元素。
xxii open cup gp of yuquan Dynamic Reachability
时间分块。
ptzsc20 D1 Raid
考虑怎么求最少的逆序对个数。考虑折半，但是合并需要归并。
考虑如果现在考虑了前$i$个，后面的数把值域分成若干段，那么每一段只有选多少个有用。
考虑这玩意状态数有多少，只考虑一个$i$，那么相当于$i+1$个和为$n-i$的数乘积最大是多少。考虑$k$个和为$n$的数乘积最大是多少，应该是$(\frac{n}{k})^k$。导一导，这玩意在$k=\frac{n}{e}$的时候最大，所以复杂度是$\tilde{O}(e^\frac{n}{e})$。
xx open cup gp of zhejiang Fast as Ryser
收录过，但是remake。
考虑爆力怎么做，状压dp，记每个点是否已经匹配。
xmas contest 22 Fast as Fast as Ryser
考虑
xvii open cup gp of romania Salaj
看起来很劲爆。考虑我们如何构造一个图，首先scc数量单减，如果一次操作减少了$k$个scc，我们可以建一条链，只有$1$所在的scc可能非平凡，这样只需要把$1$所在scc后面第$k$个点连到$1$。看起来不太能用更少的边了。
问题是边也可能太多，导致链已经穿过所有点，那么我们就顺着链连。如果顺着链也连满了，连$1$所在的scc。如果边数还要大，那就没救了。这样方案是唯一的。
dp，设$dp(i,j,k)$表示长$i$，$a_i=j$，链长为$k$的方案数。复杂度$O(n^4)$，可以前缀和优化到$O(n^3)$。
D5
由于A1 B1都被南夫拉斯势力做过，换了，所以今天有五题。由于A2也被南夫拉斯势力做过，今天unrated。
A1. a
树，求有多少种方案加上一些边，使得它变得边双连通。$n\leq 5000$。
容斥，钦点一些边不被覆盖，然后只需要记$u$所在的连通块大小就可以转移啦。
A2. aa
树，从$s$出发随机游走，每一步等概率走到一个邻接点，走到$1$就停下。随机把$k$条边变为指向$1$，求步数的期望。$n,k\leq 10^6$。
手动主元法消消，可以发现如果$k=0$，设$f(u)$表示现在在$u$，走到父亲的期望步数，是很有意义的。这玩意的转移是个几何分布，设度数是$d$，我们需要期望$d$次走到父亲，这样从$u$出发有$d$步，还有$d-1$次等概率走到一个儿子，也就是$f(u)=d+\frac{d-1}{d-1}\sum\limits_v f(v)$。那么$f(u)$就是$u$子树所有点的度数和，答案就是$s\rightarrow 1$上每个点的$f$之和。
现在$k>0$。考虑一个点的贡献，如果它不在$s\rightarrow 1$上，如果它到$s\rightarrow 1$的链上有边指向$1$，那它不会贡献。否则，它儿子的父边可能被选，枚举有多少条被选，二项式系数选选即可，然后它的贡献还要带一个链上到第一条被选的边的距离的系数，枚举这个距离，这里是个上指标求和。如果它在$s\rightarrow 1$上，还要考虑它的父边被选的情况。
B1. b
dag，边权可能是$a$或$b$，每次给$a,b$，求$1$走到某个点的最短路。$n\leq 5\times 10^4,m\leq 10^5$。
直接跑凸壳。复杂度$O(n^\frac{2}{3}m+q\log n)$。
B2. bb
给定$n\times n$的矩阵$a$，你要给每行$i$分配一个$s_i$，每列$j$分配一个$t_j$，使得$a_{i,j}+s_i+t_j\geq 0,\sum s_i+\sum t_i=0$。$n\leq 500$。
看起来像是km的顶标。我们就是要对$-a_{i,j}$这个完全二分图找一组(最大权完美匹配的)可行顶标使得顶标和为$0$。
所以如果km求出的最小顶标和$>0$，那么必然无解。如果最小顶标和$=0$，那么就找到了解。如果$<0$，直接给随便一个加上一些即可。
C. c
序列，每次可以交换相邻两个，对每个前缀求把它变得双调(先增后降)的最小操作次数。$n\leq 5\times 10^5$。
从大到小扫，发现加入一个数的时候，它放在最前面则恰好跟比它大且在它前面的数贡献一次，放在最后面则恰好跟比它大且在它后面的数贡献一次，每个数是独立的。
因为我们只往后加数，前者不变，后者只会变大，每个数只可能从后面切到前面，线段树维护即可。
图论。
先补一下km是啥。
将最大权完美匹配对偶，问题变成，每个左部点一个变量$x$，每个右部点一个变量$y$，要求$x_i+y_j\geq w_{i,j}$，最小化$\sum x_i+\sum y_i$。
联合省选23 D1 B. 城市建造
比较容易看出的是缩v-dcc，然后每个v-dcc内的边要么全断要么全不断，并且选择断的v-dcc在圆方树上是一个连通块。
$k=0$比较经典。枚举连通块大小$s$，所有子树大小为$s$的倍数的点的父边都要断。如果恰好产生$\frac{n}{s}$个连通块，那就对了。
$k=1$时。注意到圆方树的重心必然断，所以我们以它为根，那么一个v-dcc断了，的祖先考虑子树大小$<s$的必然不断，$\geq s+1$的子树中必然有一个断了，所以必然要断，
联合省选23 D2 B. 填数游戏
写写我场上做法。图论转化大家都会了。基环树是简单的。考虑树，猜测存在某种类似于center的东西，使得最优策略是让所有边都指向它，换根dp即可。我调出枚举根的时候只剩10min了，所以没有换根是64pts。
dmopc22 contest2 F. Yogyakarta Elevators
相当于每个电梯是一个团，然后无向图传递闭包。那么不行当且仅当存在一个点没有电梯，或者存在两个出现过的电梯不连通。
那么对于每个左端点，不可行区间的右端点就是$m$个区间的并，每个左端点表示一个电梯出现，每个右端点表示一个电梯合并进连通块。从右往左扫，可以维护出每两个电梯何时合并，然后枚举一个合并时间就可以做到$O(nm^2)$。
只需要维护mst。每次会加$O(m^2)$条边，但是其实我们只要加任意一个生成树，也就是$O(m)$条，直接kru地remake mst，复杂度$O(nm\alpha(m))$。
考虑怎么线性地合并mst，发现因为加的边权都一样，
cf235 D. Graph Game
考虑树怎么做，考虑一个点贡献次数的期望，考虑类似于快速排序的分析，计算$u$作为分治中心时$v$在$u$分治块中的概率，发现它就是$\frac{1}{d(u,v)}$。
bjoi2018 染色
收录于 oi题选做。
coi 2010 ROBOTI
我们可以知道到底走没走。让一个波特走整张图，然后另一个的位置就知道啦。
D6
A. a
cf1799 F. Halve or Subtract 加强版
$n\leq 10^5$。
只有最大的若干个数会被操作。把数分成$\geq 2b,\geq b,<b$三段，那么第一部分直接塞满，第二部分必然是一个前缀都选，然后一段选$\times \frac{1}{2}$，然后一段选$-b$，然后如果有数没选，第一段长度必然是$0$否则不优，否则考虑第三部分，必然是一个前缀$-b$，然后一段选$\frac{1}{2}$，然后一段不选。枚举第二部分第一段长度，那么单独的$-b$的个数就确定了，考虑两边的答案关于$-b$个数都是下凸的，做闵和即可。除去排序，复杂度$O(n)$。
也可以模拟费用流。让我想考虑一下类似的图是不是总可以简单地闵和。
B. b
环，给若干个弧，你要给每个弧染黑色或白色，使得对于每个点，包含它的弧(弧包括端点)的颜色不只有一种，可能无解。$n\leq 10^5$。
我做法是啥，考虑如果是链，贪心即可。如果是环，如果我们可以确定方案的一部分，使得有一个已经合法的点(可以只是一个点而没有长度)，那么从这里断环成链即可。考虑找到最长的弧，把它转成$[0,r)$，然后找到包含$0$的弧中左端点最左的$[l^\prime,r^\prime)$，那么如果这俩弧颜色不同，$0$就合法了，如果相同，不妨设都是黑色，那么必然还得有一个别的白色弧来覆盖$0$，由于我们选的是最长的，它必须包含在$[l^\prime,r)$中，而由于$[l^\prime,r)$已经有了黑色，完全包含在其中的任何一个弧选白色都是不劣的。这就结束了。
C. c
$n\times\infty$的棋盘，每个格子可以放一个炮或不放，如果两个棋盘可以通过若干次交换两行或交换两列变成相同的，那么它们本质相同，求有多少种本质不同的放炮的方案，使得没有两个炮可以互相攻击。$n\leq 10^5$。
还是建个二分图，发现没东西的列可以扔了，那么本质相同当且仅当图同构。环和链肯定不同构，环和环、链和链同构当且仅当长度相同，所以我们就是要计算$\frac{1}{1-z}\left(\frac{1}{(z^2;z)}\right)^2$，这里需要注意单点是环也是链，而且没有方向。直接q-二项式定理即可。
网络流。
蜥蜴
cqoi2012 交换棋子
拆点，匹配。感觉我还是不会匹配。
bjwc2018 餐巾计划问题
icpc06 beijing 狼抓兔子
平面图大师。
D7
A. string
01序列，支持单点修改，或者查询一个区间和一个thue-morse序列的区间的汉明距离。$n,q\leq 3\times 10^5$。
被根号$\log$冲爆了。
thue-morse某种意义上是循环的，所以直接分块就很好算了。
B. permutation
给一个排列，对每个前缀求有多少个子序列离散化后形如$2,1,4,3$，其中$1,2$可以相同，$3,4$可以相同。$n\leq 5\times 10^5$。
$1,2$是顺序对，$1,3,2$只需枚举$3$，$2,1,3$只需枚举$1$。还是$2,1,4,3$最为困难。
考虑把$2,1$挂在$2$，数据结构维护$4$的个数，但是发现加入$1$的时候$4$的个数会变。考虑容斥成$1,1,4,3$减去$1,2,4,3$，这样就不会变啦。复杂度$O(n\log n)$。
C. rbtree
有一个栈，有一个操作序列，每个位置可能是push $0$，push $1$，或pop。如果一次pop了一个$1$，那么下一个push的数会被改成$1$。支持区间取反push的元素，查询执行一个区间的操作之后有多少个$1$。$n\leq 6\times 10^5$。
不会修改push和pop的匹配。考虑一个push只会影响pop它之后的第一次push，所以我们从它向那个push连一条边。那么一个点会变$1$，当且仅当连向它的点有一个$1$。也就是说答案就是所有$1$和根的斯坦呐树大小。从左往右就是一个拓扑序，所以线段树维护区间第一个$1$和最后一个$1$即可。
但是，可能，这个区间不是连通的。首先加入足够多的pop弹空，然后加入个push使整棵树连通，那么如果现在要查询$[l,r]$，考虑$l$左边第一个push，设为$t$，把它到根的链加入这棵树，它就必然是连通的了，具体一点就是把$t$和根两个点加入斯坦呐树。最后删掉这条链只需要减去$t$到根的距离。
数数。
ATjsc2019_qual_f
如果没这个限制，隔板法即可。
枚举排序后$m$位的数是啥，有多少个，那么比它小的数和比它大的数的个数就要求我们拿出第二个元了。这就不好，转而考虑$m$和$m+1$位不同，枚举$m$位的数是$d$，那么问题是选$m$个$\geq d$的数且有一个$d$，和$n-m$个$<d$的数的方案数，前者隔板，后者容斥，钦点$\geq d$的数的个数，然后隔板。复杂度是调和数。
cf1264 D2. Beautiful Bracket Sequence
又见面了。
也就是找一个子序列使得深度最大。其中对深度没有贡献的匹配括号都可以删去，所以我们找到一个位置使得左边左括号和右边右括号数量的$\min$最大，然后选择这些作为这个子序列即可。
因为是两个相反方向单调函数的$\min$，这等价于左边左括号和右边右括号数量相等。枚举最小的这样的位置，枚举数量，然后选选即可。数量的枚举是个范德蒙德卷积。
arc146 E.
扫值域，dp，设$dp(i,j)$表示现在填了$1,…,i$，有$j$个间隔两侧都是$i$的方案数，不过还要单独考虑两侧。我们可以用$k$个$i+1$生成$k-1$个新的间隔，那么可以注意到每个$i$只有一个$j$可以转移到。
luogu6276
阶就是环长lcm对吧。枚举一个素数幂，考虑它不出现的方案数，那么ban掉所有是它的倍数的环长，
不等关系
容斥，钦点一些$>$变成$<$，那么每个连续段是无序的，钦点出连续段即可。发现可以分治法法。
agc060 D.
这玩意就不太阳间了。考虑可以对两个序列同时跑 不等关系 的dp，也就是分别记当前连续段长度，复杂度$O(n^3)$。
考虑继续容斥，我们给$(<,<),(<,?),(?,<)$各分配一个系数，这样只需要记上一个$(?,?)$出在哪里。复杂度$O(n^2)$。发现直接就是$\frac{1}{1-z}$复合什么东西了，法法即可。
cf1188 E.
考虑如果钦点了每个颜色被操作的次数，要判定是不是能这么操作，那么每次操作出现次数最小的颜色，如果有颜色不够了那就不行，否则必然可以。
注意到如果有至少一个颜色操作$0$次，那么两个方案不同当且仅当有两个颜色被操作次数不同。
考虑这个判定还是不够好，我们转化成，如果颜色$i$有$c_i$个，那么在前$c_i+1$次要操作它至少一次，在前$c_i+t(k-1)+1$次要操作它至少$t+1$次。看起来根据那个贪心，这是充要的。
但是这个判定还是不够好，注意到如果在前$c_i+1$次能操作它至少一次，后面的也必然可以操作了，因为只有恰好$k$种颜色，每轮的操作数必然够用。也就是说我们操作过的数的值域前缀和满足$s_i\leq i$之类的东西。
找到第一个爆炸的时刻，那么在此之前每个数可以随意选操作次数。
D8
完全错误估计了BC的trick普及度。
A. logo
cqoi2015 标识设计
/cf
枚举三条竖线，从上往下dp。不是很阳间。
B. point
xviii open cup gp of Ukraine K. Dance
数轴上有一些点，如果有一个点$x$，你要选择$x+d$或$x-d$，然后用一些区间覆盖你选的这些点，一个长$k$的区间代价是$a+bk$，最小化总代价。$n,x\leq 150,1\leq a,b\leq 10^6$。
选择的话，相当于$x+d,x-d$至少选一个。
考虑如果选完之后一个间隔长度是$k$，那么我们就会选$\min(a,bk)$。
考虑我们有关于最近的那个的贡献，还有相距$2d$的限制。
考虑每个位置选没选，按$2d$大小分块，把这些块当作行，排成一个矩阵，此时只有每个位置和上下的限制，以及和这一行上一个$1$的限制。但是这个不够局部，我们转而考虑每个位置在不在一个选了的区间里，现在行上的贡献也变得局部了。根号分治，如果$2d$很小，竖着扫，也就是依次扫每一块。如果$2d$很大，横着扫，相当于每次填一个$\bmod{2d}$等价类，还需要枚举一下第一列的状态以和最后一列拼起来。轮廓线dp即可。复杂度$\tilde{O}(2^\sqrt{2v})$。
C. rabbit
给一棵树，有$m$个未确定的点$x_i$，$q$个限制，每个表示$x_a,x_b,c$的y-center是$d$。构造一组可行的$x$。$n,m,q\leq 150$。
2-sat。给每个$x$在每个点建一个变量$t_{i,u}$，问题是如何限制$t_{i,…}$至少有一个$1$。因为这是一棵树，考虑做个子树和，这样我们只需限制根是$1$，并且可以发现限制都是子树相关的所以恰好可以表示。然后直接连复杂度就是$O(n^3)$，可以前缀和做到$O(n^2)$。
如果这是一般图，只需要使用杏仁就可以规约色数。
usaco23 feb Pt C. Watching Cowflix
he_ren讲了一个top tree做法，但是我不懂。
考虑猜测随着$k$变大，我们选的点必然是越来越多。注意到如果两个连通块距离$\leq k$，那么
loj2398 自然公园
注意到删掉一个点之后，剩下的点最多分裂成$7$个连通块。考虑我们可以查$u$到一个连通块有没有边，我们只允许从它中转，然后看看能不能到点集中任何一个点即可。那么我们只需要跑一个dfs树，在dfs序上二分。然后挖掉这个点继续做，这会产生不超过$7$个连通块，可以$O(1)$地知道$u$到每个有没有边。
问题是我们还得加点，于是我们希望加点过程中连通块数尽可能少。直接让它是一个连通块。考虑如果尝试了$u$，它到已知部分$S$没有边，那么我们找$u$到$S$路径上随便一个点，尝试加入它，直接二分就可以找到这么一个点。如果加上之后还不连通，那么继续尝试直到连通。这样每个点只会被加入一次，付出$\log$的代价。
总复杂度$O(n\log n+m(d+\log n))$。
cf1801 E. Gasoline Prices
相当于链到链对应位置合并，维护所有区间长度的乘积。
静态lct维护链hash值。
loj2785 交换
好像被xtq搬过zroi。
贪心。可以注意到只有到根的链和链上每个点的儿子可以换过来。dp，设$dp(u,i)$表示$u$子树，$u$现在是$i$的最小字典序，$i$只有$\log$个，复杂度$O(n\log n)$。但是比较字典序需要比较序列，所以其实是$O(n\log^2 n)$的。
也可以直接贪。考虑要让一个位置是某个数的方法是唯一的，枚举要哪个数，维护每条边用没用，直接爆力check即可。
codechef Balancing Network Revisited
注意到$2i-1,2i$各操作一次就达到$\frac{n}{2}$。
考虑维护若干个对和孤立点，每个对都被操作过一次，并且现在可以让其中任何一个是$1$另一个是$0$。操作两个孤立点则得到一个对，操作对和孤立点则
-
如果操作孤立点和$1$，把$0,1$互换，并让孤立点和新的$0$成为新的对，$1$成为新的孤立点。
-
如果操作孤立点和$0$，让孤立点和新的$0$成为新的对，$1$成为新的孤立点。
操作对和对也是类似的。
-
如果操作$0$和$1$，
-
如果操作两个$0$/两个$1$，$0,1$互换一对，这样当你想要改的时候，可以改为互换另一对的。
构造方案的话，直接胡乱维护一下就好啦!大概是要维护互换会发生啥，好像就是如果把换一对改成换另一对看成另一种操作，只要打一个取反标记。
joisc23 D2 A. Belt Conveyor
考虑我们希望让两个物品不可能重合，此时可以推出每个物品从哪里来。考虑按深度$\bmod{3}$分类，这样就不会重合啦，那么我们每次可以确定每个还未确定的点的一条邻边的方向。
这个还是不够好，我们每次选择一个极大的点集，使得对于每个点，没有距离在$3$以内的点被选，如果有$k$个还未确定的点，这样的点集大小至少是$\frac{2}{3}k$。于是只需要查询$\log$轮。
joisc23 D2 B. Council
考虑如果最后那个阈值是$k$，并且现在已经删掉了一个数，那么如果有一位出现$k$次，删掉这一位是$1$的会让答案减少，此外啥也不会发生了。相当于查和某个数$x$ and的最小的popcnt。考虑枚举and，但是这会算小。考虑枚举or来容斥，or只会算大，所以就赢了。因为会删一个数，维护两个特例。
但是这个法嘛塔比较智障，考虑直接批量处理 从集合中一个数出发，每次修改一位，直到完全改成查询的$x$ 这个过程，也就是设$dp(i,j)$表示前$i$位是查询的$x$，后面的位是集合中某个数的最小答案，转移枚举下一位查啥，而初值是每个集合中的数。
gcj23 farewell contest Round C D. Game Sort
如果有相邻两个字符，前一个比后一个大，那就赢了。但是这要求$k\geq 4$。
先考虑$k\geq 4$。现在它是单调递增的，如果有一种字符出现至少三次，也可以分出一个aa a，那么就赢了。
如果仍然不存在这样的字符，那么可以感觉到必然无解。
考虑$k=2$，枚举分段点，比较前面的最小字典序和后面的最大字典序，那么依次比较每个字符即可。可以注意到必然是前一半全相同且是最大的字符，且这个最大的字符在这一段出现次数比后面多。
考虑$k=3$。考虑找到最后一个最大的字符，如果它不在最后一位，我们可以把它单独划出来。如果第一个最小的字符不在第一位，也可以把它单独划出来。如果有一个最小的字符不在第二位，也可以把它单独划出来，这样它必然比第一段小。
否则，不管怎么切，第一段都必然是最小的段，因为只有第二位可能是最小的字符了，不可能产生一个比第一段更小的段。所以问题变成让第二段比第三段大，和$k=2$类似，找到一个不包含$n$的最大的字符的连续段，使得这一段中最大的字符比后面出现次数多即可。
joisc19 D1 Meetings
随机两个点$u,v$，跟所有$w$查，那么$w$在链上当且仅当答案是$w$，并且这可以求出每个点在链上哪个点的子树中。还需要求出相对顺序，我们通过查询$u,w_1,w_2$就可以知道$w_1,w_2$哪个在前哪个在后，sort即可。
首先sort的复杂度是$O(n\log n)$，因为每个点只会参与一次sort。
注意到经过边分的中心边的概率是$\Omega(1)$的，所以复杂度是$O(n\log n)$。这里认为$k=18$是常数。不过它看起来不怎么常数啊?
或者有个确定性做法，加点，维护一个点分治，那么可以通过和每个邻接点查一下得到应该走进哪个子树，走到一条边的时候查一下它和端点，就可以知道这条边发生什么变化。如果按子树从大到小查询应该走进哪个子树，那么如果我们查了$k$次，子树大小至少减少到$\frac{1}{k}$，所以复杂度就是$O(nk\log_k n)$。
但是这个需要卡一个$\frac{1}{2}$。考虑我们走到一个分治中心，问查询点和它的两个儿子，那么问题是如果答案是分治中心怎么办，此时查询点必然在它到两个儿子的边上，判断是哪条边即可。
现在考虑那个随机做法的复杂度，注意到链有至少$\frac{1}{2}$的概率砸中重心，并且它对儿子个数也是期望按顺序随机抽中的，所以这俩做法复杂度是一样的。
D9
A. tree
图，对每个边数求连通生成子图个数。$n\leq 15,m\leq 200$。
直接取$\ln$。转为点值以加速边数上的乘法。
让我来写个半在线卷积把大家都杀了。
B. difference
cf1500 F. Cupboards Jumps
未知序列，给每相邻三个位置中$\max$和$\min$的差，构造一个序列符合它。$n\leq 2\times 10^5,v\leq 10^{12}$。
dp。发现我们只需要记差，所以设$dp(i,j)$表示前$i$个，$\vert a_i-a_{i-1}\vert=j$是否可行。那么设$i-1,i,i+1$的限制是$b$，如果$j<b$则可以转移到$b$或$b-j$，如果$j>b$那就没救，如果$j=b$则可以转移到$0,…,b$。
那么也就是支持截断一个后缀，塞一个点，翻转一个前缀，也可能会全部推平。注意到推平产生一个线段，塞的点总在最前或最后，所以可以用双端队列维护，胡乱打打全局标记就赢了。
C. function
cf1098 F. Ж-function
我好像会莫队二次离线，但是还是看看polylog吧嘉然们!收录于 几个不需要静态top tree的静态top tree问题。
dp。
cf1810 G. The Maximum Prefix
经典地，设$dp(i,j)$表示前$i$个，$\max\limits_k a_k=a_i+j$的概率，
agc061 C. First Come First Serve
这玩意就是若干个两个端点都单调的区间。
heren做法比较厉害，考虑我们贪心构造字典序最小的方案，那么这个方案当然是唯一的，我们对可能出现的方案进行dp，一个方案不可能出现，当且仅当有一个数的区间中没有一个点被选，但是它选了$b$。容斥，钦点出这样的区间，和它相交的区间必须选在它外面的那个，不和被选区间交的区间是自由的。dp即可。
arc134 E. Modulo Nim
又见面了。
arc156 E. Non-Adjacent Matching
排成一个圆。
经典地，如果要构造一个度数序列，我们不停让剩余度数前两大的点连边。那么如果有一个点度数超过一半必然无解。但是如果它俩相邻就不是很好。
注意到我们可以调整一下让一条边换到里面去，也就是$a\leftrightarrow b,c\leftrightarrow d\rightarrow a\leftrightarrow c,b\leftrightarrow d$。如果一条外侧的边不能换，那么剩下所有边都和它有公共端点，那么这两个点的度数和要超过总度数的一半。这也几乎是充分的，因为这种东西我们显然是构造不出来的啦。剩下的条件是所有点的度数和是偶数。
注意到相邻且度数和超过总度数的一半的点要么没有，要么只有一对，要么是相邻的三个组成两对。先算总数，减去钦点一对的，此时两对的会被减两次，再加上钦点两对的。
对于没有限制的，直接容斥，隔板法。
对于后两个，总和不超过$4m$。对于钦点一对，钦点$1,2$是那一对，枚举$x_1,x_2$，可以背包。
对于钦点两对，钦点$1,2,3$是那两对，枚举$x_2$，
abc290 H. Bow Meow Optimization
类似于 方差，狗和猫分别是单峰的。复杂度$O(n^4)$。
joisc23 D1 B. Festivals in JOI Kingdom 2
joisc23 D3 A. Chorus
非空是没用的。考虑如何判定，找到第一个b，如果前面有$t$个a，那么我们选择最靠前的$t$个b。于是也就是，第$i$个a匹配第$i$个b。
joisc23 D3 B. Cookies
考虑给一个每个盒子装的数量，如何判定能不能装进去。这是个完全二分图的多重匹配。类似于hall定理，
D10
A. coin
01串，有一些位置没有确定，给定其中$0,1$的个数，构造一个方案，最小化最长连续段的长度。$n\leq 10^6$。
二分答案，然后单调队列优化dp求出最小和最大的$0$的个数，设方案分别为$a,b$，如果限制的$0$的个数在$[a,b]$中，那么我们取$a$的一个前缀和$b$的对应后缀拼起来，其中必然有一个答案。显然$0$的个数是连续变化的，问题是两侧拼起来的位置两边可能是相同的字符，此时向一边移动要么不会改变$0$的个数，要么会让两边变得不同，所以忽略它即可。
好像被各种贪心冲爆了。
B. segments
数轴上有一些线段，两个线段要么要么包含，且没有两个端点重合。给每个线段选一个非空子线段，要求两两不交，最大化总长。
dp，自顶向下决策，需要记子树外在子树内选了多少区间。注意到如果子树大小为$s$，那么子树外最多选$s+1$个，所以复杂度是树卷积。
C. upup
两个严格递增序列$a,b$，求从$a$出发，每次给两个不同的数$+1$，到达$b$，且任意一次操作后没有两个相等的数的方案数，膜$10^9+7$。$n\leq 30,a_i,b_i\leq 200$。
一眼 雅礼集训2017 D11 path，鉴定为lgv lemma。考虑把给两个数$+1$的操作拆成两个，这样类似于斜杨表计数的做法就能算啦，然后对$2i-1,2i$操作了同一个数的策略进行容斥即可。需要给一个元素是$O(nv)$次多项式的矩阵算行列式，插值即可。复杂度$O(n^3v^2+n^4v)$。
然而爆了ub。以后要开sanitizer测大样例。
杂题。
agc043 D.
也就是归并一下。
考虑如果一个triplet中$a_1>a_2$，那么弹$a_1$之后必然立刻弹$a_2$。
考虑如何判定一个序列能不能生成，如果$a_i>a_{i+1}$，那么$a_i,a_{i+1}$必然来自同一个序列。那么分成若干连续下降段，段首之间是上升的，每一段长度不能超过$3$，长$2$的不能比长$1$的多，长$3$的必然自己一段。记一下长$2$的个数和长$1$的个数的差，复杂度$O(n^2)$。
arc118 E.
什 么 ?
还是经典容斥，设$dp(i)$表示现在在$(i,p_i)$的方案数，但是我们不知道$p_i$是多少捏。考虑我们要钦点一个上升子序列，设$dp(i,j,k)$表示结尾于$p_i=j$，包含$k$个?的所有上升子序列的贡献和，最后乘上未确定的数随便排的方案数，可以前缀和优化，复杂度$O(n^4)$。
考虑如何做到$O(n^3)$，注意到中间的系数仅是路径数，可以类似于agc001 E. 的做法来批量转移。再来考虑那个范德蒙德卷积做法，
arc114 F.
可以想到后缀排序，选整个串和前$k-1$大。
哦，这是个排列啊!
注意到越分字典序越大，所以我们可以先最大化答案和原串lcp的长度。二分这个长度$k$，如果后面还有$k-1$个串比原串大那就行。对
cf1672 G.
还是给每行每列建一个点，那么每个操作相当于取反
注意到$n,m$都是偶数的时候，所有操作是线性无关的。如果有一个是奇数，那么
sdoi2017 硬币游戏
arc117 E.
这是一条折线。考虑扫值域，设$dp(i,j,k,l)$表示扫到$i$，长$j$，有$k$个接头，有$l$个区间和为$0$的方案数。枚举一共留了多少，插板分给接头，复杂度$O(n^6)$。
arc117 F.
差分约束，但是这是环，所以不太好办。
考虑二分总和，这就赢了。但是复杂度是$O(n^2)$。
观察一下，发现环要么经过$0\leftarrow 2n,0\rightarrow 2n$，要么经过$n$，所以跑个最短路即可。但是最短路还是不是很会，好消息是这里图性质很好，可以直接dp。
cf1608 F.
感觉很厉害。
dp，设$dp(i,j)$表示前$i$个，$\operatorname{mex}=j$的方案数，那么$\operatorname{mex}$只会变大，如果从$j_1$变到$j_2$，那么这个位置必然是$j_1+1$，而$j_1+2,…,j_2$都在前面出现过，可以钦点出它们的位置，而前面不能出现过$j_1$。最后有若干个数没有被钦点，但是它们可以是的数不太一样，不过一个数只是不能等于后面出现过的任何一个$\operatorname{mex}+1$，可以在这里留一个接头，到它比$\operatorname{mex}$小的时候再确定。dp，设$dp(i,j,k)$表示前$i$个，$\operatorname{mex}=j$，有$k$个数比$\operatorname{mex}$大且未确定的方案数。可以前缀和做到$O(n^2k)$。
cf1266 H.
状态写成一个向量，非常好对吧!但是这不是一个线性变换。
设出进入每个点的次数，那么分别从两条边离开的次数只和它的初始颜色，最后颜色，是不是$1,v$有关，并且它是满秩的，可以高消消出来。
但是问题是解出来的东西可能和初始状态不在一个环上。
结论比较震撼。
D11
A. tree
树，点有点权$w$，选一个集合$S$，最小化
\[\begin{aligned} \sum_{i,j}[i\in S,j\in S,i\in\operatorname{anc}(j)] \end{aligned}\]B.
xxii open cup gp of imo I. Intellectual Implementation
数论。
wc2020 猜数游戏
因为每个数都要问一次，相当于每个
求一个原根，那么如果$a=g^k$，就可以标记所有$g^t$满足$\gcd(\varphi(p),k)\mid t$。那么$f$就是$\gcd(\varphi(p),k)$在整除意义下的极小元个数。
于是枚举一个数，看看它何时是极小元。那么也就是比它小的都不能选。复杂度$O(n^2)$。
$\gcd(\varphi(p),k)$当然是$\varphi(p)$的因数，所以我们只需要在所有因数上跑一个每个点可以到达的点计数。做狄利克雷前缀和即可。
wc2021 斐波那契
补充到 fib数列 了。可能会remake这一篇。
D12
A. colour
序列，奇数位可以填$1,3$，偶数位可以填$2,4$，给$m$个区间，要求每个区间颜色数不能是$4$，求方案数。$n,m\leq 10^6$。
扔掉被包含的区间。
爆力dp就是设$dp(i,j,k)$表示现在在$i$，如果$i$是奇数，$j-1$是上一个和$i$不同的，$k-1$是上一个和$i-1$不同的，否则反过来。也就是说$j$是只看奇数位的上一次变化的位置，$k$是只看偶数位的。
转移的时候，奇数位是$dp(i,…,k)\rightarrow dp(i+1,i,k)$，偶数位是$dp(i,j,…)\rightarrow dp(i+1,j,i)$。给每个区间左端点$+2$，那么扫到一个右端点$r$的时候，我们要把$j,k\geq l$的所有状态推成$0$。这看起来有点像sdoi2019 染色，所以我们考虑行的和和列的和，但是这里推成$0$的时候会有问题。
注意到被推成$0$的状态对后面完全没有影响，所以不如一开始就不加入它们，也就是说现在$i$右边第一个$r$对应$l$，那么对$\geq l$的行和列我们都不更新。由于$l$是递增的，可以做到$O(n)$。
B. rps
模拟。
C. fenwick
一个函数序列，每个位置是$f(x)=x\operatorname{xor}a$或$f(x)=x-\operatoranme{lowbit}(x)$，这里如果$x=0$则$\operatoranme{lowbit}(x)=0$。每次给一个区间和$x$，求从左往右代入得到的结果，强制在线。$n\leq 10^6$。
感觉比较厉害。问题在于$-\operatorname{lowbit}$咋做，考虑设$f(i,k,j)$表示现在在$i$，低$k$位是$j$，低$k$位变成$0$
杂题选讲。
cf1514 E.
先用操作$2$归并求一条哈密顿链，然后沿着哈密顿链向前问。
cf1535 F.
显然$f$只可能是$0,1,2,1337$。
考虑$0$。hash。$1337$可以集合hash。
考虑$1$。根号分治。如果串个数不超过根号，直接做。如果串个数超过根号，那么长度不超过根号，枚举哪个区间排序了，hash即可。
考虑怎么poly log。枚举一个串，枚举一个极长上升段，如果两个串之间$f$是$1$，必然可以另一个串在这一段排序，并且由于操作方案唯一，这个极长上升段也是唯一的。正反建trie，那么前缀和这个极长上升段前面相等的，后缀和后面相等的就是两个子树的笛卡尔积。数点即可。
cf1508 D.
对于每个环，我们可以留一条边不连。这个显然比较无解啊!考虑一个大环，环上每条边都和另一个二元环相交。
考虑我们选一个点，跟所有点连一条线段，那么每个环上只有一个位置不能换对，也就是说最后每个环上有一个元素会走到下一个环上。
考虑如果只有一个环，我们就赢了。所以极角排序，如果有超过一个环，必然存在两个点满足它们在极角序上相邻且属于不同的环，所以只需要把它俩换一下就可以合并这两个环。
cf1603 D.
注意到$k$超过$\log$答案必然是$n$。
dp，设$dp(i,j)$表示$0,…,i$分$j$段的答案。注意到$c$满足四边形不等式，于是决策单调性分治，使用决策单调性分治指针移动的trick，需要莫反一下算$c$，复杂度$O(n\log^3 n)$，因为每个数贡献不超过$\log$次，而因数个数和是$O(n\log n)$，$k$还有一个$\log$。
arc153 E.
考虑怎么算$f$。我们必然把所有$1$插到左边，于是找到第一个$1$，在它左边，我们必然把所有$2$插入到左边，这样的。也就是说我们倒着每次找到最小的字符，然后正着把剩下的塞进去。那么$y$必然形如$111…1222…2333…3444…4…999…9???…???$，其中$?$就比较随意了。每个$?$中的数可以插进一个前缀，乘起来即可。我其实是没太懂啊?
洛谷9150.
我们走到点$i$，能且只能尝试通过已经走过的点走到$k_i$。考虑一个置换环，显然一个环不可能走出去，把环复制一倍，那么如果$i$能到$k_i$，$k_i$的连通性$i$可以保留。那么看看$k_i$在链上最远走到哪，比如是$x$，如果$x$能到$i$，$i$能到$k_x$，那就把$k_x$加入。
考虑我们定义链上一段是强的，当且仅当从第一个点进入，可以