14. P10253 说唱
这题怎么只有蓝的（
我们考虑将答案写成位数的形式 \((Ans=x_1x_2...x_n)\)
那么我们考虑将\(y=\sum_i x_i\frac{10^{n-i+1}-1}{9}\)
\(9y=\sum_i x_i (10^{n-i+1}-1)\)
\(9y+\sum x_i=10 \sum_i x_i 10^{n-i}\)
因为 \(\sum x_i \leq 5 \times 10^5 \times 9\)，所以直接枚举 \(\sum x_i\)，并且判断最后一位是否为 \(0\)，并且位数和等于枚举的值即可。
时间复杂度 \(\Theta(Tn \times 9)\)。
15. P10254 口吃
这题怎么只有紫的（
考虑计算长度为 \(i\) ，逆序对个数为 \(j\) 的方案数是简单的。
设 \(f[i][j]\) 表示长度为 \(i\) 逆序对数量为 \(j\) 的方案数。
然后转移的时候是一个简单的前缀和优化，时间复杂度容易做到 \(\Theta(n^3)\)。
接下来考虑计算带权值的情况：
我们考虑直接计算权值非常的困难，改变一下权值的形式。
考虑一个冒泡排序的过程：
\(1\ 3\ 2\ 4 \rightarrow 1\ 2\ 3\ 4\) 的过程，权值进行了 \(-3+2\) 的操作。
进一步的，我们观察到，权值可以被表示为 \(\sum_i i^2+\sum_{i < j}[a_i > a_j](a_i - a_j)\)。
那么这个式子之和 \(a_i-a_j\) 有关，就可以用类似上面求方案数的方式做，中间要进行一个等差数列的加法，这个也是容易的。
时间复杂度 \(\Theta(n^3)\)。
16. P10255 一首诗
首先差分，然后将所有相同的地方断开，序列将会形成若干个连续段。其中每一个连续段的贡献都是一个对于前缀的等差数列。
然后考虑本质不同的序列长度个数为 \(\sqrt n\) 的，于是考虑分治。
如果长度 \(\sqrt B\)，那么就暴力求等差数列之后求异或和，这里的时间复杂度 \(\Theta(B)\)。
否则考虑将等差数列分段，使得每一段都是一个等差数列。
接下来一个需要处理的问题就是一个等差数列的异或和。
考虑枚举每一个二进制位，然后计算 \(\sum_{i=0}^n \lfloor \frac{a_i+b}{2^k} \rfloor\) ，类欧解决，时间复杂度 \(\Theta(\frac{n}{B} \log^2 n)\)。
然后平衡一下时间复杂度，可以做到 \(\Theta(n \sqrt n \log n)\) ，可以通过这道题目。
事实上对于 \(>\sqrt n\) 的部分，我们考虑公差 \(d \leq \sqrt n\)，所以我们可以预处理，做到 \(\Theta(n \sqrt n)\)。
17. UOJ#177. 新年的腮雷
很厉害的题。
如果直接判断最优的加数方案是困难的，于是我们考虑把这个过程倒过来，考虑判断一个数拆分之后能不能得到剩下的数。
首先考虑二分答案，然后判断一个答案是否合法。
默认 \(a,b\) 全部从小到大排序。
接下来考虑判断 \(S\) 是否可以拆分为 \(T(|S| \leq |T|)\) 。
-
\(max(S) < max(T)\) ，那么这样不合法。
-
\(max(T) \leq max(S) < max(T)+b_1\)，这样的话 \(max(T)\) 一定不是从一个数拆分得到，所以找到比 \(max(T)\) 大的最小的数，删掉即可。
-
\(max(T)+b_1 \leq max(S)\) ，这个时候将 \(max(S)\) 拆分一定不劣。
重复上面过程，即可判断是否合法。
时间复杂度 \(\Theta(n \log n \log v)\)。
18. UOJ#681. 【UR #22】月球列车
首先由一个容易想到的 \(n \log^2 n\) 的做法：对于每一位，二分判断这一位的进位情况，然后容易计算出每一位 \(1\) 的个数，但是这个做法跑不过去。
考虑优化，上面的排序事实上可以变成归并排序，也就是说，所有排序的数就是在这个数的最高二进制位加上 \(0/1\)。
排序的时间复杂度优化成 \(n \log n\)，我们考虑查询。
在查询的时候，我们只关注有多少个数比 \(x\) 小，而下一次也是在 \(x\) 这个数的二进制位前面加 \(0/1\)。
于是我们只需要知道比 \(x\) 大的最小的二进制数即可。
所以设 \(w[i][j][0/1]\) 表示以前第 \(i\) 位，考虑前 \(j\) 个二进制位，下一位填 \(0/1\) 会比多少个数大。
转移是容易的。
而询问可以根据上面的状态归纳，于是也可以做到时间复杂度 \(\Theta(n \log n)\)。
19. 云斗#YDRS004D. 只是呼吸着没有颜色的日子
人类智慧构造题。
首先考虑 \(n\) 为奇数：将所有点围成一个圆，然后考虑枚举每一个点，将图上的所有以这个点为顶点的等腰三角形连边。
考虑每一条边被算的次数，首先在两个点分别作为顶点的时候被算，还有在取到一边中点的时候会被算一次。所以每一条边被算了三次，上面的构造方式是对的。
需要的次数为 \(\frac{n(n-1)}{2}\)。
然后考虑 \(n\) 为偶数的情况：
我们考虑对于前 \(n-1\) 个点，考虑对于这 \(n-1\) 个点的排列，我们连 \(n-1\) 条边：\((n,p_i,p_{(i+1) \bmod (n-1)})\) 。
然后我们首先对于 \(p_i=i\) 的情况进行操作两次。然后对于 \(P=\{ {1,3,5,7...(n-1),2,4,6...(n-2)} \}\) 操作一次。
考虑现在这张图，\((i,n)\) 被统计了 \(6\) 次，此外，对于 \((i,(i+1) \bmod (n-1),(i+2) \bmod n-1)\)，这些三角形都计算了一次。
然后我们考虑在此基础上，将前 \(n-1\) 个点按照上面的奇数情况操作两次，并且在第二次的时候对于上面被操作过的边上的等腰三角形不进行操作，这样就可以得到一个每一条边被统计 \(6\) 次的方案。
需要的次数为 \(n(n-1)\)。
20. [AGC056B] Range Argmax
好题！！
我们考虑一个序列 \(x\) 还原序列 \(p\) 的方式。
在当前局面当中，找到所有跨过 \(k\) 的区间全部满足 \(x_i=k\) 的位置，并且将所有满足这样条件的位置中最靠左的位置填为最大值。
根据这个思路，考虑求出不同的 \(x\) 的方案。
考虑对于一个区间 \([l,r]\) ，我们枚举区间当中出现最大值的位置，记为 \(x\) ，然后需要满足 \([l,x)\) 当中不存在满足上面条件的点，不然点 \(x\) 就不会成为最大值。
于是考虑设计状态，设 \(f[l][r][k]\) 表示区间 \([l,r]\)，最大值位置在 \([k,r]\) 的方案数。
转移预处理 \(p[l][r][k]\) 表示被区间 \([l,r]\) 完全包含的区间，跨过 \(k\) 的左端点的最小值，预处理这个是简单的。
则有 \(f[l][r][k]=f[l][k-1][pos[l][r][k]] \times f[k+1][r][k+1]\)，理解这个转移是容易的。
并且 \(f[l][r][k] \leftarrow f[l][r][k+1]\)
时间复杂度 \(\Theta(n^3)\)。
21. [ARC156E] Non-Adjacent Matching
在省选之后见到的又一道不等式分类题。
考虑一个序列 \(x\) 的合法条件：
-
\(S=\sum x\) 是偶数。
-
\(x_i + x_{i+1} \leq \frac{S}{2},x_{n+1}=x_1\) ，我们称不满足这个条件的 \(i\) 为不合法位置。
证明考虑通过归纳法证明。
于是我们尝试对于这样的序列计数：
考虑对于第二个条件容斥：总方案减去钦定一个位置不合法加上钦定两个位置不合法，这里需要注意的是，不存在有 \(3\) 个位置及以上不合法的情况，并且两个位置不合法的情况这两个位置一定相邻。
总方案数：
考虑我们写出每个位置的生成函数：\(f(x)=\frac{1-x^{m+1}}{1-x}\)，那么 \(f(x)^n\) 的偶数次项系数和就是总方案数。
记 \(F(x)=(1-x^{m+1})^n,G(x)=\frac{1}{1-x}^n,f=FG\)，于是我们考虑写出 \(F,G\) 的形式。
\(F(x)=\sum_{i=0}^n (-1)^i\dbinom{n}{i} x^{i(m+1)}\)
\(G(x)=\sum_i \dbinom{x+n-1}{n-1} x^i\)
上面是一个二项式反演的形式，下面是一个插板法，很好理解。
于是容易通过前缀和做到 \(\Theta(k)\)。
钦定一个位置不合法：
假设位置 \(1\) 不合法，因为对于每个位置等价，所以最后将方案数 \(\times n\) 即可。
然后考虑 \(\frac{S}{2} < x_1+x_2 \leq m+m=2m \Rightarrow S \leq 4m\)。
于是考虑枚举 \(S,x1+x2\) ，转移是容易的。
钦定两个位置不合法：
同理，钦定位置 \(1,2\) 不合法。
考虑枚举 \(x2,\sum_{i=3}^n x_i=T\)
设 \(g(s1,s2)=\sum_{0 \leq x_1 \leq c,0 \leq x_3 \leq m,2|x1+x3+s1} [x_1+x_3+s1 \leq k][|x_1-x_3| \leq s2]\)
其中第一个表示的是 \(\sum x \leq k\)，第二个表示 \(x_1+x_2 >\frac{x_1+x_3+s1}{2},x_3+x_2 >\frac{x_1+x_3+s1}{2}\)。
于是 \(\sum_{0 \leq x_2 \leq m,T} g(x_2+T,x_2-T)\)。
按照上面来处理就可以了，时间复杂度 \(\Theta(k+m^2)\)
22. CF1290E. Cartesian Tree
首先考虑对于每一个位置，找到这个位置左边右边第一个比这个位置大的数，记为 \(l_i,r_i\)
\(ans=\sum_i r_i-l_i+1\)
于是我们考虑用数据结构来维护这个东西，考虑需要的操作：
-
区间加
-
区间取 \(min\)
-
区间求和
容易使用 \(seg-beats\) 维护，时间复杂度 \(\Theta(n \log n)\)。
23. P4211 [LNOI2014] LCA
套路题。
考虑对于求区间 \([l,r]\) 的答案，进行一步差分，求 \([1,r]-[1,l-1]\)。
然后考虑求 \(dep[lca]\) 的贡献，一个思路是将每一个点的所有祖先全部 \(+1\) ，然后对于查询的点，求出这个点的所有的祖先的和，是一个可以想到的思路。
于是直接扫描线，对于每个点求值，树链剖分 + 线段树，时间复杂度 \(\Theta(n \log^2 n)\)。
24. P3345 [ZJOI2015] 幻想乡战略游戏
上面题目的加强版，考虑将 \(dis(u,v)=dis(u,rt)+dis(v,rt)-2dis(lca,rt)\) ，然后将贡献拆开，按照上面的思路，时间复杂度 \(\Theta(n \log^2 n)\) 。
25. P8203 [传智杯 #4 决赛] DDOSvoid 的馈赠
感谢来自学长 sampson_yw 的高级做法。
将询问离线下来，然后将 \(S\) 分块，每次计算 \(s_i(i \in [l,r])\) 的方案。
具体的，考虑将 \(s_l-s_r\) 建立 \(AC\) 自动机，然后将 \(t\) 暴力跑匹配，每次计算的时候将两个 bitset 进行与操作得到答案。
时间复杂度 \(\Theta(\frac{n^2}{\omega})\) ，跑得非常的快。
26. P9481 [NOI2023] 贸易
本来准备找个时间 vp 的，但是一直拖到了现在，还是没有 vp 。
因为原图上面只有树边和返祖边，所以每次考虑一个子树里面的贡献就可以了。
具体的，每次在 \(lca\) 的地方统计贡献。
考虑这种特殊的情况，需要特殊处理包括 \(lca\) 的祖先的情况。
时间复杂度 \(\Theta(n^22^n)\) ，如果有没有理解的地方可以参考代码的实现。
27. P9726 [EC Final 2022] Magic
一道看起来并不是很难的题。
首先考虑，两个区间如果互相包含，那么先填外面后填里面一定不劣；如果两个区间互不相交，那么两个区间的顺序没有影响。
所以我们只需要考虑两个区间相交的情况，考虑 \([l_1,r_1],[l_2,r_2](l_1 \leq l_2 \leq r_1 \leq r_2)\)，那么 \(r_1,l_2\) 不难共存。
所以建边之后就是一个最小点覆盖，转化之后得到最大匹配，用 bitset 优化，时间复杂度 \(\Theta(\frac{n^3}{\omega})\)。
28. LOJ#6042. 「雅礼集训 2017 Day7」跳蚤王国的宰相
一道看起来并不是很难的题。
首先考虑对于每一个点统计答案，那么就是要断掉一些边然后接到某一个点的儿子，然后满足所有子树的大小 \(\leq \frac{n}{2}\) 。
首先将原来的子树变成重心为根，设重心为 \(rt\) 。
然后考虑 \(rt\) 的答案显然为 \(0\) ，考虑 \(x\) 的答案。
此时需要断掉一些边，使得以 \(rt\) 为根的子树大小 \(\leq \frac{n}{2}\)。
考虑二分，这个是容易的。
最后可能还需要段一条边，判断一下 \(fa_x\) 子树大小就可以了。
时间复杂度 \(\Theta(n \log n)\) ，可以做到线性但是感觉 \(\log\) 好写并且能过，就没有写线性。
标签：Set,frac,复杂度,leq,sum,Theta,Problem,考虑 From： https://www.cnblogs.com/AntelopeWang/p/18081217