加训大数据结构。
「LG6109」[Ynoi2009] rprmq1
在一般的矩形修改问题中，有时间，横坐标，纵坐标三维，而这题只有横纵坐标两维，所以这本质上是序列上的问题。
如果对于每次查询，都有 \(l_1=1\)，那么直接扫描线，用线段树维护第二维的历史最大值就好了。
对于一般情况，需要在第一维进行分治，用类似猫树的方法转化成 \(l_1=1\) 的情况。
实现可能要精细一点，时间复杂度 \(O(mlog^2n+qlogn)\)。
「LG8512」[Ynoi Easy Round 2021] TEST_152
简单题。
如果确定了 \(r\)，无论如何选取 \(l\)，对于所有 \(i\ge l\)，对答案的贡献都是一定的。有影响的只有所有 \(i<l\)，它们的贡献变为 \(0\)。
对于时间做扫描线，我们要维护的是任意一个前缀的贡献和。注意到操作是一个区间推平，于是使用珂朵莉树就做完了。
时间复杂度 \(O(nlogn)\)。
「LG8337」[Ynoi2004] rsxc
找到结论这题就简单了。 不在线的做法：
可以发现合法的充要条件是，\(S\) 中的所有数二进制下有 \(k\) 个位置有 \(1\)，且 \(|S|=2^k\)。证明可以考虑线性基。
对右端点扫描线，用线段树维护所有左端点：到右端点的区间哪些位置有 \(1\)，还缺多少个数达到“饱和”，历史达到“饱和”右端点个数。
第一个信息使用 Segment Tree Beats 维护；而后两个就是经典线段树打标记。
时间复杂度 \(O(nlognlogV+qlogn)\)。
然而我猛然发现这题强制在线，题面却没写，所以这个做法死了。
「LG7907」[Ynoi2005] rmscne
记 \(w(l,r)=\min_{[l',r'] 合法} r'-l'+1,wl(l,r)=\min_{[l,r'] 合法} r'-l+1\)。
则有 \(w(l,r)=\min_{[l',r] 合法}wl(l',r)\)。
对右端点扫描线，我们是容易对每个 \(l'\) 维护出 \(wl(l',r)\) 的（只需知道上一个 \(a_r\) 出现的位置即可）。而对于一个确定的 \([l,r]\)，我们也很好算出最大的 \(l'\)，使得 \([l',r]\) 合法。
那么就做完了，时间复杂度 \(O(nlogn)\)。
「LG8265」[Ynoi Easy Round 2020] TEST_63
这题一看就很 LCT，所以就用 LCT 维护。维护森林的虚实链剖分，使得其与轻重链剖分一致。
每次 \(\text{makeroot},\text{link},\text{cut}\) 操作时，我们都可以先 \(\text{access}\)，认为重儿子就是此时的实儿子。注意到此时仅会使 \(O(logn)\) 个点的重儿子发生改变，所以可以暴力修改，问题是如何找到这些点。
考虑树上一条 \(u->v\) 的边，若这条边为轻边，则一定有 \(sz_u>2sz_v\)，且存在 \(k\) 使得 \(sz_u\ge 2^k>sz_v\)。
我们可以枚举这个 \(k\)，找到最深的 \(u\)，满足 \(2^k\le sz_u\)，就可以找到所有需要切换轻重的边了。
最后在全局用一个数据结构维护即可，时间复杂度 \(O(nlog^2n)\)。
「LG6780」[Ynoi2009] pmrllcsrms
把原序列以 \(c\) 为块长分块，那么有两种贡献答案的方式，一是块内最大子段和，二是两个相邻块间取一个前缀，一个后缀。
第一种是容易处理的，整块直接贡献，散块在查询的时候额外做一次线段树就好了。
对于第二种，我们先复制一遍原序列，然后右移 \(c\) 位。则答案变为在一个整块内选择一个不能有交的前缀和后缀（注意这二者不是同一个序列）。
整块还是直接贡献，散块要写得精细一点，时间复杂度 \(O(nlogn)\)。
「LG6105」[Ynoi2010] y-fast trie
这题没独立做出来，感觉有点溜大。
先取模，最优解有两种情况，一是 \(x+y\in[0,c)\)，二是 \(x+y\in[c,c+c)\)。后者是平凡的，取最大值与次大值即可，主要问题在于前者。
一个简单的想法是维护每个数的最优匹配，但删除要修改 \(|S|\) 个点。考虑最终贡献到答案的最优匹配一定是双向的，那么我们维护所有的“双向最优匹配”，就可以做到只修改 \(O(1)\) 个点了。
还有一种处理方法就是上面那个题的做法，但我就是没想到……
时间复杂度 \(O(nlogn)\)。
「LG6018」[Ynoi2010] Fusion tree
简单题。
对于一个结点 \(u\)，维护它的所有儿子的信息，父亲可以 \(O(1)\) 访问。
换而言之，我们要维护一个集合，支持加/删点，全局加一，查询全局异或和。可以用 Trie 实现，时间复杂度 \(O(nlogn)\)。
「LG8530」[Ynoi2003] 博丽灵梦
对第一维回滚莫队（只删除），然后就有 \(O(n\sqrt m)\) 次修改操作，\(O(m)\) 次二维数点。
上一个二维分块就做完了，但是我不会这个科技，自闭了。
「LG8336」[Ynoi2004] 2stmst
这种奇怪权值求最小生成树的题一般考虑 Boruvka。
考虑 \((x_i,y_i)\) 的最优出边 \((x_j,y_j)\)，其中一维没有子树关系的情况是简单的，剩下的话分类讨论。
-
如果 \(x_i\) 为 \(x_j\) 的祖先且 \(y_i\) 为 \(y_j\) 的祖先，对 \(x\) 线段树合并，线段树的下标是 dfs 序。
-
存在 \(x_j\) 为 \(x_i\) 的祖先，或者 \(y_j\) 为 \(y_i\) 的祖先，更为简单，直接在树上 dfs 一下就好了。
时间复杂度 \(O(nlognlogm)\)。
标签：端点,17,复杂度,这题,唱片,2023.4,维护,nlogn,线段 From： https://www.cnblogs.com/Nesraychan/p/17327357.html