给定一个序列，求选出一堆不相交的子区间，每个子区间的 $\gcd$ 相同，要求最大化选出的个数，并求出对应方案数。
其中 $1 \le n \le 10^5, 1 \le a_i \le 2333333$。
首先我们知道一个结论，对于固定的左端点，它后面所有区间的 $\gcd$ 最多变化 $\log$ 次。
考虑四元组 $(x,i,l,r)$ 表示左端点为 $i$，右端点在区间 $[l,r]$，所有区间的 $\gcd$ 为 $x$，枚举端点二分即可。
将相同 $x$ 并在一起按顺序处理，令 $dp(i)$ 表示以 $i$ 结尾的最大值和方案数。
加一个四元组也就是从 $[1, i - 1]$ 中选一个最优决策（并且维护最优决策的方案数），覆盖（越往后越优）到 $[l,r]$ 中的每个位置。
线段树需要支持区间覆盖，维护区间和（最大值），并且打时间戳标记删除之前枚举的 $\gcd$。
给定一个序列 $a_1, a_2,\dots, a_n$，有 $n$ 个人排好队按顺序拿数字，每次只能选择序列首尾拿一个。
你是第 $m$ 个人，你很聪明，但是除你以外所有人都是随便拿。你可以至多选择 $k$ 个人，强迫他们拿首部还是尾部，问最坏情况下，你拿到的最大数字。
枚举你强迫多少人拿首部，剩余的人拿尾部，而你就是枚举剩余的人拿多少首部尾部，每种有两个选择，你取 $\max$ 后，对所有情况取 $\min$，最后对于枚举的东西再取 $\max$。
定义等价表示两个串，每种字母出现次数相同。定义 $t$ 对于 $s$ 的合法分解，$t$ 和 $s$，等价，至少再某些位置切开后，$t$ 和 $s$ 的对应串等价。
给定一个母串，每次询问当中的一个子串，是否可以存在一个串 $t$ 和它等价，但是不可分解。
串长等于 $1$，其本身与自己不可分解。
出现字母种类大于 $2$，存在不可分解。
出现种类数为 $2$，两端相同则都可以分解，否则存在不可分解。
一排灯，给定初始状态，有 $k$ 个开关，每个开关控制一个灯的子集，且任意 $3$ 个子集不交。对于每个前缀，求将它们同时点亮的最少开关数。
题目条件转化为每个灯最多出现在两个子集内。将开关建图，边为每个灯泡，问题变成你现在需要对每个点染色，表示开关状态。
先假装所有灯都亮，对图上的每个开关染色。具体地，就是看灯泡的状态决定相邻的开关状态。
于是，枚举前 $i$ 个灯，加入的时候，就是将某些点（对应联通块）连接，并加入答案。如果这个灯只出现在一个子集内，就钦定一下这个开关的颜色。
钦定不选，即设置大小为 $\infty$。
藏着一个数组，你现在要猜出当中不同数字个数。
维护着一个长度为 $k$ 询问队列，表示最近的 $k$ 次询问。每次询问会告诉你，你询问的位置是否在队列里出现，然后加入队列，如果队列长度大于 $k$，则删除队首元素。
你还有一个操作是清空队列。清空最多 $30000$ 次，询问最多 ${ 3n^2 \over 2k }$ 次。
考虑每种元素只保留第一个，删除每种元素之后的出现。
将序列按照 $k \over 2$ 的大小分块，块内的相同关系容易处理。
在 Easy Version 中，你只需要暴力枚举两个块即可，期望的次数 $\frac{k}{2}\frac{n}{k}(\frac{n}{k}-1)$ 次。
在 Hard Version 中，将块看成一个完全图，枚举所有边时，可以将块放在一起枚举，即将图划分成一堆路径。
具体地，可以枚举块间的距离 $i$，对于块号模 $i$ 同余的块，连在一起询问。下图中，每种颜色代表一次连续的询问。
对于每条路径，需要的次数是 $\frac{k}{2}(\text{边数}+1)$。
总的询问数大约是 $\frac{1}{2}\frac{k}{2}\frac{n}{k}(\frac{n}{k}-1) + \frac{k}{2}\text{路径数}$。
路径数大约是 $1 + 2 + \dots + \frac{n}{k}$，因此询问次数小于 ${ 3n^2 \over 2k }$ 次。
| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 70 | 4 | O | . | Ø | . | O | . | Ø | O | . | . | . | . | O |
定义 $E’$ 为我们当前找到的最小生成森林的边。在算法执行过程中，我们逐步向 $E’$ 加边，定义 连通块 表示一个点集 $V’\subseteq V$ ，且这个点集中的任意两个点 $u$ , $v$ 在 $E’$ 中的边构成的子图上是连通的（互相可达）。
定义一个连通块的 最小边 为它连向其它连通块的边中权值最小的那一条。
初始时， $E’=\varnothing$ ，每个点各自是一个连通块：
当原图连通时，每次迭代连通块数量至少减半，算法只会迭代不超过 $O(\log V)$ 次，而原图不连通时相当于多个子问题，因此算法复杂度是 $O(E\log V)$ 的。给出算法的伪代码：（修改自 维基百科 ）
$$
\begin{array}{ll}
1 & \textbf{Input. } \text{A graph }G\text{ whose edges have distinct weights. } \
2 & \textbf{Output. } \text{The minimum spanning forest of }G . \
3 & \textbf{Method. } \
4 & \text{Initialize a forest }F\text{ to be a set of one-vertex trees} \
5 & \textbf{while } \text{True} \
6 & \qquad \text{Find the components of }F\text{ and label each vertex of }G\text{ by its component } \
7 & \qquad \text{Initialize the cheapest edge for each component to “None”} \
8 & \qquad \textbf{for } \text{each edge }(u, v)\text{ of }G \
9 & \qquad\qquad \textbf{if } u\text{ and }v\text{ have different component labels} \
10 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }u \
11 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }u \
12 & \qquad\qquad\qquad \textbf{if } (u, v)\text{ is cheaper than the cheapest edge for the component of }v \
13 & \qquad\qquad\qquad\qquad\text{ Set }(u, v)\text{ as the cheapest edge for the component of }v \
14 & \qquad \textbf{if }\text{ all components’cheapest edges are “None”} \
15 & \qquad\qquad \textbf{return } F \
16 & \qquad \textbf{for }\text{ each component whose cheapest edge is not “None”} \
17 & \qquad\qquad\text{ Add its cheapest edge to }F \
\end{array}
$$
转载自 最小生成树 - OI Wiki
定义 half border 为长度不超过一半的 border。
给定一个长度为 $n$ 的字符串 $s$，$q$ 次询问，每次独立地删除一个子串 $[l_i,r_i]$，左右连起来，询问这个串的 half border 长度和。
其中 $1 \le n, q \le 5 \cdot 10^5$。
不妨设左半边比右半边长。
有两部分贡献：
border 不跨过边界，这部分就是原串长度小于 $\min(l_i, n-r_i+1)$ 的 border 之和，预处理后二分即可。
border 跨过边界了边界，下面分析这部分如何计算。
观察到，实际上是前缀的 border 位置和后缀的 border 位置求了交。
对前缀和后缀分别建立 KMP 的 fail 树。询问离线到前缀树上的每个点。
设有询问 $[1, l_i]$ 和 $[r_i, n]$，在前缀树上根到 $l_i$ 的所有点，若其出现在后缀树上 $r_i$ 的子树内，则其会被算一次长度的贡献。
但是，上面没有考虑到 half border 的长度限制，设路径上的一个点 $k$，$2(k+n-r_i+1) \le l_i+n-r_i+1$，也就是 $k$ 小于某个值。对于这个限制，在路径上二分，把询问二次离线到对应的点，使用树状数组容易计算答案。
UpSolved by XLor.
求每种本质不同好子序列的出现次数立方和。
令 $f(a)$ 表示子序列 $a$ 的出现次数，立方和展开一下，$\sum_{i=1}^{f(a)} \sum_{j=1}^{f(a)} \sum_{k=1}^{f(a)} 1$。观察上式的实际意义，等价于将序列复制三份，求公共好子序列的个数。举例来说，假如 $a$ 作为子序列出现了 $2$ 次，分别出现在位置序列 $a_1,a_2$，那么有公共子序列 $(a_1,a_1,a_1)$ 一直到 $(a_2,a_2,a_2)$ 共 $8$ 种对应。
记 $dp(i,j,k)$ 表示在第一个串以 $i$ 结尾，第二个 $j$ 结尾，第三个 $k$ 结尾的方案数。$dp(i,j,k)$ 有值当且仅当 $a_i=a_j=a_k$。
$$
dp(i,j,k)=[ a_i=a_j=a_k ]( \sum_{i’=1}^{i-1} \sum_{j’=1}^{j-1} \sum_{k’=1}^{k-1} dp(i’,j’,k’) [M(a_{j’},a_i)] )
$$
转移过程相当于同时从 $(i’,j’,k’)$ 走到 $(i,j,k)$，我们将这个过程拆开变成 $3$ 个阶段，钦定先走 $i$，再走 $k$，最后走 $j$。也就是说最后一步的 $j’$ 和 $i$ 两个之间必须可以走。
枚举 $i$，令 $f(i,j,k) = \sum_{i’=1}^{i=1} dp(i’,j,k)$, $g(i,j,k) = f(i,j,k) [M(a_j, a_i)]$。
$$
dp(i,j,k)=[ a_i=a_j=a_k ] ( \sum_{j’=1}^{j-1} \sum_{k’=1}^{k-1} \sum_{i’=1}^{i=1} dp(i’,j’,k’) [M(a_{j’}, a_i)]) \
dp(i,j,k)=[ a_i=a_j=a_k ] ( \sum_{j’=1}^{j-1} \sum_{k’=1}^{k-1} g(i,j’,k’)) \
$$
因此，$dp$ 的转移，只需要对 $g$ 数组做一次二维前缀和即可。
UpSolved by XLor
求母串的本质不同子串个数，且子串 $T$ 满足，对于任意非空串 $P$，若 $TP=PT$，那么 $TP$ 不是 $S$ 的子串。
观察一下，对于子串 $T$，当存在 $TT$，$T$ 不合法，存在 $TTT$，$TT$ 不合法，也就是对于这样的一组串只会算一次。
上述等价于，减去多算的 $TT,TTT,TTTT,\dots$，暴力枚举每个 Runs 内部的每个右端点的周期串，哈希去重。
UpSolved by XLor
给定树上 $q$ 条路径，求选出 $k$ 条有公共点的路径的方案数。
对于一种选择方案，公共点数减去公共边数等于 $1$。
对于所有点和边，分别求其出现在多少条路径上，相减即为答案。
UpSolved by XLor.
给定一个序列，将序列划分为长度为 $1$ 或 $2$ 的子串，最小化每个子串和的极差。
显然，枚举最小值，dp 出可能的最小的最大值。
令 $\infty$ 表示情况不存在，$-\infty$ 表示任意。
记 $dp(i,0/1)$ 表示 $i$ 位置是否被用过的最小最大值，当前下界为 $D$。
$$
dp(i,0)=dp(i-1,1) \
dp(i,1)=\min(\max(a_i+a_{i-1}, dp(i-1,0)), \max(a_i, dp(i-1,1)))
$$
上式中的 $a_i,a_i+a_{i-1}$ 均会在 $< D$ 时，被换成 $\infty$。最终最小的最大值为 $dp(n,1)$。
上面的 $dp$ 状态改成可以线段树动态维护的，允许区间合并的状态。
令 $dp(l,r,0/1,0/1)$ 表示：
00：$[l,r]$ 都被用上；
01：$l$ 和 $l-1$ 配对；
10：$r$ 没有被用上；
11：$l$ 和 $l-1$ 配对，且 $r$ 没有被用上。
合并时，只需要枚举中间两个位置的情况即可。
定义一个串的 LCP 集合，由每对后缀的 LCP 值组成。
给定一个母串，求它的每个前缀的这个集合的 mex。
考虑一个 endpos 等价类，如果它的出现位置不止一个，考虑某两个出现位置，它们的 LCP 为 $1$（必定存在，因为不存在的话与等价类定义不符），同时往左走一步，LCP 变成 $2$，一直到最大长度，都会出现。
因此答案必定是这样的结点的最大长度 $+1$。考虑这样的结点一定不是叶子结点，一定是一个内部结点，且根据后缀树的结构，内部不存在二度结点，因此只需要对所有内部节点取 $\max$ 即可。
注意特判：单字符集串，没有 $0$。
给定至多 $5 \cdot 10^5$ 个长度总和至多 $5 \cdot 10^5$ 的模板串，每个模板串有花费 $cost_i$。
要求将母串分为数段，每段均为模板串，产生的代价是该串的花费。
暴力：建出 AC 自动机，母串在 AC 自动机上跑，每次暴力跳 fail 指针转移 dp。
优化：暴力跳 fail 可能会退化为 $O(n^2)$，注意到几个事实：串长的种类小于 $\sqrt{5 \cdot 10^5}$，而每次跳 fail 串长至少减一，因此扣出有效的转移即可。
定义 $f(S,k)$ 表示将字符串 $S$ 划分为至多 $k$ 段，对于所有划分方案，要求最小化这种划分的字典序最大串。
每次询问一个后缀 $S[l \dots |S|]$，划分为至多 $k$ 段的答案，若有多种答案，输出左端点最小的，且它必须在某一种划分中。
大胆猜测：一定切在后缀的 Lyndon 分解上。
求出每个后缀的 Lyndon 分解，记这个 Lyndon 分解长度为 $p$，和这个 $$ 在后面一共重复了 $cnt$ 次，开始讨论：
后缀有一个整周期为 Lyndon 分解的长度，即类似 bbbbbb，我们肯定是尽量平均的划分，并且为了左端点最小，也就是取后缀的某几个周期的前缀。
$cnt$ 次 $p$ 后还有 Lyndon 分解，即类似 bbbba，如果 $cnt \bmod k = 0$，我们将 $cnt$ 次 $p$ 平均分解，答案为划分后最后一个段。
同情况 $2$，$cnt \bmod k \neq 0$，当成 $cnt + 1$ 段平均分解，答案为该后缀的前缀。
关于后两种情况的区别，如果整除的话，只将重复的 $cnt$ 段平均分解，那么答案就是最后一段，若你移动之前的某个分解位置，产生的字符串会大于这个最后一段（根据 Lyndon 分解）。其他情况就正常对所有段均分，取前缀即可。
强制在线，维护一个串和一个数组，每次向后加一个字母和一个值，定义一个子串的权值为数组对应区间的最小值，求出所有和串的子串，满足等于相应长度的前缀条件，价值之和。
显然，只需要算出每次 push back 产生的贡献即可。
首先，可以动态维护一下每个前缀的 border 集合，遍历一遍得到答案，但是 border 集合的总大小可能是 $O(n^2)$ 的。因此，我们可以考虑维护 border 集合的变化，显然这部分是均摊 $O(n)$ 的（参考 KMP 算法证明）。
考虑 KMP 的过程，从上一点的 fail，暴力往上跳找到第一个点，其对应前缀的下一个字母等于当前字母，显然上跳的中间过程，这些前一次的 border 无法扩展，需要从 border 集合中被删除。
但是，这部分是不够的。还需要考虑，当前的最长 border 之前的转移情况，实际上等同于这个 border 作为前缀时的转移情况，将其丢进被删除集合即可。
官方题解这里给出了另外一个做法，多维护一个上跳指针，表示往上第一个后继字母与当前不同的点，每次暴力往上跳即可（次数等价于变化大小）。
最后，考虑如何维护出答案的增量。加入新的 border，删除 border，border 集合保留未删除的部分，相当于每个权值对于新加入元素对于 $w$ 取 $\min$。使用 std::map 维护每种取值的个数，取 $\min$ 就暴力枚举比 $w$ 大的元素。这样复杂度是均摊 $O(n \log n)$ 的，因为如果我们对同一个 std::map 取 $\min$，其大小（种类数）不会增加，而操作代价实质是大小的变化量。
读错题了。
定义一个长度为 $n$ 的排列合法，当且仅当，满足：排列可以划分成一系列连续的子区间，每个子区间是一个周期等于子区间长度的置换群，且子区间的第一个位置是该子区间的最大值。求长度为 $n$ 的字典序第 $k$ 大的合法排列。
首先，dp 出每个点开头有多个合法排列，即枚举这个点开始的子区间长度，长度为 $n$ 的合法置换群有 $(n-2)!$ 种。
然后，开始逐位确定，枚举当前位置应该填多少，等价于子区间的结束位置，直到方案数大于 $k$，说明子区间在这里结束。
这里需要生成字典序第 $k$ 的一个置换群，这里的 $k$ 等于全局的 $k$ 除掉后面的方案数（每种子区间排列对应后面的排列），全局的 $k$ 取模。
最后，问题就是解决生成这样的置换群，还是考虑逐位确定，使用并查集检查防止提前出现环，方案数使用 $(n-2)!$ 进行更新。
注意一些细节：
使用 C++ 防止爆 $long long$，自定义一个带上限的加法和乘法；
注意 break；
字典序编号为 $0$ 到总方案数减一。
wqs 二分。
| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 36 | 8 | O | . | O | O | O | O | . | . | . | . | O | O | O |