260914 - 260926
AT_joisc2017_a 開拓 (Cultivation)
首先本质有用的长和宽分别只有 \(O(n^2)\) 种。我们枚举高度 \(len\)，然后对每个点画出线段 \((x,y)\leftrightarrow(x+len-1,y)\)，然后可以对线段向左右扩展，要求在竖直方向至少有长度为 \(r\) 的区间被整个覆盖。
于是只需要求出每个水平位置中，最靠左、右的线段到边界的距离，以及中间距离的最大值，那么左右扩展的总距离形如 \(\max(a+b,c)\)，可以用三个单调队列求出答案。然后又注意到跨过一个水平位置的线段的竖直坐标形如一个区间，而我们可以提前对所有区间求出答案。复杂度 \(O(n^3)\)。
P12264 『STA - R9』咏叹调调律
可以看成
那么合法的必要条件之一显然有括号序列合法，但是 (( 的两个括号不能分别和 )) 的一半和一个 ) 匹配。然后，我们一定会钦定一个前缀的 A 为 ((，其余后缀的为 )。于是可以设状态 \(f_{i,j,k,0/1}\) 表示有 \(j\) 个 (，\(k\) 个 ((，是否选过 )。转移考虑贪心，但是发现加入 ) 时如果同时存在 (( 和 ( 则无法立即决策，考虑把它存起来，即 ( *( <=> ((（其中 *( 表示只能和 ) 匹配的东西）。
因此我们再记一个 \(0/1/2\) 表示存在 *( 或者 (*(。如果加入 ) 则优先匹配二者。如果加入 )) 则优先匹配 ((，(*( 次之。于是大力转移即可。
CF2262E Paired Bracket Sequences
最后二项式反演，转化成钦定 \(k\) 对括号相同的方案数。于是设 \(f_{n,k}\) 表示长为 \(2n\) 钦定 \(k\) 对括号的方案数。直接背包很难优化，考虑到对于任意一对匹配的括号，其内部都是合法括号序列，外面左右可以拼成合法括号序列，于是有转移如下：
直接做是 \(O(n^4)\) 的，注意到第二维是卷积，因此用插值优化到 \(O(n^3)\) 即可。
260915 D
给定一个序列，称一个区间是合法的当且仅当它存在一个划分点使得前后部分出现的数字集合相等，问合法区间数量。
\(n\le 10^6\)
在最左边的划分点统计贡献，就是要求 \(l>pre[m]\)。对 \(m\) 扫描线，记 \((x_i,y_i)\) 表示一个数于左边最后出现在 \(x_i\)，于右边首次出现在 \(y_i\)。然后维护每个 \(l\) 对应的答案，形如 \(\min_{x_i<l}\{y_i\}-\max_{l\le x_i\le m}\{y_i\}\)。前后缀最值可以通过线段树维护，在本题中由于加删点的性质，暴力更新所有最值就是对的。
此外还需去掉上式小于零的情况，发现一对 \((x_1,y_1),(x_2,y_2)\) 满足 \(x_1<x_2,~y_1<y_2\) 会 ban 掉 \((x_1,x_2]\) 的点，这可以通过对 \(y\) 排序，之后对所有相邻两点满足 \(x_i<x_{i+1}\)，将 \((x_i,x_{i+1}]\) 违法次数加一即可。
P13841 芳权多
关键在于处理 hi...hihis 或者 hi...hihe，注意到每个单元的贡献形如 \(k\max(0,t-a)+b\) 其中 \(k\in\{0,1\}\)。于是直接用线段树维护区间内的所有单元，按照 \(a\) 排序，这样给定一个时间容易通过一次二分求出当前长度。复杂度 \(O(q\log^2n)\)。
CF1305G Kuroni and Antihype
可以加入一个 \(0\) 并钦定其初始就位于组织中。然后注意到邀请关系形如一棵树的结构，节点的系数等于儿子数量，在非根的节点上等于度数减一。于是可以赋边权等于两点权之和，最后减去所有点一次即可。
需要用到一个叫 Boruvka 的最小生成树算法，我们每轮对每个连通块找到连接外部的最小的边，然后对所有连通块同时执行合并，这样最坏只需要 \(\log n\) 轮就可以完成。找最小边可以通过一次高维前缀和，为了去除自己连通块的贡献，只需要记录前两大的不同连通块的答案即可。复杂度 \(O(V\log V\log n)\)。
260917 D
给定一棵以 \(1\) 为根的树。其的一个拓扑序是好的，当且仅当不存在一个长度为 \(k\) 的连续区间 \([l,r]\) 使得对任意 \(i\in(l,r]\) 满足 \(p_{i-1}\) 是 \(p_i\) 的父亲。计数好的拓扑序数量对 \(998244353\) 取模的结果。
\(2\le k\le n\le 4000\)
不难想到容斥，钦定一些链连续，通过手动递推可以得到容斥系数等于 \([len \bmod k=1]-[len\bmod k=0]\)。于是，状态记录当前链长度 \(\bmod ~k\) 或者不延伸，以及子树内链的总数，转移时可以断掉当前链并乘上 \(\frac{1}{cnt}\)。这样复杂度是 \(O(n^2k)\) 的。
考虑到 \(k\) 很大的时候大小超过 \(1\) 的链的数量不太多，令 \(h\) 表示 \(len\bmod k=0\) 的链数量，那么对有效的状态有 \(cnt-h+r\equiv sz\pmod k\)，于是不同的 \(r\) 只有 \(\sqrt n\) 个，通过精细实现可以只转移有用的状态，这样复杂度是 \(O(n^{5/2})\)。
260917 B
对于一个字符串 \(S\) 和常数 \(k\)，初始时 \(U=S\)，你需要进行以下操作恰好 \(k-1\) 次：
- 选择 \(S\) 的一个非空周期（可以是本身），拼接在 \(U\) 后面；
问可以得到多少种本质不同的 \(U\)。给定一个字符串 \(S_0\) 和 \(q\) 次询问，每次给定 \(k\) 并将 \(S_0\) 的一个前缀作为 \(S\) 进行查询。
\(n\le 10^6,~q\le 10^5\)
考虑什么时候会算重，发现最小正周期的若干倍之间会混淆。考察其它情况，若两个周期 \(A,B\) 满足 \(A\) 是 \(B\) 的前缀，那么 \(B-A\) 也是周期。对于不是最小正周期 \(A_0\) 若干倍的周期，其长度 \(>|S|-|A_0|\)（WPL）。若 \(A,B\) 都不是 \(A_0\) 的若干倍，可以得到更小的周期，矛盾；若 \(A=k_1A_0\)，\(B-A\) 必然是 \(k_2A_0\)（WPL），矛盾。
于是我们只关心 \(S\) 的最小正周期 \(A_0\) 和不是 \(A_0\) 若干倍的周期 \(B\) 的数量。设最小正周期及其倍数有 \(a\) 个，其余的有 \(b\) 个。本质不同的 \(U\) 的数量可以通过 (能划分成不超过 \(k\) 个周期) 减去 (塞不下 \(k\) 个周期) 得到。对于前者考虑贪心划分，需要记 \(f_0,f_1\) 表示可以接 \(kA_0,~k<a\) 或者不行，转移是线性的，用矩阵快速幂优化；后者显然是 \(\sum_{i=1}^{k-1}(b+1)^i\)。
CF1458D Flip and Reverse
把 \(0\) 改成 \(-1\)，连边 \(s_{i-1}\to s_i\)，注意到操作不改变图，只是选择路径上的一个环，把它反过来。猜测所有欧拉路径都可以实现，考虑调整，找到第一个不同的位置，必然可以通过一次操作变为相同。
qoj18965 最小异或乘积
P8500 [NOI2022] 冒泡排序
先求出每个位置的下界 \(b_i\)，然后对于一个限制 \((l,r,v)\) 实际要求 \([l,r]\) 中 \(b_i=v\) 的位置中至少填一个 \(v\)。于是按照 \(v\) 分别处理所有限制，每一类从右往左填，不难说明贪心的往左填是最优的。
于是现在有些位置已经钦定，有些位置有一个下界，要最小化逆序对数。考虑对值域上的每个数维护一个 \(c_i\) 表示填入 \(i\) 会和前面的数以及后面钦定的数产生总共多少逆序对。如果填入 \(x\) 那么会使 \(c_{1\sim x-1}\)++，走过一个钦定的数 \(x\) 会使 \(c_{x+1\sim n}\)--，\(c_{1\sim x-1}\)++。于是如果某时刻 \(x>y\) 且 \(c_x<c_y\)，那么之后都有 \(c_x<c_y\)。
于是，每次直接填下界内 \(c_i\) 最小的位置，因为比它更小的位置永远不会更优，而且对 \(1\sim b_i\) 的影响相同所以不管。
AT_agc057_c [AGC057C] Increment or Xor
qoj964 Excluded Min
即找到最大的 \(x\) 满足 \(\sum [a_i<x]\ge x\)。考虑离线，从大到小枚举 \(x\)，维护每个询问的 \(\sum[a_i<x]\)。然后注意到如果一个询问被另一个询问包含，后者的答案一定比前者大，因此只维护当前不被包含的区间，这样删除一个 \(a_i\) 就只需要修改一个区间的询问。如果找到一个询问的答案了，就把它删除，然后插入新的不被包含的区间。这样复杂度 \(O(n\log n)\)。
qoj10100 Exchanging Kubic 3
260922 B
P5359 [SDOI2019] 染色
考虑所有至少有一个位置确定的列，它们将序列划分成若干段，每段的方案数只与两端的 \(O(1)\) 种情况以及相等关系有关，可以 dp 预处理求出。然后大概要用一个数据结构维护所有颜色的方案数，所需要的所有操作只需要全局 tag 就可以。
260924 B
注意到如果一个颜色形成多个连通块，那么只有中间那部分可以作为起点。进一步，考虑所有颜色可行集的交集什么时候不可行，发现如果一个点不可行，那么所有点都不可行。于是只需要对所有颜色都扫一遍，最后再 check 一下就行了。
260924 C
对于固定集合的答案，设置变量 \(x\) 初始为 \(1\)，然后每次找到集合中剩余的 \(\le x\) 的数，令 \(x\) 加上它，最终 \(x\) 的值就是答案。于是暴力维护应该可以做到 \(O(n\log n\log V)\)（扫描右端点，维护所有左端点的扩展）。正解考虑倍增值域分块，那么每个块要么所有数都不被选中，要么都被选中，于是我们只需要对每个右端点 \(r\) 和块 \(k\) 求出答案包含块 \(k\) 时左端点的范围（一个前缀），那么最后的贡献是好算的。
记上述范围为 \(g_{k,r}\)，考虑 \(g_{k-1}\to g_{k}\) 的递推，考虑双指针，只需要维护区间内 \([2^k,2^{k+1})\) 的最小值以及 \([0,2^k)\) 的和，前者用单调队列。这样复杂度 \(O(n\log V)\)。