要告别了吗。
对于给定的前缀，从大到小贪心放左边优还是放右边优。考虑如何维护每个前缀的答案。令 \(L_i\) 为 \(i\) 左边比他大的元素个数，\(R_i\) 表示右边比他大的元素个数，\(ans=\sum \min(L_i,R_i)\)。考虑计算每个 \(i\) 对于答案的影响，从大到小枚举值域，用树状数组维护 01 序列，二分求出第一个位置使得 \(L_i\) 优于 \(R_i\)，对于答案的贡献就是前一段加（前缀 \(1\) 的个数减 \(L_i\)），后缀加 \(L_i\) 即常数，用线段树维护矩阵或者一些标记即可。\(O(n \log n)\)。
设 dp 状态为 \(f_{u,k,0/1,0/1}\) 表示，\(u\) 子树内除了自己要选的那个区间以外，额外要选 \(k\) 个非空区间，并且这 \(k\) 个区间是否要包含一个前缀，和包含一个后缀。（如果选的区间是前缀或者后缀那么可以为空）
转移时，枚举儿子 \(v\)，设 \(g_{v,k,0/1}\) 表示考虑到儿子 \(v\)，前面的儿子一共选出了 \(k\) 个额外区间，这 \(k\) 个区间里有没有一段最后的后缀区间。设这个儿子的左端点和上一个儿子的右端点相差为 \(len\)。列出以下转移：
- \(g_{v,k_1,x}+f_{u,k_2,y,z} \to g_{v,k_1+k_2,z}\) （我们不选中间的那段 \(len\))
- \(g_{v,k_1,x}+f_{u,k_2,y,z}+len \to g_{v,k_1+k_2+1-x-y,z}\) （选中间的 \(len\)，只要能和一边合并就会少一个区间）
（由于保证线段端点两两不同，所以我们不会在第二种转移中合并出空的东西）
我们在考虑第一个儿子的时候还要记录是否选了一段前缀区间才能从 \(g\) 转移到 \(f\)。
- \(g_{v_1,k,x,y}=f_{v_1,k,x,y}\)
设 \(pre\) 指 \(u\) 最前面那段区间的长度，\(suf\) 是最后一段的长度。我们最后把儿子都合并完之后这两段区间也给合并上。依次进行以下转移：
- \(g_{v_{lst},k,x,y}+pre \to g_{v_{lst},k+1-x \ or \ k+1,1,y}\)
- \(g_{v_{lst},k,x,y}+suf \to g_{v_{lst},k+1-y \ or \ k+1,x,1}\)
最后枚举当前节点选择的区间是前缀/后缀/中间的区间就可以把 \(g\) 转移到 \(f\)。
时间复杂度分析：我们可以对 \(L,R\) 离散化一下，可以发现离散化后每一段肯定都是一起选或不选的（证明考虑对于一个方案可以把端点调整到关键点处每个区间依然可以保持非空）（这同时让我们处理叶子的 dp 值时可以只考虑全选的情况），所以一个子树内最多选出来 \(O(siz)\) 个区间， \(f\) 的第二维是 \(\min(dep_u,siz_u)\)，转移是经典的背包合并，所以复杂度 \(O(n^2)\)。
背包 dp 一定要注意边界问题，具体要 for 到哪里，哪些 dp 是有效的。不要想当然，dp 数组要赋初值 \(-\inf\)。不然的话调试会很痛苦。
树链剖分，转化为若干段重链前缀和后缀的查询。把每条重链离线下来扫描线，暴力把轻儿子信息全加入，使用数据结构维护深度相关信息。具体的，前半段是一个三维偏序，后半段是一个二维偏序。时间复杂度 \(O(n log^3 n)\)（小常数）
考虑 dp。我们可以只在状态中记录最后两个数的差，设 \(f_{i,x}\) 表示 \(a_{i+1}-a_i=x\) 时是否存在方案。假设当前 \(b_i=d\)。我们考虑 \(f_{i,x}\) 能转移到谁。
当 \(x \ge 0\) 时：
- \(x=d\) 时 \(f_{i,x} \to f_{i+1,j} ( -d \le j \le 0)\)
- \(x<d\) 时 \(f_{i,x} \to f_{i+1,-d}\) 和 \(f_{i+1,d-x}\)
\(x \leq 0\) 可以发现转移的过程中和 \(x \ge 0\) 的部分完全对称，只维护一边就好。
考虑维护 \(f\) 值是 \(1\) 的位置。可以发现，我们每次是把 \(>d\) 的部分直接扔掉。如果之前已经有 \(d\) 就把 \([0,d]\) 全部赋值为 \(1\)。否则把 \([0,d]\) 的部分前后翻转，然后插入 \(d\)。我们可以记一个翻转标记（\(x'=kx+b\)）就可以用双端队列维护全 \(1\) 段来实现这个过程。
如何构造？我们从最后的状态里随便取一个合法的位置，往前推的过程中，如果他变成当前的 \(d\) 里，那么上一步可以等于任意一个 \([-d,0]\) 里的合法位置，我们在正着转移的时候记录一下。否则他要么是从上一个 \(d\) 转移来的，或者从 \(d-x\) 对称转移来的。正着 dp 的时候再记录一下有没有 \(d\)，优先走 \(d\) 的转移即可。
首先把每个点看成不动或者向右移动 \(2d\)。用 \(D\) 表示 \(2d\)。
我们可以把整个数轴排成二维平面上的一个矩阵：
\[\begin{array}{c} 0 & D & 2D & \cdots \\ 1 & D+1 & 2D+1 &\cdots \\ 2 & D+2 & 2D+2 & \cdots \\ \cdots & \cdots & \cdots & \cdots \end{array} \]当 \(D\) 比较小的时候，我们可以设 \(f_{i,s}\) 表示当前考虑到位置 \(i\)，\([i-D,i-1]\) 的被覆盖状态是 \(s\)。转移枚举当前位是否被覆盖，check 一下 \(x+2D=i\) 的那些限制是否满足条件。复杂度 \(O(m2^D)\)，其中 \(m\) 是值域。对应到矩阵上也就是从第一列开始做从左到右，从上到下的轮廓线 dp。
当 \(D\) 比较大的时候，考虑从矩阵的第一行开始做从上到下，从左到右的轮廓线 dp。我们依旧可以在 dp 的过程中 check 我们的限制。不过此时我们 dp 到最后一行之后还需要知道第一行的状态是什么才能计算贡献。此时要在 dp 前枚举第一行的状态。复杂度 \(O(m2^{2m/D})\)。
取分块阈值为 \(\sqrt{2m}\) 可以在 \(O(m2^{\sqrt{2m}})\) 的时间复杂度内解决问题。
dp 的计算贡献可以写成每选一个位置就 \(+a\)，每选两个相邻的位置就 \(-a+b\)。
我们可以发现，在每一次加入一个左括号的时候，它的颜色是之前一段连续的右括号的或。每一个右括号无论询问的区间是啥对应的左括号都是唯一确定的。
可以发现，这种左括号之间的传递关系变成了一颗树，每一次我们干的事情就是，从 \(l\) 开始扫到 \(r\)，把 \(a_{fa_i}\) 或上 \(a_i\)。问过程中有几个 \(1\)。
也就是说，有多少个 \(l \le u \le r\)，满足 \(u\) 的子树里有 \(l \leq v\) 使得 \(a_v=1\)。
如果没有修改操作，可以考虑从后往前扫一遍，由于 \(fa_i>i\)，所以每个 \(1\) 的贡献一定是他到他祖先里第一个 \(1\) 那一段。
怎么支持修改呢？这时需要这颗树的性质：由于他是由类似括号匹配的定义而来，我们可以发现每一个左括号的子树里的所有左括号在编号上一定是连续的（这里的编号指他是第几个左括号）。
考虑一个部分分：询问的 \(r=n\)，这个时候我们相当于求 \([l,n]\) 里的所有黑点到根的链并的节点个数，类似于求虚树节点数。我们可以把黑点按 dfs 序排序，所有点的深度和减去 dfs 序相邻点对的 LCA 深度和就是答案。由于这颗树满足节点编号就是某种 dfs 序，所以可以用线段树方便的维护修改查询。具体的，在线段树上维护区间内第一个以及最后一个 \(0/1\) 的位置，\(0\) 的答案和 \(1\) 的答案以及翻转标记即可。
如果询问的不一定是一个后缀呢？我们此时计算出 \([l,n]\) 的答案与 \([r+1,n]\) 的答案，可以将两者相减，但此时还不是最终我们想要求的答案。考虑一个 \(u \ge r+1\) 满足他的子树里有 \([l,r]\) 里的黑点但没有 \([r+1,n]\) 中的黑点，这种点我们会算多，需要在答案里减去该类点的个数。
这种点的集合会是一个什么样的东西呢？我们设 \(r\) 前面第一个 \(1\) 是 \(p\)。对于一个的 \(u \ge r+1\)，假设他的子树里存在一个 \([l,r]\) 中的黑点 \(x\)，由于 \(p\) 是 \([l,r]\) 里编号最大的黑点所以 \(x \leq p\)。根据每个子树都是区间的性质，\(u\) 子树内必然包含 \([x,u]\) 这段区间，也就必然包含 \(p\) 点。所以 \(u \ge r+1\) 且 \(u\) 子树内有 \([l,r]\) 内的黑点当且仅当 \(u\) 在 LCA(p,r) 到根的路径上。
此时，我们只用考虑这条链上有哪些点的子树里存在 \([r+1,n]\) 中的黑点。注意到此时 \(u\) 子树中必然有 \(r\)，也就必然有 \([r+1,u]\) 中的所有点，并且子树中的点不超过 \(u\)，所以我们只用考虑 \(u\) 是否包含 \(r+1\) 之后的第一个黑点，设其为 \(q\)。要找的不合法点集合也就呼之欲出了：LCA(p,fa[r]) 到 LCA(p,r,q) 的这一条路径。注意它不应该包含端点 LCA(p,r,q)。
注意到我们实际上维护的是一个森林而非树，我们可以把每颗树的根都连到 \(n+1\) 这个虚拟点上就行了。
使用 \(O(n \log n) - O(1)\) 求 LCA 的方式优化线段树的 pushup 就可以做到 \(O(n \log n)\) 的时间复杂度。
设 \(f_u\) 为只考虑 \(u\) 子树内的路径，\(g_u\) 表示只考虑子树外的路径。通过这两个数组可以 \(O(n)\) 计算出答案。
计算 \(f_u\) 可以考虑转移时枚举 LCA 是当前点的路径，设 \(f'_u\) 表示 \(fa_u\) 除去 \(u\) 这颗子树后其他儿子的 \(f\) 值之和。我们用树状数组维护 \(f'\) 的单点加链求和就可以从下往上计算出 \(f_u\)。
计算 \(g_u\) 时，考虑从 \(g_u\) 转移到 \(g_v\)。\(u\) 点不选路径就是用其他子树的 \(f\) 和 \(g_u\) 的和转移；选了一条 LCA 为 \(u\) 的路径，相当于 ban 了某些儿子不能用这条路径转移；
选了一条 LCA 在 \(u\) 上面的路径，相当于 ban 了一个儿子不能转移。我们在从上往下枚举到某个 LCA 时可以把这条路径的答案存在端点处，转移的时候查询子树 max 即可。用线段树维护。
总时间复杂度 \(O(n \log n)\)。
首先我们用 burnside 引理，设 \(f(i)\) 长度为 \(i\) 的环的方案数。\(\text{ans}=\sum\limits_{i=0}^{n-1} f(\gcd(n,i))=\sum\limits_{i|n}f(i) \varphi(\frac{n}{i})\)。
考虑如何计算 \(f(m)\)，相当于把划分成若干段，每段选一个点的方案数。可以考虑找规律/手推矩阵树定理/环上dp。设 \(f_{n,0/1}\) 表示选到第 \(i\) 个位置，当前这一段选没选过点，每次 \(0 \to 0,0 \to 1,1 \to 0\) 有一种转移，\(1 \to 1\) 有两种转移。注意第一段和最后一段可以合并，我们可以发现矩阵快速幂矩阵上的 \(a_{0,0}\) 和 \(a_{1,1}\) 的和就是我们想要的东西。
由于每一次我们要对每一个 \(n\) 的约数计算矩阵快速幂，我们可以考虑预处理 \(x^{aB^b}\)。（注意这么做的话不能向量乘矩阵，如果用手推矩阵树或者其他方法直接得到线性递推就可以向量乘矩阵）
枚举一个分界点，可以得到 $F(n)=\sum\limits_{i=1}^{n-1} k^{ \lceil \frac{i}{2} \rceil + \lceil \frac{n-i}{2} \rceil} $，从中间去掉算重的部分。设 \(g(n)\) 表示划分方案唯一的串，可以发现一个能划分的串，他一定能够表示成一个划分方案唯一的串作为一个周期重复若干次。如果重复了 \(m\) 次那就会算重 \(m\) 次（比如 ABAB 可以表示为 A,BAB 以及 ABA,B）。
所以可以得到 \(g(n)=f(n)-\sum\limits_{d|n}g(d)\frac{n}{d}\)。可以直接 \(O(n \log n)\) 递推得出。
考虑最后第 \(i\) 个位置上的答案是啥。可以发现他就是前缀最大值和后缀最大值取较小的那个减当前位置的高度。考虑全局最大值的位置，他前面的只跟前缀最大值有关，后面的只跟后缀最大值有关。
我们考虑枚举全局最大值，设 \(f_{i,j,k,o}\) 表示前 \(i\) 个删 \(j\) 个，保留的东西里最大值是 \(k\)，答案的奇偶性，有多少种方案数。后缀也同样 dp。算答案的时候枚举最大值是谁，用前后的 dp 合并。我们可以把相同的数字看成前面那个东西更大。
由于我们最多删 \(25\) 个数字，那全局最大值只有 \(25\) 种。所以我们 dp 的时候最大值的那一维只用记 \(25\) 种。时间复杂度 \(O(nk^2)+O(k^3)\)。空间上，我们只用记录 \(k^2\) 个 dp 值用于合并，dp 时使用滚动数组。
考虑轮廓线 dp。记录集合划分表示连通性。而且可以发现颜色一定是黑白交替。钦定 \(a_{1,1}\) 是白色的。转移的过程中，如果这个时候某种颜色有两个及以上的联通快，我们不能把这种颜色的某个联通快封死。如果从有黑色的状态转移到全白，可以直接统计答案了（之后必须填白色）。如果从任意状态转移到了全黑色那么也是直接统计答案。最后我们统计最后一行不是全黑的方案数。注意这里全白是可以转移到全白的。
考虑点分治，计数跨过根的合法路径条数。每次我们试图把 \(u\) 到根的串和 \(v\) 到根的串拼起来。可以发现，较短的那一段一定是较长的那一段的一个后缀，并且较长的那一段除去这个后缀的那个前缀是一个回文串。这提示我们把每个点到根的串插进 AC 自动机里。假设较长的那段是 \(u\)，那么 \(u\) 在 fail 树上到根的那条链上的节点有可能作为他的后缀。
我们找出 \(u\) 点到根的最长回文前缀，可以发现，每一个回文前缀都是最长的回文前缀的 border。而一个串的 border 可以被描述为 \(\log\) 段等差数列。所以可以将问题转化为，每次查询一个点到根的链上有几种长度满足他在某一个等差数列段里。我们考虑对公差根号分治，在 fail 树上 dfs。
- \(\le B\) 的公差我们记录 \(cnt_{d,r}\) 表示 \(\bmod d=r\) 的长度里有几个终止节点，把查询在树上拆成两个差分一下，每次 dfs 到一个点对于每个 \(d\) 修改一下。
- \(>B\) 的公差直接在查询的时候暴力跳，dfs 的时候维护一下每个深度有几个终止节点。
求最长回文前缀以及 border 等差数列段可以在 trie 树上递推一遍。
时间复杂度可能是 \(O(n \sqrt n \log n)\) 的，不是很会分析。常数很小，随便过。实测取 \(B=2\) 的时候最快，可能是数据太水。
如果起点在 \(1\) 终点在 \(n\)，我们保留考虑一座天桥，我们一定可以调整使得最优路径是从最左边的位置上来，以及从最右边的位置下去。这时我们保留每个天桥端点以及正下方第一个在另一座天桥上的点，连边跑最短路即可。
对于起点终点任取的情况，我们设 \(p\) 为起点往左走遇到的第一座高度比这作天桥高的建筑，\(q\) 为往右，我们此时把该天桥分成 \([l,p],[p,q],[q,r]\) 三段，每段做上述处理即可。对于终点做同样的处理。连边的实现可以考虑扫描线 set 维护。可以发现每个天桥至多会产生 \(12\) 个关键点，实测最后数据中去重后不超过 \(8n\) 个关键点。时间复杂度 \(O(n \log n)\)。
考虑值域分块，块内的询问处理可以考虑并查集上维护链表很方便的维护 merge 和撤销，查询把链表上的数全拉出来求第 k 大就好了。由于操作树形态固定，可以考虑预处理出每次并查集合并的时候操作的根是谁。空间线性时间单根号。
把每个物品看成向量 \((V,m)\)，按照斜率排序，在平面上首尾相接，形成一个从 \((0,0)\) 到 \((sum_V,sum_m)\) 的下凸壳，我们用一条斜率为 \(\frac{sum_V}{sum_m}\) 的直线从 \((0,0)\) 出发往下扫，每个时刻把凸壳分成三段，如果满足第二段是总和的一半就直接得到方案。二分一下在 \(x\) 轴上的截距即可。
考虑计算贡献的方式，枚举一个值 \(x\)，计算最小值 \(\ge x\) 的连通块个数，这样我们就把权值转化成了 \(01\)。每次动态把一个 \(1\) 改成 \(0\)，查询树上每个全 \(1\) 联通快的权值之和，这里 \(siz\)。很明显是一个 ddp 可以处理的问题。
设 \(f_u\) 表示 \(u\) 子树内的贡献之和，\(g_u\) 表示包含 \(u\) 点的联通快贡献和。
对于 \(a_u=1\) 有：
- \(g_u=\Pi_{v\in son(u)} \frac{1}{2}(g_v+1)\)
- \(f_u=g_u+\sum_{v\in son(u)} (f_v-\frac{1}{2}g_v)\)
对于 \(a_u=0\) 有：
- \(g_u=0\)
- \(f_u=\sum_{v\in son(u)} (f_v-\frac{1}{2}g_v)\)
对每个点维护轻儿子的 \(g_v+1\) 的乘积、 \(f_v\) 之和以及 \(g_v\) 之和，转移写成 \(3 \times 3\) 矩阵的形式。为了防止修改乘积时除 \(0\) 可以写线段树（但是据说原题没卡/卡不掉）。
如果和 \(S<0\) 或者 \(S=0\) 且有小于 \(0\) 的数直接无解。考虑序列上应该怎么做。考虑前缀和数组，操作直接转化为相邻两项，我们的目标是排序，那么答案就是逆序对数。
考虑把环变为无限长数列，向前和向后都无限复制自身，再求一个相对的前缀和。如果我们定义下标 \(\bmod n\) 相同的位置是一类，每一类里相邻两个都差 \(S\)，每次操作就是 swap 相邻的两类。
我们考虑每两个类对答案的贡献，相当于后面那类每 swap 一次就会加上 \(S\)，目标是让这两个东西归并之后是不降的。
所以此时答案就等于 \(\frac{1}{2}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \lceil \frac{|s_i-s_j|}{S} \rceil-\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} [s_i<s_j]\)。设 \(r_i=s_i \bmod S\)，前面那个东西按余数做个二维偏序就好啦。
可以发现，一个左侧的点至多连两个右侧的点。我们考虑把这两个点连边，如果是同一个点就连自环。由于保证一定存在匹配，所以最后每个联通块一定是树或者基环树。我们的任务是给边定向，定成某种方向有一个权值，保证每个点入度 \(\leq 1\) 的同时最大化权值和。
对于基环树，只有环可以有两种决策，逆时针或者顺时针，修改的时候改一下对应的权值和就好了。
对于树，对每个点维护他作为根的时候的答案。修改就在线段树上区间加维护全局 max 就好了捏。
先选两颗外向树，为最后染色的那些边。然后再把所有边定向使得可以进行欧拉回路。
感受一下，反正画画就会了。
需要做若干次正则二分图匹配。随机增广的做法可以做到 \(O(nk \log n )\)。
对于关键边必须是第一次到达某个点的限制，考虑建反图，跑欧拉回路的时候最后走关键边。
我们考虑如何处理一对询问 \((A,B)\)。我们把过程看作是先把 \(B\) 点删掉，如果一个点此时没有出度，那我们就继续把这个点也给删掉。一直这样进行下去。如果最后 \(A\) 被删掉了，那么 \((A,B)\) 就能成为答案。
对于当前选择的根，如果删掉点 \(u\) 后会导致 \(v\) 点也被删除，我们称其为 \(u\) 支配点 \(v\)。我们可以构建出支配树：考虑一个点的所有出度，他们在支配树上的 LCA 就是它的父亲。
需要注意的是，根可能支配自己。根的所有出度如果都会被自己删掉那么他们在支配树上的 LCA 就会支配根。所以实际上，我们最后得到的关系是一个支配基环树。对于环上的每个点，我们如果删掉他就会让这个基环树被删掉；对于不在环上的点，删掉它会使得子树里的点被删掉。
可以发现，我们可以把一个图变成基环树森林再统计答案。考虑按 \(k\) 从 \(1\) 枚举到 \(n\) 动态的维护基环树森林的形态。最开始的图是 \(n\) 个自环，每次我们枚举到点 \(u\) 我们就把这个自环去掉，他的出边都加到图中。
可以发现 \(u\) 之前一定是某颗树的根。
- 如果当前这个点 \(u\) 的出度都在自己这颗树里，把他们的 LCA 往 \(u\) 连一条边就好了。
- 如果所有出度都在另一颗树中，同样求出 LCA，我们现在就是是把 \(u\) 的子树接到 LCA 下面。
- 如果出度分散在不同的联通块，此时 \(u\) 并不任何点支配。但是随着合并的进行，可能在某一刻，\(u\) 的出边全都在某一个联通块里了。所以我们在加入 \(u\) 的时候往每个联通块里扔一个标记，每次合并两个联通块的时候把两个联通块都有的标记的计数器减一，减到 \(0\) 就需要把 \(u\) 重新拿出来，把出度的 LCA 和它连边。我们可以考虑用线段树合并维护这个过程就可以做到单 log。每次在 merge 两个叶子的时候处理一下计数器。开一个队列记录当前需要考虑的 \(u\)，每次拿队首出来做。计数器变成 \(0\) 就 push 进去。
考虑怎么算答案，即对于每个时刻的支配森林求出有多少个点对 \((u,v)\) 满足 \(u\) 能到达 \(v\)。
答案就是每个点的 siz 和也就是 dep 和，我们要维护的操作是把一个树根接到某个点的儿子处。考虑在 LCT 上维护 Link，求某个点的 dep，求 LCA，求联通块 siz 的操作就可以做了。
如果过程中出现了一个新的基环树，需要特殊处理一下。由于每个联通块只会变成一次基环树，我们可以直接暴力的通过某些手段 \(O(siz)\) 的处理这颗基环树的答案。
但是要注意的是，一颗基环树虽然不会再往外连出出度，但是里面的点之后有可能作为其他的点的出度。为了方便后续的答案计算，需要把基环树上的环点的 dep 人为的修改一下。具体的，把根的 dep 改为环长，其他环点的 dep 改成 \(0\) 就好啦。
以及，每颗树的树根有可能编号大于当前枚举的 \(k\)。可以最开始每个点的 dep 设成 \(0\)，加入这个点的时候加上对答案的贡献，再把 dep 改成 \(1\)，这样算出来的 dep 才是对的。
总体的时间复杂度为 \(O(m \log n)\)。可以发现这颗 LCT 由于 Link 操作都是把一个树根接到另一个儿子上所以只需要 access 而不需要维护懒标记进行 makeroot，常数是很美丽的。
另一个做法，我们可以先直接求出 \(k=n\) 时的基环森林。再考虑在最后的状态上统计答案。
首先应该怎么求出 \(k=n\) 时的状态呢？如果我们现在有一个根，我们可以直接在图上模拟一遍求 LCA 加边的过程，用倍增维护就好。但是我们不能暴力的枚举一个根然后做一遍这样的事情。因为一个点为根的支配树可能是另一个点为根的支配树的子树。所以问题就变为了找到那些最厉害的根。
我们考虑不断的缩图。考虑一个点 \(u\)，如果他只有一条出边连向 \(v\)，那么我们就可以把 \(u\) 扔了，因为 \(v\) 的支配树一定包含他的支配树。此时我们把 \(u,v\) 缩成一个点，并且把之前连向 \(u\) 的边全部接到 \(v\) 上。重复这个过程，直到图中每个点的出度都 \(\ge 2\)。此时图中的每个点都可以成为一个根/一个基环树环里的某个点。
维护缩图的过程可以使用线段树合并，可以发现和第一个做法中维护的信息大同小异，每个联通块的根处维护有那些点连向他，每次合并的时候相当于把两者都有的点的出度减一，每次找到出度变为 \(1\) 的那些点执行合并操作即可。
之后我们考虑怎么求出每个 \(k\) 的答案。首先可以发现每个时刻的图都是最后的图的子图，并且每条边都是在 \(k\) 逐渐增大到某个值的时候出现。这个值可以在求出基环树的过程中维护出来。具体来说，考虑构建基环树的过程中考虑到了当前点 \(u\) 以及他的出度的 LCA，\(u\) 连向 LCA 的这条边就是 \(u\) 到 LCA 上的每一条链上的所有边的权值的 max。于是我们在倍增的时候多维护一个链上权值的 max 即可。
之后考虑统计答案。我们拎一个环上的点当根搞一颗外向树。这个图会存在至多一条返祖边。我们把答案分为直上直下和必须经过返祖边的两部分进行统计。
- 对于直上直下的部分，可以并查集维护 siz 和最浅的那个点，很好做。
- 对于经过返祖边的部分，我们可以巧妙地把最开始钦定的根设置成使得那个返祖边是环上边权最大的边的那个点。这样我们就能保证在加入返祖边的时候，整个环就完整的形成了。
- 加入返祖边之前只有直上直下的贡献。
- 加入返祖边时，由于只会加入一次，我们可以暴力的 DFS 一遍算贡献。
- 加入返祖边后，可以发现如果一对 \((u,v)\) 满足从 \(u\) 走到 \(v\) 必然要经过返祖边那么一定是形如 \(u\) 处于 \(v\) 在环上的投影以下一直到返祖边端点的那一条链上。于是也可以很方便通过并查集的 siz 信息计算贡献。
最后整体的时间复杂度依然是 \(O(m \log n)\)，来源于线段树合并以及倍增求基环树。
贡献等于最大的 \(\frac{n-1}{2}\) 个边的权值减去剩下的 \(\frac{n-1}{2}\) 条边的权值。由于我们要最大化这个东西，所以我们把它看做从所有边里随意选一半系数为 \(1\) 和一半系数为 \(-1\) 的和，取最大还是一样的。
那么就可以上 WQS 二分了。每条边看成两条边，边权为 \(w\) 和 \(-w+mid\)。求最大生成树就好了。
注意 \(n-1\) 是奇数时事实上中位数没贡献，只用选 \(n-2\) 条边来贡献。\(n-1\) 是偶数就是 \(n-1\) 条边。或者看成选若干对匹配，选的要是偶数条边。
考虑把一个点 \((x,y)\) 对应到一个区间 \([x,n-y]\)。对于 H 操作而言，相当于给定一个 \(x\)，对每一个区间 \([l,r]\)，如果 \(l \leq x \leq r\)，那么就把这个区间变成 \([x,r]\)。对于 V 操作就是变成 \([l,x]\)。
考虑如果所有区间都包含某一个 \(p\)。那么我们执行一个值为 \(x\) 的操作，若 \(x \leq p\)，那么 V 操作相当于把这个区间的右端点直接设为 \(x\)，且该区间就不会再包含 \(p\) 了。H 操作相当于所有左端点对 \(x\) chkmx，并且不会出现不再包含 \(p\) 的情况。
我们可以把这个过程放在线段树的分治结构上进行考虑。我们把每个区间存在最小的包含它的区间处（类似猫树的结构）。一个区间被划分后有可能跑到左儿子或者右儿子里面去了，我们要用数据结构来维护这个过程。
在线的做的话我们对每一个线段树节点开一个线段树维护左右端点 chkmx 和 minpos 就能做了，时间 log 方但是空间也带 log。考虑离线把空间变成线性的。我们最开始在根处处理所有的操作，按照时间顺序从前往后维护左端点，如果碰到一个 chkmx 操作把小于他的那些 \(l\) 拿出来 merge 在一起再塞回去。碰到一个 \([l,r] \to [l,x]\) 操作就把 \(l \leq x\) 全拿出来 pop 了，处理询问就开个数组记录一下第 \(i\) 个点当前的 \(l\) 是啥，如果已经似了就把询问也丢到儿子里面去。用堆和并查集上记录链表维护就好了捏。
那么就可以做到时间 \(O(n \log^2 n)\)，空间线性了。
标签：世界末日,可以,快乐,LCA,考虑,我们,dp,维护 From： https://www.cnblogs.com/acfunction/p/17504878.html