CF1286D LCC
这个题还是比较简单的，考虑拆贡献，将所有碰撞情况拿出来考虑其出现的概率，显然只有相邻的。
按照时间排序。假设我们钦定了 \((i,i+1)\) 这对碰撞为最先碰撞的，那么需要满足若干条件：
例如若 \(j\) 向右，\(j+1\) 不能向左等，因为限制只存在于相邻两位，我们可以考虑 dp 过去。
然后这就是一个动态 dp 了，不需要让 \(i\) 向左向右都 dp 一遍，其实只需要从 \(1\) 扫到 \(n\) 即可。
矩阵+线段树维护即可。
P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95
cdq 分治。考虑拆贡献到每个点对 \((x,y)\)，那么其能贡献的条件是 \(fir_x<las_y\) 且 \(x>y\)。
对于单点修改每次只会产生 \(O(1)\) 次对 \(fir,las\) 的改变。考虑用 set 维护即可。
考虑将修改拆到 \(las,fir\) 两部分，这两部分互不重复。
如果要 cdq 分治我们需要将其转化为偏序形式，我们将所有修改都记为 \((x,y,t,0/1,-1/1)\)。
表示 \(fir_x/las_x\) 改为 \(y\)，此时在 \(t\) 时刻，是要加上还是减掉。
那么考虑 \((x_0,y_0,t_0,0)\) 与 \((x_1,y_1,t_1,1)\) 之间的贡献条件是 \(x_0<x_1,y_0>y_1\)，\(t_0,t_1\) 谁大就贡献到哪。
然后得到每个时刻的变化量，最后只需要将前缀加起来即可。所以对时间这维做 cdq 即可。
注意修改是不变的情况。合并两个归并的区间可以用 inplace_merge 函数。
P5163 WD与地图
折磨。首先删边转化为加边，相当于将时间轴倒序。
我们如果能知道一条边两端点被并到一个 scc 里的时间，我们就能用线段树合并轻松解决。
观察特殊性质，对于单条边，答案满足可二分性，对于多条边的情况，我们可以尝试整体二分。
对于当前二分的时间区间 \([l,r]\)，对于时间在 \([0,mid]\) 的所有边都加入，然后用 Tarjan 来缩点。
如果某条边已被缩起来，那么其之后也一定被缩，往左区间递归；反之右区间递归。
当然我们每次都取出 \([0,mid]\) 的边是复杂度错误的，考虑利用上一层的缩点信息。
即我们在 \([l,r]\) 已经用了 \([0,mid]\) 的边，直接去右儿子 \([mid+1,r]\) 可以直接用上。
然后考虑用可撤销并查集维护缩点，去左儿子 \([l,mid]\) 的时候撤销当前区间的操作即可。
我们可以只加入 \(r-l+1\) 条边，即将并查集维护的 SCC 连起来。
然后我们把新连边的点拿出来跑 Tarjan，这样复杂度跟区间大小挂上。
但是原来 SCC 之间连的边怎么办？我们可以忽略。如果新边和 SCC 之间边可以构成新的 SCC，
那么边集中的该条边一定会在之前的二分中被划分到答案更早的区间，所以不会出现在当前区间里。
于是每条边最多经过 \(O(\log m)\) 层，并查集算 \(O(\log n)\)，复杂度 \(O(n\log ^2n)\)。线段树合并 \(O(n\log n)\)。
P5069 [Ynoi2015] 纵使日薄西山
观察到，如果操作了 \(a_x\) 那么 \(a_{x-1},a_{x+1}\) 肯定都不会被操作，因为他们之间相互大小不会变。
那么这个 \(a_x\) 一定是一直被操作直到 \(0\) 的，此时 \(a_{x-1},a_{x+1}\) 也肯定为 \(0\)。
其次，我们不必模拟整个过程，我们只需要直到哪些 \(a_x\) 被操作了即可，维护 \(a_x\) 集合。
考虑模型化。我们可以把问题转化为 \(01\) 序列，\(0/1\) 表示没选或者选了。然后观察这个序列的性质。
首先 \(0,n+1\) 两个位置取 \(0\)；\(0\) 的连续段不超过 \(2\)；每个 \(0\) 至少有一个相邻的 \(1\) 比它大。
那么这是一个动态 dp 的形式，我们直接从 \(1\) 扫到 \(n\) 即可。
三个状态：取 \(1\)；取 \(0\) 且满足有相邻 \(1\) 比它大；取 \(0\) 但没有相邻 \(1\) 比它大。矩阵处理。
因为我们整个过程是确定的，所以一定只有一种合法的 \(01\) 序列。至于有多种转移我们可以先存着。
矩乘写 \((\max,+)\) 矩乘，用 \(-inf\) 表示没有转移。
P4117 [Ynoi2018] 五彩斑斓的世界
第二分块。考虑弱化题目，如果是整体操作查询该怎么做。发现每次操作势能都减少。
设最大值为 \(mx\)。若 \(2x> mx\)，那么考虑将 \([x+1,mx]\) 区间整体平移；
若 \(2x\le mx\)，那么考虑将 \([1,x]\) 平移；同时打上全局减的 tag。
那么我们这样操作只需要复杂度 \(O(V)\)，而 \(V\le 10^5\) 刚好契合我们的做法。
考虑平移操作该如何实现，我们可以维护相同值的数位置的集合，用并查集维护。
具体是给每个值一个代表位置，然后并查集维护这些代表位置的关系，以及集合的大小。
那么回到原题我们可以考虑将序列分块，如果是整块的操作那么显然就是整体操作；
如果是散块的操作，我们考虑直接重构整个块。
本题卡空间，而每个块是独立的，所以我们离线每个块都做一遍即可。
CF1129D Isolation
这个题属于典题。\(dp_i=\sum _{calc(j+1,i)\le k}dp_{j}\)，其中 \(calc\) 表示出现次数为 \(1\) 的元素数量。
我们考虑加入 \(i\) 会对所有 \(calc(j+1,i)\) 造成什么影响，设 \(pre_i\) 表示上一次出现的位置。
那么 \(j\in[pre_{pre_i},pre_i)\) 的 \(j\) 会减去 \(1\)；\(j\in [pre_i,i-1]\) 加 \(1\)，转化为区间操作，查询值 \(\le k\) 的权值和。
这个显然非 poly，考虑分块，由于是加减 \(1\) 形式操作，所以我们只需要算原来 \(k-1,k+1\) 的贡献。
我们维护块里每个元素可以考虑维护一个桶表示当前值为 \(x\) 的和 \(s_x\)。
整块修改直接打 \(tag\)；散块简单修改。
P6578 [Ynoi2019] 魔法少女网站
考虑没有修改弱化版。考虑将所有数从小到大加入，设已加入为 \(1\)，那么维护连续的 \(1\) 构成的段即可。
其次将所有询问离线，只需要在对应时间上查询答案即可。线段树维护。
考虑加上修改，那么相当于修改若干的 \(0/1\)。我们容易想到操作分块。
考虑操作分块后块内如何做，还是将所有数从小到大加入，对于每个询问，将其对应的改了即可。
但是我们别用线段树，因为查询是 \(O(n)\)，但修改是 \(O(n\sqrt n)\)，考虑给序列分块。需要支持撤销。
这里省略细节。总复杂度平衡后是 \(O(n\sqrt n)\)。
不需要用到并查集，只需要维护每个值所在位置区间最左和最右。
注意规避 \(1\to 0\) 的改变，这是很难处理的，只能处理 \(0\to 1\) 的操作。