P13644 K-LCA
给出树和 \(k\)，每次询问给出区间 \([l,r]\)，找到选择 \(k\) 个区间内的点使得 LCA 深度最大。
\(n,q\le 10^5,1<k\le n\)。
考虑回滚莫队，每次加入一个点，二分最深的子树个数 \(\ge k\) 的祖先，可以做到两个 \(\log\)。
考虑树链剖分，标号是先标号轻儿子，再标号重儿子。
则同一条重链上的点对应的 dfn 区间右端点相同。
这样就能线段树二分处理一条重链。
初始先得到答案在哪条重链上再二分即可做到单 \(\log\)。
P3206 [HNOI2010] 城市建设
修改边权，求最小生成树。
重温。
动态边权最小生成树。
已知原图的一个边集 \(S\)。
-
若将 \(S\) 边权设为 \(inf\)，找出最小生成树，则非树边是没用的。
证明：将 \(S\) 边权降低，则根据
LCT维护最小生成树的过程，只会替换树边。 -
若将 \(S\) 边权设为 \(-inf\)，找出最小生成树，则不管 \(S\) 取什么值，树边都是要用上的。
证明：根据
kruskal维护最小生成树的过程，当 \(S\) 的边全取最小值时，这些树边还能连接两个联通块，则若 \(S\) 边权增大，这些树边还能连接。
考虑 cdq 分治，每次跑到一个点 \([l,r]\)，维护一个边集 \(f\)。
将 \([l,r]\) 要修改的边设为 \(-inf\)，求出最小生成树，将树边直接缩起来，并从 \(f\) 中删去。
所以往下的联通块个数为 \(\mathcal O(len)\)。
将 \([l,r]\) 要修改的边设为 \(inf\)，求出最小生成树，将非树边从 \(f\) 中删去。
所以往下的边数也是 \(\mathcal O(len)\) 的。
时间复杂度 \(\mathcal O(n\log ^2n)\)。
P13342 [EGOI 2025] Wind Turbines / 风力涡轮机
每次询问先将 \([l,r]\) 的缩到一个联通块，求最小生成树。
666。
考虑问题即在最小生成树上删去 \(r-l\) 条边，使得每个关键点独属于一个联通块。
暴力想法就是先将 \([l,r]\) 联通，再加入树边求最小生成树。
考虑隐式地求解，从小到大加入树边，若连接的两个联通块都存在 \([l,r]\) 内的点，则这条边不取，其他情况都取。
即重构树上某个点左右子树都有 \([l,r]\) 内的点，就有贡献，发现这些点即 \([l,r]\) 的两两 LCA 集合，只有 \(r-l\) 个。
则暴力就是建出虚树即可。
类似铃原露露，求出支配点对。
启发式合并时求出前驱后继，共有 \(\mathcal O(n\log n)\) 个点对。
但是我们要求贡献不能算重。
考虑扫描线，对于当前 \(r\)，对每个点 \(u\) 维护 \(l\le c_u\) 则这个点有贡献。
可以事先对每个 \(u\) 的支配区间处理一下，使得左右端点单调。
那么修改就变成了区间加，单点查。
时间复杂度 \(\mathcal O(m\log m+n\log^2n+q\log n)\)。
P13345 [EGOI 2025] IMO
有 \(n\) 个人，\(m\) 道题，问最少公开多少道题的分数，使得排名与最终相同，且唯一确定。
\(n\le 2\times 10^4\)，\(m,k\le 100\)。
先有知道上一个人分数的右端点，枚举当前人公开题数，找到一个最小的无交的分数的左端点的 dp。
根据值域上无交，可以将若干东西分析成 \(mk\)，就做完了。
xor
给定正整数 \(n,a,b\) 。
你需要选取 \(0\le x<a, 0\le y<b\) ，设 \(S_1=\{i:0\le i<n,i \bmod a=x\}\)，\(S_2=\{i:0\le i<n,i \b mod b=y\}\) ，然后最大化 \(n−|S_1\oplus S_2|\) ，即 \(n−|S_1|−|S_2|+2|S_1 \cap S_2|\)。
要求单次询问 \(\log n\)。
\(n\le 10^{18}\)，\(a,b\le 10^9\)。
答案可以表示为 \(n-(\lfloor\frac{n}{a}\rfloor+[n\bmod a>x])-(\lfloor\frac{n}{b}\rfloor+[n\bmod b>y])+2(\lfloor\frac{n}{lcm}\rfloor+[n\bmod lcm>z])\)。
先计算固定的系数，然后 \(n\leftarrow n\bmod lcm\) 答案不变。
通过 \(a,b\) 去计算 \(z\) 不太好，考虑枚举 \(z\)，这样每次的 \(a,b\) 的变化都是 \(+1\)。
那么就是在一个 \(a\times b\) 的循环网格上，每次往右上角走。
问能否在 \(n\) 次操作内走到 \((a_0,b_0)\) 的右上角。
考虑先算出第一次合法时走到的是哪个点，最后算一下走到这个位置是否不超过 \(n\) 步。
假设 \(a<b\)，不嫩发现可以转化为 \(a\times (b-a)\) 的情况，可以加速计算。
Cluster
\(m\) 个容量为 \(2\) 的栈，栈里共有 \(2n\) 个元素，其中 \(1,2,\cdots ,n\) 分别出现两次。
你每次可以选择两个栈 \(i,j\)，把 \(i\) 的栈顶弹出，压入 \(j\) 里。你需要保证操作后栈的大小仍然不超过 \(2\) 。特别的，如果操作后 \(j\) 的大小是 \(2\)，那么其里面两个元素必须相等。
你需要在 \(\lfloor\frac{3n}{2}\rfloor\) 次操作内使得每个栈内要么为空，要么是两个相等的元素。或者判断无解。
\(n\le m\le 2\times 10^5\)。
对栈顶和栈底连边。
则图形如若干环和若干链。
分别讨论几种情况即可。
鲍勃杂货店
给出一个后缀表达式，可以使用交换律，结合律（要求相同运算符），使得表达式的连续相等字符的段数最少。
\(s\le 5\times 10^6\)。
先考虑将表达式树上有连边的相同运算符缩起来，这样结合率就没用了，新树的同父亲的每个儿子可以任意排列。
我希望求出以每个颜色作为开头的子树最大答案。
发现若一种方案不是最大答案，则不优，故只需求出达到最大答案能以哪些颜色开头即可。
发现就是做一个二分图匹配，然后求每个点能否删去使得最大匹配不变。
争锋频道
给定点数为 \(2n\) 的无向图，求完美匹配方案数。
\(n\le 20\)。
考虑将任意两种完美匹配的边连起来的图形成若干个环。
每个环的边的虚实相错的。
考虑定义虚边的匹配为 \(2i,2i+1\)。
对每个环从最小点开始加边，每次加入一条实边，对应加入他的虚边，或者选择结束这个环，而直接记录当前有哪些虚边就能知道所有点集。
故可以处理出哪些虚边构成一个环的方案数，对其做 exp 即可。
写作
给出一棵树，以及一个排列，每次可以交换相邻数，求最少次数使得树上每个子树的点形成一个区间。
从下往上不好优化。
可以考虑从上往下聚拢，这样不影响内部的逆序对个数。
聚拢的时候需要求出两类之间的逆序对个数，考虑轻重链剖分，枚举轻儿子计算即可，信心使用线段树合并维护。
字符串
给出母串 \(A,B\)，定义一个串是好的当且仅当存在划分成偶数段的方式，使得每一段为 \(A\) 或 \(B\) 的子串，排列的顺序为 \(A\) 的子串和 \(B\) 的子串交替排列。
求长度 \(\le K\) 的好串个数，字符集为 \(A,C,G,T\)。
\(|A|, |B|\le 20\)，\(K\le 10^9\)。
考虑分成公有与私有字符处理。
对于一个匹配区间 \([l,r]\)，若 \((l,r)\) 存在公有字符，则一定可以切开调整。
故对于一个极长的私有区间 \([l,r]\)，匹配左端点一定是 \(l-1,l\)，右端点一定是 \(r,r+1\)。
对于极长的公有区间，一定不存在连续 \(3\) 个字符属于同一个匹配区间，否则可以调整。
故中间的匹配区间长度为 \([1,2]\)。
若当前属于公有区间，则需要记录 \(i-1,i\) 分别能否以 \(A,B\) 结尾，以及当前的字符。
若从公有区间进入私有区间，根据公有区间的结尾能否匹配，可以贪心以 \(l-1\) 或 \(l\) 开始匹配，这时候只需记录当前在谁的私有字符上，以及跑到的 sam 节点。
总信息可以做到 \(\le 144\) 个。
然后矩阵快速幂即可。
带权重心
https://www.cnblogs.com/caijianhong/p/19074425
从树上的任意一点出发到树上所有点的距离乘上目标点的点权和最小的起点一定是树的带权重心，\(k\) 次方仍然成立。
以任意点为根时，子树的点权和大于等于整棵树点权和的一半的点中最深的那个点是带权重心。
点带正权时，子树的点权和大于等于整棵树点权和的一半的点是根所在重链的前缀。
令任意一个节点为根，带权重心是带权 DFS 序的重心在树上所代表的节点的祖先，找到之后倍增往上跳到第一个“子树权值和大于等于 \(\frac{s}{2}\)”的点即可。
CF2138D
给出一个初始箱子状态，以及一个操作序列 \((x,p)\)，表示将第 \(x\) 个箱子推到 \(p\)，路径上的箱子会挤过去。
对于操作序列的所有排列方式，求每个点在所有方式下的最终位置之和。
\(n,q\le 5\times 10^3\)。
直接考虑求结束位置 \(\ge x\) 的方案数即可。
P14008 序列游戏
定义一个序列的权值是所有极长颜色段长度的平方的和。
已知序列 \(a\) 长度为 \(n\)，\(a_i\) 是在区间 \([l_i,r_i]\) 之间等概率选取的整数，对于所有可能的序列 \(a\) 求权值的期望。
\(n\le 2\times 10^6\)。
可以先求极长差分，问题变成求形如枚举 \(r\)，求出 \(\sum_{l=1}^{r}\max(0, \min_{i\in[l,r]}R_i-\max_{i\in[l,r]}L_i+1)a_l\)。
如果没有对 \(0\) 取 \(\max\)，直接维护 \(\min,\max\) 两个单调栈就能快速更新了。
否则考虑每次加入完单调栈后对开头不合法的位置弹出，复杂度均摊正确，更新也是可以快速做的。
P14009 数字游戏
sb 题。
P13997 【MX-X19-T6】「FeOI Round 4.5」はぐ
给出一棵树，每次询问给出 \((u,v)\)，定义路径点序列为 \(p_i\)，求 \(\oplus_{i=0}^{len-1}(a_{p_i}+i)\)。
\(n\le 2\times 10^5\)。
妈的怎么不是根号？？
先将 \(a_{p_i}+i\) 拆开独立，可以看成 \(a_{p_i}-dep_{p_i}+k\) 或 \(a_{p_i}+dep_{p_i}-k\)。
考虑拆位，\(a+b\) 第 \(k\) 位为 \(1\) 的条件：若固定 \(b\)，则要求 \(a\bmod 2^k\) 在至多两个区间中。
求路径上权值在一个区间中的点个数的奇偶性。
对值域扫描线。
单点加，路径查不好优化。
考虑转成子树加，单点查。
时间复杂度为 \(\mathcal O(n\log n\log V)\)。
AT_arc205_d
给出一棵树，求最大匹配，使得匹配的两个点不为祖先后代关系。
\(n\le 2\times 10^5\)。
考虑从上往下做，对于根节点的子树，若最大的 \(\le\) 其他的和，则可以全部匹配，否则可以证明存在一种最大匹配方式使得其他子树全部连到最大子树上了，递归求最大子树最多的匹配数即可。
括号序列(bracket)
给出长度为 \(n\) 的括号串，每个左括号有正整数权值 \(a_i\)，定义一个子序列是合法的即他组成的括号串合法，定义合法子序列的权值为所有左括号的权值和。
\(q\) 次询问，求 \([l,r]\) 合法子序列的最大权值。
\(n,q\le 2\times 10^5,a_i\le 10^9\)。
这不是我们“推箱子”吗？
另外的性质：括号串的最大匹配数为右括号个数 \(+\) 前缀最小值。
从左往右就是维护剩余左括号的堆，加入右括号时查找最大值匹配。
从右往左就是定义右括号权值为 \(0\)，并于当前已经匹配的左括号放入一个堆中，加入左括号时，如果最小值比他小就替换掉。
然后考虑猫树合并，左半区间剩下若干左括号，右半区间有若干匹配左括号和若干剩余右括号，合并就相当于总体求个前 \(k\) 大和。
时间复杂度 \(\mathcal O(n\log^2 n)\)。
你的名字
有 \(n\) 个字符串，每次操作可以同时将 \(26\) 个字符各自改成某种字符，或者问 \(S_x\) 在所有字符串里的排名。
\(n,q,L\le 5\times 10^5\)。
当修改发生合并了就重构。
否则只需考虑与串 \(i\) 的 \([1,j]\) 相同，且 \(j+1\) 位为字符 \(c\) 的个数就能计算贡献。
统计一下即可。
树的直径
给出一棵树，每条边权值取 \([0,1]\)，求所有方案下的直径数量（端点不同）之和。
\(n\le 3000\)。
广为人知
网格(grid)
求多少长度为 \(m\) 的序列满足 \(0\le x_i\le b^i-c\) 且 \(\sum_{i=1}^{x_i}\le n\)。
考虑容斥：
后面的东西可以提出来，令 \(A=n+m+k(c-1)\)，则有：
展开组合数：
后面的式子是 \(\mathcal O(m)\) 次的多项式，设为 \(\sum_{l}a_lx^l\)，则枚举 \(l\)，计算所有合法 \(s\) 的 \((\sum_{i\in s}b^i)^l\) 即可。
先不考虑合法，设 \(f_{i,j,k}\) 表示考虑前 \(i\)，\(|s|=j\)，的 \(k\) 次方，有转移：
再考虑合法条件，发现 \(\sum_{i\in s}b^i\) 不会进位，直接在数位 dp 上做这个 dp 即可。
)
)
安装mysql8.4.5(建议安装glibc2.28版本))
