2019 Dec 9.4
感觉没啥难度，C的思维很好，值得学习。
A
简单区间 dp。\(f_{l,r}\) 表示只在 \([l,r]\) 内部覆盖得到的最大权值，转移首先将两个相邻区间 \([l,k],[k+1,r]\) 拼起来，以及找到覆盖点区间 \([l,k-1],[k+1,r],cov(k,l,r)\)，其中 \(cov\) 可以 \(n^3\) 预处理。
B
考虑对于每种颜色分开处理，一种直接的想法是建立出每种颜色的虚树，修改时若已经被染色就不管，否则相当于把所有子树内已经染色的区域全撤回再加入整个子树染色，由于每个点最多只会染一次和撤回一次，均摊正确。
而对于子树内染色，维护 \(dfn\) 序后变为区间加，区间求和，BIT 维护即可。
思路好想但是似乎有一点点难写。
实际上不用这么麻烦，发现本质还是对 \(dfn\) 序列操作，每次相当于一段区间推平，每种颜色开一个 ODT 维护即可。
复杂度 \(O(n \log n)\)
C
笛卡尔树形态非常难维护，考虑如何处理最后的答案，考虑一个点 \(u\)，它的深度相当于它的祖先个数，于是枚举一个点 \(v\)，计算 \(v\) 是 \(u\) 祖先时有多少方案。
\(v\) 是 \(u\) 祖先的条件是 \(a_v < a_u\)，且满足 \(a_v\) 是 \([\min(u,v),\max(u,v)]\) 这一段中的最小值。
接下来考虑逆序对数量为 \(k\) 的限制，若没有 \(u,v\) 的要求则是经典问题，考虑每次插入 \(i\)，能造成逆序对数量为 \([0,i-1]\)，于是答案就是 \([x^k] \prod_{i=0}^{n-1} \sum_{j=0}^i x^j\)。
有了 \(u,v\) 限制怎么办呢，先插入 \([\min(u,v),\max(u,v)]\) 这一段，再插入前缀，再插入后缀，不难发现除了插入 \(v\) 的时候有问题，剩下的贡献一模一样。而插入 \(v\) 时的贡献由于钦定 \(v\) 是最小值，所以 \(u<v\) 是贡献为 \(x^{v-u}\)，否则为 \(x^0\)。
答案只跟 \(v-u\) 差值有关！于是暴力维护多项式，每次初掉一项，复杂度 \(O(n^3)\)。
2020 Jan 9.5
呜呜被打爆了。
A
方向错了就真的想不出来了。
答案是每个连通块方案数乘积，先把一行内连续段缩点。连通块可以并查集维护，如何合并方案？从小到大开放点，不难发现若两个连通块合并答案为两者乘积，因为相互独立，最后每一行的连通块方案还要 +1，因为可以用当前最高的覆盖。
B
没啥思维难度。
首先 dp 转移显然能写出来，进而发现可以写成矩阵形式。
暴力的想法是猫树维护矩阵乘法，但是做一次矩阵乘法复杂度为 \(O(n^3)\)，还有猫树的 \(\log\)。
转移矩阵形如一个单位矩阵在加上一列，只有 \(O(k)\) 个地方有值，于是矩阵乘法变成 \(O(k^2)\)，但是多个 \(\log\) 还是不能过。
考虑一些其他想法，不用数据结构维护而是直接前缀和维护，\([l,r]\) 的乘积应该是 \(pre_r * inv_{l-1}\)，其中 \(pre_n = \prod_{i=1}^n w_i, inv_{n} = \prod_{i=n}^1 w_i^{-1}\)，注意乘法顺序，因为矩阵没有结合律。
逆矩阵也是只有 \(O(k)\) 个位置，预处理部分为 \(O(k^2)\)。
查询时是向量乘矩阵，\(O(k^2)\)。
总复杂度 \(O(nk^2+qk^2)\)，注意空间。
C
清新小贪心。
首先拍到平面上变成了很多条直线，有交点便可以换乘。
对于 \(a_{q_i} < a_i\)，\(q_i\) 在 \(a_i\) 下部，所以应该换成下标尽可能大的线，这样下降的才能更快。
猜测一手答案肯定在凸包上，证明感性理解。
而对于这种情况，只有满足 \(a_j > a_i\) 的直线才会有用，且凸包内的斜率（即下标）应该单减。
于是按照 \(a\) 排序后一个个插入即可得到凸包。
查询的话是求凸包与斜线交点，二分即可。
对于 \(a_{q_i} > a_i\) 同理。
注意细节。
2020 Feb 9.5
AK了。
A
先二分，注意到对于每个点只能由一条边向上，于是内部需要两两匹配掉，显然往上的边越长越好，且往上的边长度具有单调性，对这个二分，判断剩下的能否两两匹配即可。
B
对于一个曼哈顿三角形，一定存在一个点（叫做它的中点）满足：三角形其中有两个点与它 \(x\) 坐标或 \(y\) 坐标相等，另一个点的范围在一条直线上，且中点到三个点的曼哈顿距离相等。
枚举中点和中点到顶点的距离，预处理一条斜线前缀和即可。
需要注意的是类似于 \((x+d,y),(x,y-d),(x,y+d)\) 这样的三个点会被计算两次，还需要减掉一次。
C
看见 \(K\) 次幂先考虑斯特林转下降幂，变成计算 \(\binom{cnt(S)}{i}\)，其中 \(cnt(S)\) 表示连通块个数，于是按照线段左端点排序，对每段区间分类讨论，而 \(\binom{n}{m} + \binom{n}{m-1} \to \binom{n+1}{m}\)，剩下还需要区间乘和区间求和，线段树维护。
2020 OPEN 9.6
难。
A
由于不能重叠，所以轮廓线呈阶梯状，且每个拐角处必须放，剩下的随便放，对答案贡献是 \(2^{c-拐角数量}\)。
故直接对轮廓线做 dp，\(f_{i,j,0/1}\) 表示当前在 \((i,j)\) 右下角且最后一段是向右/向下，转移是平凡的。
B
优秀的 Min-Max 容斥练习题。
显然答案为环长的 \(\text{lcm}\) 乘积，而对于 \(\text{lcm}\) 不好记数，故考虑 Min-Max 容斥，变为对子集的 \(\gcd\) 计数带上容斥系数。
考虑枚举一个 \(d\) 表示 \(\gcd\)，做一个 dp 求出 \(x\) 个数被许多环长为 \(d\) 的倍数的环组成的方案数，这里要带容斥系数，最后枚举一下 \(x\)，剩下的 \(n-x\) 的数没有限制，也就是 \(n-x\) 随便被环分割的方案数，这个众所周知是 \((n-x)!\)，可以考虑排列是环排列的 \(\exp\)。
但是这样无法保证 \(\gcd\) 正好是 \(d\)，实际上计算的是 \(\gcd\) 为 \(d\) 的倍数的方案数，于是最后再做一遍莫反即可。
复杂度为 \(\sum_{i=1}^n (\frac{n}{i})^2=n^2*\sum_{i=1}^n \frac{1}{i^2}= n^2*\frac{\pi^2}{6}=O(n^2)\)。
C
很难，咕咕咕。
2020 DEC 9.6
还好，难。
以前做过的 dp。首先按照 \(s\)，\(t\) 排序，暴力的考虑是枚举 \(s\) 未选的最小值，然后大于 \(s\) 的 \(t\) 就必须选择了，\(O(n^3)\)。
发现只需要在 dp 时知道前面是否已经选定过最小值就行了，不需要知道具体，\(O(n^2)\)。
感觉思路很自然！
首先考虑操作序列，最大值只有一个，按照最大值分割之后递归到子问题，这启发我们记录最大值是多少即可，记 \(f_{i,j,k}\) 表示从 \(i\) 到 \(j\) 最大值为 \(k\)，转移枚举最大值所在位置 \(t\)，并选择 \(u,v\) 满足 \((u,t),(t,v)\) 即可，两维独立即可优化到 \(n^4\)，而每组询问也是特殊情况，塞到 \(n\) 个点里面一起跑即可。
超级大粪。
首先这个题和 Keep XOR Low 很像，非常像。
给定了强制选 3 个的限制，所以套用一样的方法，设 \(f_u\) 表示在节点 \(u\) 里面选三个的方案数，转移考虑限制数 \(K\) 这一位是 \(0\) 还是 \(1\)，若为 \(1\) 则考虑要分叉，再记录 \(g(u,v)\) 表示在节点 \(u\) 和节点 \(v\) 子树内选 \(1,2/2,1\) 的方案数，同理还要 \(h(u,v)\) 表示在节点 \(u\) 和节点 \(v\) 子树内选 \(1,1\) 的方案数。
\(f(x,y)=f(ls(x),ls(y))+f(rs(x),rs(y)),[k=0]\)
\(f(x,y)=g(ls(x),rs(y))+g(rs(x),ls(y))+C_3(s(x))+C_3(s(y)),[k=1]\)
\(g(x,y)=g(ls(x),ls(y))+g(rs(x),rs(y)),[k=0]\)
\(g(x,y)=g(ls(x),rs(y))+g(rs(x),ls(y))\\+h(ls(x),rs(y))*(s(rs(x))+s(ls(y)))+h(rs(x),ls(y))*(s(ls(x))+s(rs(y)))\\+C_2(s(ls(x)))*s(ls(y))+C_2(s(rs(x)))*s(rs(y))\\+C_2(s(ls(y)))*s(ls(x))+C_2(s(rs(y)))*s(rs(x)),[k=1]\)
\(h(x,y)=h(ls(x),ls(y))+h(rs(x),rs(y)),[k=0]\)
\(h(x,y)=h(ls(x),rs(y))+h(rs(x),ls(y))+s(ls(x))*s(ls(y))+s(rs(x))*s(rs(y))\)
\(s\) 为子树大小。
不难发现对于 \(f,g,h\) 都满足每个点恰好走过一遍，所以复杂度是可以接受的。
现在的问题是如何进行区间插入，考虑 Trie 树本身就是一颗线段树，将区间分成 \(\log V\) 个长度为 \(2^t\) 区间依次插入即可，这个可能会对复杂度分析有一点影响，但是增加量也是在 \(\log V\) 内，可以接受。
2021 JAN 9.9
质量很高，很合胃口。
A
首先要先看懂那个新图是怎么建的，其实就是新图上走一步等于在每个图上各走一步。
由于是无向图，所以可以往前一步往后一步使得步数 \(+2\)，不难想到对于奇偶分开讨论。
具体的，对于第 \(i\) 个图上的 \(j\) 点，它的奇偶最短路分别为 \(d_{i,j,0/1}\)，对于选择方案 \(S\)，答案即为 \(\min (\max d_{s,0}, \max d_{s,1})\)。
有 \(\min\) 和 \(\max\) 很烦，如果要暴力记录必须记录具体值，所以考虑类似期望的贡献计算，\(\sum_i i*f(i)=\sum_j \sum_{i \ge j} f(i)\)，即考虑上面的式子大于 \(k\) 的方案，这样就转化为 \(01\) 序列，此时暴力记录最大值，同时拿线段树维护即可。
一点小细节是对于走不到的距离会导致这一维直接不能选，也就是都不能选奇数或偶数，所以记录状态应该是 \(0/1/2\) 表示无 \(1\)，有 \(1\)，不能选。
B
很套路的题。
首先有朴素的 \(n^2\) dp。
对于一列同时考虑，一列变化时会加上一个二次函数，而还有 \(f_{j}=\min(f_j,f_{j-1}+c_{j-1})\)，本质是将斜率大于 \(c\) 的点全部推到 \(c\) 这条直线上，归纳可得 \(dp\) 下凸。
暴力一点是直接平衡树维护，但是不太好做加二次函数的操作。考虑每次推斜线一定是推一段后缀，于是用一个单调栈维护转折点即可。
C
有点奇怪，略。
2021 FEB 9.9
A
唐氏DS。
首先考虑如何计算整个区间答案，由于小的只能被大的覆盖，考虑按照值域扫描线，具体的，对于当前区间 \(l,r\)，找出所有最小值位置，那对于这些位置可以一步覆盖到，后面的数就不能覆盖这些位置了，即递归到子问题。
考虑多组询问，对于该分治区间，与上面蓝色区间有交，且不位于红色区间内的所有询问答案都会 \(+1\)，离线下来扫描线即可。
B
真的很难。
首先由于是无向图，可以对一条边反复横跳使得最短路 \(+2\)，故只需要考虑奇偶最短路。
由于图联通，若没有奇环，则所有点要么只有奇最短路，要么只有偶最短路，只需要构造最短路树即可。
考虑一般情况，将二元组用 \((x,y),x<y\) 表示。
考虑 \((x,y)\) 的连边：
- \((x-1,y-1)\)
- \((x-1,y+1)\) 和 \((x+1,y-1)\)
解释一下第二个，就是 \(x,y\)分别从不同的点跑过来最短，而由于要满足 \(dis_u+1 \ge dis_v\)，第二维限制最多 \(+1\)。
当 \(x+1=y\) 时 \(x+1 > y-1\)，\((y-1,x+1)=(x,y)\)。
我们要最小化边数量，贪心考虑一定是要第一种最优，而第二种的边发现都满足 \(x+y=d\)，故按照 \(x+y\) 分层贪心。
记 \(c\) 为 \((x-1,y+1)\) 对 \((x,y)\) 有几条链接。对于 \((x,y)\)：
- \(siz(x,y) \ge c\)，往 \((x-1,y+1)\) 连 \(c\) 条，若存在 \((x-1,y-1)\)，则往上连 \(c - siz(x,y)\) 条边，否则全往 \((x+1,y-1)\) 连。
- \(siz(x,y) \le c\)，往 \((x-1,y+1)\) 连 \(siz(x,y)\) 条，往 \((x+1,y-1)\) 连 \(c\) 条。
对于上述情况，若出现不存在 \((x+1,y-1)\)，则说明这个点是全局结尾或满足 \(x+1=y\)，此时若 \(x+1=y\) 则向自己连 \(\frac{c}{2}\) 条边，否则 \(c\) 条。
不难发现上述贪心最优。
C
跟 B 题差不多，大概跟着 B 的连边方式即可。
\(f_{x,y,i}\) 表示有 \(i\) 个往左继续连，\(g_{x,y,i}\) 表示有 \(i\) 个往右连，保证必须连一条，\(h_{x,y,i}\) 表示大小为 \(x\) 的集合与 \(y\) 的集合，恰好 \(i\) 个 \(y\) 内的点有边相连，可以二项式定理预处理出来。
复杂度 \(O(n^3)\)。
2021 OPEN 9.10
easy。
A
清新数据结构。
对于三个特殊点的区间问题，扫描线左端点，数据结构维护左端点答案。
首先对于每个数求出 \(pre_i\) 表示上一个 \(a_i\) 相等的位置，没有设为 \(0\)。
对于确定的右端点，左端点得在 \([pre_r+1,r-2]\) 取。
同时 \(l\) 需要满足区间内没有与他相同的数，即 \(r \to r + 1\) 时 \(pre_r\) 就不能成为左端点，\(r\) 可以成为。
第三个点也要满足数不同，\(r \to r + 1\) 时给左端点在 \([pre_r+1,r-1]\) 中的数答案加 \(1\)。
也就是需要支持激活/关闭一个点，区间加，区间求和，线段树即可做到。
B
谔谔，为什么没有想到。
首先每条路径都要走一步，想到欧拉回路，再看到计数，想到 BEST 定理。
然后就做完了？需要将许多路径连通起来，开一个超级源点向 S 连边，T 向超级源点连边，然后是 BEST 定理板子，最后要除一个阶乘，因为第一步随便选本质相同。
C
雪豹书上的原来是这个题吗。
发现合法连通块一定长的是凸多边形，数据范围很小，考虑直接维护，\(f_{i,l,r,0/1,0/1}\) 表示第 \(i\) 行选在 \([l,r]\)，且左端处于伸/缩，右端处于伸/缩。
转移能二维前缀和优化。
2021 DEC 9.10
基础。
A
首先考虑建图，\([a,b]\) 向 \(p\) 连长度为 \(c\) 边，即可求出到 \(1/n\) 的最短路。
但是题目要求同时能扩展到两个点的花费，如果两个点路径上有重合就寄了。
注意到跑出 \(dis_{1 \to i},dis_{n \to i}\) 后设 \(f_{i} = dis_{1 \to i} + dis_{n \to i}\)，之后的转移是 \(f_i + val(i \to j) \to j\)，发现还是最短路转移，所以跑三遍最短路即可，问题转化为如何跑最短路。
暴力一点直接线段树优化建图，默认 \(n,m\) 同阶，复杂度 \(O(n \log^2 n)\)。
考虑这样一个事实：对于每张票，能从 \([a,b]\) 转移过来且转移来的边权都为 \(0\)，故跑 dijkstra 时第一次松弛即为最终答案，也就是只会被松弛一边。
对于每条线段，我们将它挂到线段树上 \(\log\) 个区间，扩展点 \(u\) 时直接找出所有覆盖它的区间拓展并删掉，复杂度 \(O(n \log n)\)。
B
好题。
第一问即最大化匹配和，容易发现直接设 \(f_{i,j}\) 表示考虑 \(H\) 前 \(i\) 个和 \(G\) 前 \(j\) 个就是对的，因为由于要答案最大所以跑出来的一定是最大匹配，不会出现有点对未匹配的情况。
第二问则需要考虑如何为最大匹配，暴力一点需要多加一维 \(x\) 表示上一个未匹配的牛在哪里，复杂度不可接受。
改一下状态，多加一维 \(0/1\) 表示未匹配的牛在 \(i/j\)，转移枚举接下来的匹配长度，以及是否改变未匹配的牛。注意刚刚的转移是 \(O(1)\)，状态是 \(O(n^3)\)，这里我们让转移是 \(O(n)\)，状态是 \(O(n^2)\)。
发现本质在对一条对角线取 \(\max\)，改成前缀 \(\max\) 即可。
C
考虑拆贡献，一个简单的想法是枚举一对点 \((x,y)\) 并枚举位置 \((i,j)\)，要求 \([i+1,j-1]\) 内每个数都被忽略掉，故还需要枚举前缀 \([1,i-1]\) 中最大的小于 \(k\) 的数，然后拆拆贡献，优化到 \(O(n^2)\)。
2022 JAN 9.11
呜呜为什么就是想不到呢。
A
注意到 \(|a_i - a_j| >k\) 的两个数相对位置不能改变，考虑增量，每次插入一个数维护答案。
在 \(i\) 插入一个数时，设它最后换到 \(j\)，则需要满足 \(p \in [j,i],|a_p - a_i| \le k\)，符合条件的 \(j\) 是一段后缀，由于需要字典序最小，故应该在这段符合条件的后缀中选择最靠前的 \(a_t > a_i\) 插入，平衡树维护即可。
B
操作可以看为只能交换两个绝对值相差 \(1\) 的数，对于不能交换的数从前向后连边，变为了拓扑序计数。
但是一般 DAG 拓扑序计数没法做，发现这个图性质：奇偶性相同的数一定连边，也就是这个图是两条链然后相互连边。
那就直接 \(f_{i,j}\) 表示选完了第一条链前 \(i\) 个和第二条链前 \(j\) 个，转移 \(i+1\) 要满足它的所有入边都在 \(j\) 之前，预处理下即可做到 \(O(n^2)\)。
C
计算几何入门题。
不难证明答案一定取在凸包上，证明考虑若取在凸包内部则可调整到外部。
也就是要对 \(n\) 个凸包求闵可夫斯基和，分治即可。
注意细节，额外注意判断共线等情况。
标签：rs,复杂度,记录,USACO,即可,ls,区间,考虑 From： https://www.cnblogs.com/Anonymely/p/18410970