1500 分段
455A
DP。
首先将数排序并记录每个数有多少个。
首先所有数肯定是都要取完的。
每个数可能被它前一个数取，可能是自己取，也可能是被它后一个数取。
所以可以考虑定义状态 $f(i,0/1/2)$ 表示第 $i$ 个数被 前/自己/后 取 时的最大得分。
考虑如何转移。
被前面取时，很简单
被自己取时，那么它前一个数可能被前一个数的后一个数取，也可能被前一个数的前一个数取，所以为
其中 $cnt_i$ 表示数 $i$ 的个数。
被后一个数取时，那么它前一个数可能被自己取，也可能被前一个数的前一个数取，所以为
过程中取最大值即可得答案。
时间复杂度 $O(n)$ 。
事实上可以更精简。
定义 $f(i)$ 表示取到 $i$ 时的最大得分。
有
不取和取。
580C
DFS。
直接 DFS ，过程中记录以目前节点为末尾的连续点权为 $1$ 的长度，过程中去最大值，到叶节点时判断即可。
1600 分段
431C
递归+记忆化。
很容易想到，可以转化成 $n$ 叉树的总方案数减去 $k-1$ 叉树的总方案数。
于是便可以递归 + 记忆化解决本题。
定义 $f(n,k)$ 表示 $k$ 叉树，和为 $n$ 的方案数。
有
1700 分段
466C
前缀和。
感觉不像这个分段的题。
直接做一遍前缀和。
如果整体之和不是三的倍数，那就直接输出 $0$ 。
否则，遍历一遍前缀和，如果到目前位置的前缀和等于整体之和的三分之一，那么就将 $cnt_i$ 标为 $1$ 。
处理完后再对 $cnt$ 求前缀和，然后用一个变量，一位一位地计算后缀和。若当前位置 $i$ 的后缀和恰好等于整体之和的三分之一，那么答案就加上 $sum_{cnt_{i-2}}$ 。
时间复杂度 $O(n)$ 。
474D
DP。
$f(i)$ 表示长度为 $i$ 时的方案数。
每次可以加 $1$ 个 $0$ 或者 $k$ 个 $1$ ，所以状态转移方程为 $f(n)=f(n-1)+f(n-k)$ 。
当 $n<k$ 时， $f(n)=1$ 。
询问 $l,r$ ，求前缀和后求区间和即可。
1800 分段
478C
贪心。
假设 $a,b,c$ 中最大的是 $a$ ， $a+b+c=s$ 。
如果 $a\le \dfrac{2}{3} s$ 的话 ，那么总有一种方法能够尽可能用上全部的气球，答案为 s/3 。
若 $a> \dfrac{2}{3}s$ 的话，说明即使是两个 $a$ 两个 $a$ 地用也用不完 $a$ ，所以答案为 $\min(\dfrac{a}{2},b+c)$ 。
上面的除法均为 / 。
1328D
贪心+构造。
看了题解。
答案不会超过三。
当只有一种类型时答案为 $1$ 。
否则，当长度为偶数时，直接 1 2 1 2 这样填，所以答案为 $2$ ；当长度为奇数时，若存在两个相邻的类型相同，那么令他们颜色相同，这样就又转化成了奇数的情况（相当于长度减了 $1$ ），接着 1 2 1 2 这样填。答案为 $2$ 。
否则，当长度为奇数且不存在相邻的类型相同，前 $n-1$ 个 1 2 1 2 这样填，最后一个填 3 即可，答案为 $3$ 。
1900 分段
577B
首先可以可以考虑直接对每个数模 $m$ ，统计剩余类个数。
子序列，想到了背包。
可以发现是一个恰好装满的多重背包问题。
直接多重背包过不了，可以进行二进制优化，
复杂度 $O(n\log m)$ 。
看了一下题解，发现有结论：如果 $n>m$ ，那么一定有解。
挺妙的，另一种形式的鸽巢原理，有 $n$ 个 $a_i$ ，也就有 $n$ 个 $s_i$ ，所以模 $m$ 后，必然存在 $i,j$ 使得 $s_i=s_j$ ，所以必然存在一个区间之和模 $m$ 等于 $0$ ，所以必然有解。
如果知道这个结论的话，那么需要考虑的就只有 $n\le m$ 的情况，那么直接背包就行，无需优化。
2000 分段
380C
看了题解。
求的是子序列的最长合法，直接求不好求，所以考虑求不合法的，即无法匹配的 ( 与 ) 数量 $lcnt$ 与 $rcnt$ 。
对于两个区间，若合并这两个区间，容易发现新区间的 $lcnt$ 与 $rcnt$ 是易于维护的
这个很好想，合并后左边区间的无法匹配的 ( 可以与右边区间无法匹配的 ) 匹配。
于是可以考虑用线段树来维护。
询问区间时类似，也用上面的求法。
时间复杂度 $O(n\log n)$ 。
1438C
看了题解。
可以考虑从奇偶性的角度来分析。
奇数肯定是不等于偶数的。
所以可以按照棋盘那样，一个奇一个偶。
如果当前位置的数的奇偶性与它应是的奇偶性不符，就加一。
还是挺妙的。
2200 分段
490F
本题数据很小，所以可以直接以每个点为起点 dfs 一遍求 LIS ，时间复杂度 $O(n^2 \log n)$ 。
如果 $n$ 大一些的话，这种做法就不行了。
考虑每个点建一个权值线段树，维护以 $i$ 为结尾的 LIS 和 LDS 长度。
在枚举一个点时，有两种 LIS ：
- 经过该点的 LIS 。
- 不经过该点的 LIS 。
第一种长度就是一个子树的 LIS 加另一个子树的 LDS 再加 1 。
另一种直接在线段树合并的过程中用左边的 LIS 与右边的 LDS 之和来更新 ans 即可。注意还可以反过来。
写起来细节很多，需要仔细想想。
调了好久 qaq 。
86D
容易发现由区间 $(l,r)$ 转移到 $(l+1,r),(l-1,r),(l,r+1),(l,r-1)$ 都是 $O(1)$ 的。
所以考虑莫队。
直接莫队即可。
2300 分段
600E
比较板的线段树合并。
注意开 long long 。
