ARC187
A
略
B
发现，对于一对 \((i,j)\) 如果满足 \(a_i\le a_j\)，那么 \(i\sim j\) 每个点都在一个连通块里。因为对于 \(i<k<j\)，要么 \(a_i\le a_k\) 要么 \(a_k\le a_j\)。
所以有 \((i,i+1)\) 不连边的条件：
令 \(A\) 里满足该条件的 \(i\) 共有 \(x\) 个，那么 \(f(A)=x+1\)。
于是对于每个 \(i\) 去考虑多少种方案中 \((i,i+1)\) 不连边。令 \(p_i\) 表示 \(1\sim i\) 的最小值，\(s_i\) 表示 \(i\sim n\) 的最大值（\(-1\) 分别视为 \(m\) 和 \(1\)）。
考虑枚举 \(1\sim i\) 的最小值 \(x\)，则 \(i+1\sim n\) 的最大值必须 \(<x\)，所以 \(s_{i+1}<x\le p_i\)。
考虑前半部分，如果 \(x\ne p_i\)，那么必有一个 \(-1=x\)。考虑看哪些 \(-1=x\)，则剩下的只要 \(>x\) 即可。令 \(q\) 为 \(1\sim i\) 中 \(-1\) 的个数，所以方案为：
否则如果 \(x=p_i\)，那么所有 \(-1\) 只要 \(\ge x\) 即可，即为 \((m-x+1)^q\)。
考虑后半部分，由于只要 \(<x\)，所以在 \(1\sim x-1\) 中任选，即为 \((x-1)^{p-q}\)，\(p\) 为 \(-1\) 的总数。两部分相乘即为总方案数。
ARC201
A
令 \(cnt_a\) 为执行 \(a+b\) 的操作数，\(cnt_b\) 为执行 \(b+c\) 的操作数，则要最大化 \(\min(cnt_a,cnt_b)\)。
发现减少一个 \(cnt_a\) 最多只会增加一个 \(cnt_b\)，所以可以先最大化 \(cnt_a\) 后调整。
对于 \(i\)，如果 \(a_i+c_i\le b_i\)，那么 \(cnt_a\) 和 \(cnt_b\) 分别加上 \(a_i\) 和 \(c_i\) 即可；否则优先处理 \(cnt_a\)，令 \(x=\min(a_i,b_i)\)，\(y=\min(b_i-x,c_i)\)，则分别加上 \(x,y\) 即可，同时减少 \(cnt_a\) 以增加 \(cnt_b\) 的次数最多为 \(\min(x,c-y)\)。
最后处理，如果 \(cnt_a\le cnt_b\)，不需要减少了，答案就是 \(cnt_a\)。否则，令 \(s\) 为最多减少的次数，如果 \(cnt_a-s\ge cnt_b+s\)，则答案为 \(cnt_b+s\)，否则就是 \(\frac{cnt_a+cnt_b}{2}\)。
B
不断执行如下操作（每个体积都可以添加无限个价值为 \(0\) 的物品）：
- 若 \(w\) 为偶数，那么可以将体积为 \(1\) 的物品合并为体积为 \(2\) 的物品，并将 \(w\) 和所有物品体积除 \(2\) 显然不影响答案。合并的时候显然将价值从大到小相邻合并最优。
- 若 \(w\) 为奇数，那么将体积为 \(1\) 的物品中最大价值取出，再变成第一种情况即可。
C
首先容易想到建出 Trie，考虑统计答案。
令每个字符串的结尾点为关键点，将 Trie 上只有一个儿子的点补上一个叶子，于是问题转换成选出若干个关键点，使得所有根到叶子的路径都经过选出的点的方案数。
这东西可以树形 dp，在线每次修改只会修改一条链。
D
如果将 \(A\) 和 \(B\) 递增排序，那么最优的方案肯定是选取一个点 \(s\) 分成 \([1,s-1]\) 和 \([s,r]\) 两段区间，然后每段区间 \(a_i\) 和 \(b_i\) 交替相加。
要求 \([s,r]\) 区间 \(a_i\) 和 \(b_i\) 交替相加结果都 \(\ge m\) 且 \(s\) 最小，因为 \(s\) 越大 \(\max(a+b)\) 越大。然后直接二分即可。
CF2150
D
首先思考哪种状态是合法的，设 \(p_i\) 表示 \(i\) 位置上的人数，容易发现
- \(p_i\) 的值是一段连续区间，假设是 \([L,R]\)。
- \(\forall i\in (L,R)\)，\(p_i\) 是奇数。
是合法的充要条件，模拟过程可得到。
于是考虑统计权值和，假设 \(L=1\)，则枚举 \(R\)，不妨换一种形式表达 \(p\)：
- \(p_1=2q_1+x(1\le x\le 2)\)，
- \(p_i=2q_i+1(1<i<R)\)，
- \(p_R=2q_R+y(1\le y\le 2)\)。
考察 \(q_i\) 的性质，容易发现 \(\sum q_i=\frac{n-x-y-(R-2)}{2}\)，然后求 \(\sum 2q_i a_i\)。然后发现 \(q_i\) 是轮换对称的，所以 \(q_i\) 的期望值就是 \(\frac{n-x-y-(R-2)}{2R}\)，于是就变成 \(w \frac{n-x-y-(R-2)}{R}\sum a_i\)，其中 \(w\) 为 \(q_i\) 的方案数，用隔板法可求。
F
第一步选 \(k=3\)，因为 wxr 说加的边最多。
然后考虑第二步直接选 \(\lceil\frac{d}{2}\rceil+1\)，其中 \(d\) 为原图任意一棵生成树的直径，接下来说明对于每个点对一定存在长度为 \(p=\lceil\frac{d}{2}\rceil\) 的路径。
- \(dis_{u,v}\ge p\)，把树上 \(u,v\) 路径拿下来，先若干步 \(2\) （由于第一步是可行的）后再若干步 \(1\) 即可。
- \(dis_{u,v}<p\)，考虑找到点 \(x\) 使得 \(|u\leadsto x\bigcup u\leadsto v|=p+1\)，这样的 \(x\) 是一定存在的，因为考虑距 \(u\) 最远的点，其距离一定是 \(\ge p\) 的（直径某一端点 \(t\)）。然后考虑构造，分类讨论即可。
CF2152
F
首先把条件改一下，因为 \(y\) 有序，假设选了 \(p_1,p_2,\cdots,p_k\)，则等价于要求 \(\forall i\ge 3,y[p_{i}]-y[p_{i-2}]>z\)。
所以考虑对于每个 \(i\)，找到前面第一个 \(j\) 满足 \(y_i-y_j>z\)，记为 \(t_i\)，则 \(p_{i-2}\le t[p_i]\)。
然后再考虑，区间 \([l,r]\) 选出来的子集一定可以包含 \(\{r-1,r\}\)，否则将后两个替换为 \(r-1\) 和 \(r\) 一定不劣，于是考虑从 \(r-1\) 和 \(r\) 开始跳 \(t\)，这个可以倍增预处理，如果跳到某个位置相同后，则要将其中一个数 \(-1\)，然后变成子问题。
G
首先将题目要求转换为，有多少个 \(u\) 满足 \(a_u=1\) 且子树内没有其他 \(1\)。然后有子树，有翻转，考虑括号序。将 \(a_u=1\) 进来和出去分别看为 \(1\) 和 \(3\)，\(a_u=0\) 看为 \(0\) 和 \(2\)，则转为求最长的 \(131313\cdots\)，用线段树维护即可。对于子树翻转，交换 \(1,0\) 和 \(2,3\) 即可。
CF2159
E
先考虑求 \([x^k]F(n)\)。直接做显然不好做，注意到 \(n\le 3\times 10^5\)，考虑分块。
假设块长为 \(B\)，先递推算出 \(F(0\sim B-1)\)，这一部分时间复杂度 \(O(B^2)\)。然后要求出任意一个 \(F(n)\)，还要算出 \(F(0,B,2B,\cdots,\lfloor \frac{N}{B}\rfloor B)\)，假设当前要求 \(F(m)\)。
由于 \(F(m)=f^m\)，其中 \(f=ax^2+bx+c\)，考虑一种常见思路，即先求导。
考察 \([x^{k-1}]\)（以下记 \(F[k]\) 表示 \([x^k]F(m)\)）：
所以先求出 \(F[0]\) 和 \(F[1]\) 便可递推算了，这一部分时间复杂度 \(O(\frac{N^2}{B})\)。
然后每次询问 \(n,k\)，只需要算 \(F(n\bmod B)\cdot F(\lfloor \frac{n}{B}\rfloor B)\) 的第 \(k\) 项，假设两个多项式长度分别为 \(p,q\)，则这一部分时间复杂度是 \(O(\min(p,q))=O(B)\) 的。所以取 \(B=\sqrt N\) 最优。
现在是求前 \(k\) 项的和，只需要将 \(F(0,B,2B,\cdots)\) 做一遍前缀和即可。