lxl:长度 >= k 大家还不熟悉吗，让我们打开洛谷，NOIP2024,NOIP2025
来看这个粉兔题。
什么！
\(r'\) 更简单，咦，不是，让我看下题。
这翻译神金吧，夹带私货。
你看 NOIPT4 nqlog 都过了，所以有信仰就行。
\(25*10^4\) 是什么小众变态写法？
12.22 log 数据结构
区间的区间并：每次右移右端点要把 \(lst[l\dots r]\) 改成 r+1。
这东西可以颜色段均摊，查询部分可以树状数组。
A.TEST_73
每次只保留编号在区间 [l,r] 内的边和点，求连通块个数。
最后留下来的一定是树上的连通子图，相当于森林，森林连通块数是点-边。
点：全部保留，r-l+1
边：a-c->b \(l\le a,b,c\le r\)，三维数点。
因为 \(l,r\) 不变，所以取最小和最大值，就是二位数点 \(O(n\log n)\)
B.Closest Equals
原。
C.
给定 n 个相互不包含的区间 \([l',r']\)，每个区间有权值，给定 \(l,r,k\)，求在 \([l,r]\) 范围内长度 \(\ge k\) 的区间最大值。
考虑两两不包含的这个性质，进行编号后可以发现肯定是按顺序的，所以询问也是一段区间。
然后就是 k和编号两维限制，扫描线。
但是 lxl 看错题了，没看到不互相包含，求和，于是：
画在图上，没有长度限制相当于紧贴 y=x 的一个三角形内的信息，加上 k 的限制可以通过右移这条线完成。
然后差分一下，假设所求点为 \((a,b)\)，若 \((x,y)\) 在三角形内 \(y\le a,x+y\le a+b\)
D.
平面上有n个矩形，给你一个常数d，你需要找到一个点(x,y)，满足对任意整数k1,k2，(x+k1d,y+k2d)都不在任何矩形中。
可以分成若干 d*d 的矩形，有一个矩形包含了整个网格，直接无解。
然后可以把这些矩形直接平移到第一个格子，对于列或行超过 2 个格子的部分，只用移动中间的一块就可以了。
E.[Ynoi2004] rsxc
弱化版。
给定 n 个不相互包含的区间 \([l',r']\) 求 \([l,r]\) 与所有 \(l\le r' \le r\) 的区间的交集之和。
这东西前缀和一下，分成两部分。完全包含和不完全包含，分界点预处理一下，就线性了。
F.[Ynoi Easy Round 2023] TEST_107
究极卡常题。
相当于不包含一个数的最长区间长度，就是 B 了。
但是如果是 1 2 3 4 5 就不对了，所以还有找区间中所有出现过的数的最靠左的位置中最靠右的。
听起来很神经病，但是其实简单扫描线就可以了，每次把这些值的最左边的值扔进 set，可以简单处理。
右边其实同理，也能用线段树做，一坨……
G.k-d-sequence
按 \(\bmod d\) 分组，只有一样的部分可能有答案。
考虑什么情况下可能有结果，首先不能有相同值，其次就是空隙数量不超过 k。
空隙数量就是 max-min+1-(r-l+1)，就是满足 \(max-min-r+l-k\le 0\)
扫描 r，然后在 l 记录这个东西，然后右移指针，用单调栈维护一下，区间修改。
查找可以线段树二分。
H.フードコート
交换时间和位置，维护一下修改情况。
麻烦的点在于有可能会删空，在不空的情况下可以独立考虑加入删除。
假设删了 x 个，直接查第 x+k 个位置，线段树二分。
可以找最后删空的位置，考虑什么时候会删空，就是前缀和最小的位置。
证明一下，因为删空必然有一段为负，而每次删空必然前缀和增加一个负数，最后一次必然前面有最多的删空次数。
且此时如果有值，那么它一定会多一个正贡献，所以前面一定有比它更小的。
I.
给一些路径，求区间路径并。
同区间的区间并，套个树剖就行了。
J.众数
分块，每次从最后的块开始，从后往前找，从前往后扫这个块。
可以倍增分块，因为每次浪费的查询长度一定不会长于 k。
\(O(1)\) 修改每个块其实打个标记，因为一定会推到，所以修改量就是查询量。
K.Communication Towers
难以删除，线段树分治，但是难以标记点是否连通。
考虑建虚点，每次合并把对应连通块连到虚点上，每次删除直接拆掉虚点，下放标记。
还要维护一个路径压缩的并查集，保证复杂度。
L.[ROI 2023] 生产计划 (Day 2)
考虑先求出一个最大独立集，每次选一个点 +1，发现每次只能变化 1。
先求最大和最小情况下的最大独立集，显然中间的部分一定能构造出来。
考虑每个点增加对答案的影响，这东西的变化函数一定是先不动在斜率为 1。
动态维护最大独立集可以动态 dp，上树维护。