加训大数据结构。
「LG8528」[Ynoi2003] 铃原露露
lxl 怎么一题多投，很坏啊！
考虑哪些 \((a_x,a_y)\) 有约束力，一是 \(a_z>a_x\) 且 \(a_z>a_y\)， 或者 \(a_z<a_x\) 且 \(a_z<a_y\)。这也就相当于将 \(l\in[L_l,R_l],r\in[L_r,R_r]\) 的二元组 \((l,r)\) 均设为非法。
对于一次询问，我们可以将他先差分，这样就可以对 \(r\) 做扫描线，需要查询区间历史 \(0\) 个数，这是经典线段树标记。
最后发现有用的限制其实不多，在值域上相邻的两个点，它们的约束力才比较强，这样就可以在树上启发式合并求出所有有用的限制。
时间复杂度 \(O(nlog^2n)\)。
「LG8527」[Ynoi2003] 樋口円香
对 \(a\) 序列分块，散块直接暴力加。
整块的话，先枚举 \(\frac{n}{B}\) 块，再跑一个卷积贡献答案。
时间复杂度 \(O(n\sqrt{mlogn})\)，感觉有点卡常。
「LG7722」[Ynoi2007] tmpq
\(\text{Poly log}\) 的做法很显然，可惜空间过不去。
那就考虑分块，每次修改块内的信息，再修改 \(O(1)\) 个颜色的整块的答案。
时间复杂度 \(O(n\sqrt n)\)。
「CF1764H」Doremy's Paint 2
这题为什么想了半天没想出来啊啊啊啊啊啊！
倒着扫描 \(t\)，认为 \(t\) 时刻为初始状态，维护每个颜色什么时候全部消失。
则 \((l_t,r_t]\) 的值均变为 \(t\)，\(l_t\) 的值变成 \((l_t,r_t]\) 的 最大值，珂朵莉树维护即可。
时间复杂度 \(O(nlogn)\)。
「LG8987」[北大集训 2021] 简单数据结构
考虑所有被 \(\text{chkmin}\) 影响过的 \(a_i\)，他们是单调的，而其余没被影响过的也很好维护。
现在的问题就是求出每个 \(a_i\) 何时变得单调，可以使用整体二分+凸包解决。
时间复杂度 \(O(nlogn)\)。
「LG8990」[北大集训 2021] 小明的树
这题也没独立想出来，急眼了！！！
考虑题目中的条件本质上是，所有黑点的父亲不为白点，而又由于 \(1\) 号点始终为黑，这又等价于黑点为一个联通块。
考虑到森林的连通块数等于点数减边数，对时间轴建一个线段树就做完了。
时间复杂度 \(O(nlogn)\)。
标签：片段,19,text,复杂度,时间,啊啊啊,2023.4,考虑,nlogn From： https://www.cnblogs.com/Nesraychan/p/17334697.html