Ynoi
大战 Ynoi 系列，顺序是洛谷题号排序。
已经有标题但是还没写 sol 的是因为博主是个大鸽子。
P4690
区间赋值，区间数颜色。
考虑静态询问区间颜色总数的经典问题怎么做？定义 \(pre_i\) 表示 \(i\) 之前最后一个和 \(i\) 颜色相同的下标。
那么询问 \([l,r]\) 的答案为 \(\sum_{i=l}^r[pre_i<l]\)。使用二维数点可以以 \(O(n\log n)\) 的复杂度解决。
沿袭静态的做法，很容易做单点修改的问题：多带一维时间，离线使用 CDQ 分治即可以以 \(O(n\log^2 n)\) 的复杂度解决。
考虑使用 ODT 进行区间推平，颜色连续段修改时仅会改变开头位置的 \(pre\) 值，容易势能分析出总共仅有 \(O(q)\) 次单点改变 \(pre\) 值，离线使用 CDQ 分治即可。
时间复杂度 \(O(n\log^2n)\)。
P5065
给定一个长度为 \(n\) 的序列，单点修改，询问满足区间 or 不小于某个值的区间的最短可能长度。
一个经典的结论是固定一个端点，区间 or 只有 \(w=\log V\) 段单调的值。
维护每个位置 \(i\) 往后第 \(j\) 个 bit 出现的第一次下标 \(f_{i,j}\)。考虑 \(i\) 之后的 \(w\) 段不同的区间 or 可以通过排序 \((f_{i,j},j)\) 找到。对于 \(i\) 的升序 \((f_{i,j},j)\) 序列转移到 \(i-1\) 的序列仅需考虑对序列进行归并（重复的 \(j\) 只取较前者）。单次复杂度 \(O(w)\)。
考虑分块，设块长为 \(B\)，考虑对于每个块维护 \(mx_i\) 表示块内长度为 \(i\) 的区间能取到的最大区间 or，维护块左端点在块内往后的 \((f_{l,j},j)\) 升序序列以及块右端点在块内往前的 \((f_{r,j},j)\) 降序序列。
对于修改，容易 \(O(Bw)\) 重构出块内维护信息。
对于查询，对于每个块内的区间可以 \(O(\log n)\) 找出答案，合并出前缀块右端点往左的信息与后缀块左端点往右的信息（复杂度 \(O(\dfrac n Bw)\)），枚举块间，双指针贡献答案。
取 \(B=\sqrt n\)，总复杂度 \(O(n\sqrt n\log V)\)。
P5311
给定一棵大小为 \(n\) 的树，点有颜色，\(m\) 次询问保留编号在 \([l,r]\) 的点后，\(x\) 所在连通块颜色种类数。
考虑任意一个连通块在点分树上一定均在一个子树里（连通块中在点分树上深度最小的点）。
考虑对于一个询问找到 \(x\) 所在连通块在点分树里深度最小的点（记录点分治每一层每个点到重心的节点 \(mn,mx\)）。
对于一个点可以放在二维平面的 \((mn_i,mx_i)\) 上，询问 \(x\geq l,y\leq r\) 的点的颜色种类数。
考虑按 \(mn\) 从大到小排，扫描线，维护每个颜色出现的 \(mx\) 最小值，使用树状数组。
总时间复杂度 \(O(n\log^2n)\)。
P5397
给定一个长度为 \(n\) 的序列，将所有值为 \(x\) 的位置修改为 \(y\)，查询 \(x\) 和 \(y\) 的最近距离。
考虑根号分治。
若询问中两个颜色的集合大小（下文称颜色大小）均不超过 \(\sqrt n\)，那么暴力归并可以得到答案。
否则对于一个大小超过 \(\sqrt n\) 的颜色，预处理其与其它所有颜色的答案。
若合并的两个颜色大小均不大于 \(\sqrt n\)，直接合并，修改大块对小块的答案，如果合并后大小超过 \(\sqrt n\) 成为大块，那么 \(O(n)\) 预处理其与其他所有颜色的答案。
若合并的两个颜色大小均大于 \(\sqrt n\) 的，直接合并，暴力修改大块对小块的答案，复杂度 \(O(n)\)。
否则考虑小块和大块的合并，对于每个大块维护一个附属集合用于处理与其合并的小块，将小块与附属集合合并，转换成小块与小块合并的情况。
复杂度分析考虑大块之间的合并仅有 \(O(\sqrt n)\) 次，总复杂度 \(O(n\sqrt n)\)。
P6109
P6578
单点修改，询问区间的子区间最大值 \(\leq x\) 的子区间个数。
静态怎么做？考虑询问离线，按 \(x\) 升序排列，按权值升序加入下标，使用线段树维护已加入的极长连续段（\(\dbinom{len} 2\) 和）。时间复杂度 \(O(n\log n)\)。
考虑单点修改怎么做。操作分块，每次处理 \(O(\sqrt n)\) 个询问和 \(O(\sqrt n)\) 个修改。
考虑沿袭静态问题的想法，按权值升序加入下标，将涉及修改的下标空着，按 \(x\) 升序排列询问，每个询问都将在其前的修改做一遍。
仍然可以使用线段树，不过带 \(\log n\)，无法通过，修改 \(O(n\sqrt n\log n)\)，查询 \(O(n\log n)\) 过于不平衡，考虑设计一个序列分块平衡复杂度。
序列分块里维护块前缀极长 1 段，后缀极长 1 段，块内除前后缀极长 1 段 \(\dbinom{len} 2\) 和，块内维护一个极长 1 段起点到终点的链表，修改时容易 \(O(1)\) 更改链表，查询时散块暴力，整块利用维护信息即可，每个询问后撤销修改。
总复杂度 \(O(n\sqrt n)\)。
P6780
给定一个长为 \(n\) 的序列 \(a\) 和常数 \(c\)，\(m\) 次操作，支持单点修改，询问区间内子区间长度不超过 \(c\) 的最大子段和。
考虑按 \(c\) 对序列分块。
区间长度不超过 \(c\) 的区间要么完整包含在一个块里，要么仅跨越两个相邻块。
我们分别计算两种情况的贡献。
对于前者，我们考虑每个块维护一颗线段树维护最大子段和，容易支持单点修改。
再维护一颗下标为整块的线段树，询问时查询一个区间的整块信息。散块在每个块对应的线段树里查贡献即可。
这部分复杂度单 \(\log n\)。
跨块的情形我们可以再分成跨越两个整块和两边的两个散块和整块/散块和散块。
具体的，考虑左块长为 \(i\) 的后缀（记后缀和为 \(A_i\)）和右块长为 \(j\) 的前缀（记前缀和为 \(B_j\)）拼出的一个子段，满足 \(i+j\leq c\)，可以贡献 \(A_i+B_j\)。
我们反转 \(B\) 数组，令 \(j=c-j'\)，则\(i\leq j'\)，这样的最大值容易线段树 pushup 时维护。
单点修改只是区间修改 \(A,B\) 数组。
带散块的情形只是多一个区间限制。
总复杂度 \(O(m\log n)\)。
P7124
P7126
P7722
P8265
P8336，[CTS2022] 燃烧的呐球
一个 \(n\) 个点的以 1 为根的有根树，有 \(m\) 个二元组 \((x_i,y_i)\)。定义 \(D(a,b)\) 表示在 \(a\) 子树里却不在 \(b\) 子树里的节点个数。
一张 \(m\) 个点的完全图，\(i,j\) 之间的边权为 \(D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)\)，求最小生成树大小。
直接上 Boruvka。
分析一下 \(D(a,b)+D(b,a)\) 。当 \(a,b\) 没有祖先后代关系时，值为 \(siz_a+siz_b\)，否则不妨设 \(a\) 是 \(b\) 的祖先，值为 \(siz_a-siz_b\)。
试图分类讨论 \(x_i,x_j\)，\(y_i,y_j\) 两对点的位置关系，统计 Boruvka 每一轮中每个点异色的最小边。
具体的，对于 \(x_i,x_j\) 或者 \(y_i,y_j\) 没有祖先后代关系的情况比较容易，这里讨论前者，后者对称。
我们可以把 \(+siz_{x_i},+siz_{x_j}\) 挂到 \(y_i,y_j\) 上，对于一个固定的 \(y_i\)，我们只需要查询其子树内异色的最小的 \(siz_{x_j}-siz_{y_j}\) 以及子树外异色的最小的 \(siz_{x_j}+siz_{y_j}\)。
我们可以通过维护最小次小换根 DP \(O(n)\) 的完成这个部分。
对于 \(x_i,x_j\)，\(y_i,y_j\) 均有祖先后代关系的情况我们进行更细致的讨论。
-
\(x_i\) 是 \(x_j\) 的祖先，\(y_i\) 是 \(y_j\) 的祖先。
我们可以以 \(y_j\) 的 DFS序作为下标线段树合并，dfs 时遇到一个 \(x_j\) 我们在 \(y_j\) 的 DFS 序插入贡献。
遇到 \(x_i\) 时，查询 \(y_i\) 子树内的最小次小完成异色查询。
时间复杂度 \(O(m\log n)\)。 -
\(x_i\) 是 \(x_j\) 的祖先，\(y_j\) 是 \(y_i\) 的祖先。\(x,y\) 反过来对称。
DFS 到 \(y_j\) 时在 \(x_j\) 的 DFS 序插入贡献，到 \(y_i\) 时查子树 \(x_i\) 内的最小次小完成异色查询。
回退时撤销 \(x_j\) DFS 序上的信息即可。时间复杂度 \(O(m\log n)\)。
-
\(x_j\) 是 \(x_i\) 的祖先，\(y_j\) 是 \(y_i\) 的祖先。
延续情况 2 的想法。DFS 到 \(x_j\) 时在 \(y_j\) 插入贡献，到 \(x_i\) 时查 \(y_i\) 到根的链上的最小次小信息完成异色查询。
回退时撤销 \(y_j\) 贡献即可。
可以树剖线段树做到 \(O(m\log^2 n)\)，或者全局平衡二叉树 \(O(m\log n)\)。
总复杂度取决于情况三的实现，\(O(n\log m+m\log^2n\log m)\) 或者 \(O(n\log m+m\log n\log m)\)。
P8337
给定一个长为 \(n\) 的数组 \(a\)，\(q\) 次询问一个区间有多少子区间满足元素对异或封闭，强制在线。
一个经典的结论是一个元素集合 \(S\) 对异或封闭等价于 \(|S|\geq 2^k\)，\(k\) 为集合 \(S\) 的线性基大小。
考虑扫描子区间的右端点，在线性基中加入元素采取经典的区间线性基处理（CF1100F），那么区间 \([l,r]\) 的线性基大小就是线性基内标记 \(\geq l\) 的元素个数。
我们将线性基内的标记排开，对于每个 \(k\) 都可能存在一段【有贡献的左端点区间】，一个较好的性质是对于同一个 \(k\)，右端点增时有贡献的左端点区间做右端点不降。
对于一次询问 \([L,R]\)，我们枚举 \(k\)，只需要得到 \(r\leq R\) 的所有【有贡献的左端点区间】和 \([L,R]\) 的交的长度和。
狂暴差分预处理，容易 \(O(1)\) 计算。
总复杂度 \(O(n\log n)\)。
P8512
一个长为 \(m\) 的序列，初始全 0，有 \(n\) 个区间赋值操作。
\(q\) 次询问进行完一个区间的区间赋值操作后整个序列里所有数的和，询问独立。
询问离线扫描线，珂朵莉树维护每个位置最后一次被覆盖的操作编号，拿一个 BIT 维护以最后一次操作编号为下标的元素和。
单个询问就是查询最后一次覆盖编号不小于 \(l\) 的元素和。
时间复杂度 \(O(n\log n)\)。
P8526，[CTS2022] 普罗霍洛夫卡
P8527
两个长度为 \(n\) 的序列 \(a,b\)，初始 \(b\) 全 0。
\(m\) 次操作每次形如给定一个 \(a\) 上的区间，将其平移到 \(b\) 的某一段加到 \(b\) 上。
操作让我们想到了多项式乘法。
我们考虑分块，散块暴力加，整块打平移 tag。最终每个块会有若干个 tag，将他们写成多项式的形式，FFT 优化。
设块长为 \(B\)，复杂度为 \(O(mB+\dfrac{n}{B}(n\log n+m))\)，\(B\) 取 \(\sqrt n\) 复杂度为 \(O(m\sqrt n+n\sqrt n\log n)\)。
P8528
P8530
一个 \(n\) 个点的二维平面，第 \(i\) 个点坐标为 \((i,p_i)\)，\(p\) 为一个 \(n\) 阶排列，每个点有一个颜色，不同的颜色有权值。
\(m\) 次查询矩形内不同颜色权值和。
对横坐标莫队，问题变成 \(O(n\sqrt m)\) 次加删元素，\(O(m)\) 次查询区间不同颜色权值和。
以 \(l\) 为横坐标，\(r\) 为纵坐标建立新的坐标系，对于一个颜色出现的若干位置 \(x_k\)，可以刻画成 \((x_k,x_k)\) 的左上角覆盖，利用前驱后继信息可以差分成 \((x_k,x_k,+1),(x_k,x_{k+1},-1)\) 单点加，矩形求和，的形式。
前驱后继查询如果直接使用 set 等数据结构得带 \(\log n\)，考虑使用不增加莫队利用链表解决。
查询考虑二位分块。对横坐标纵坐标分别先分 \(n^{0.75}\)，每个块内分 \(n^{0.5}\)。
那么一次矩形询问会变成 \(n^{0.25}\times n^{0.25}\) 个 \((n^{0.75}/n^{0.5},n^{0.75}/n^{0.5})\) 整块和横坐标 \(n^{0.5}\) 的散块和纵坐标 \(n^{0.5}\) 的散块。
基于单点加的特殊形式，对于同一个横坐标，最多只有两个纵坐标有单点加，对于同一个纵坐标，也最多只有两个横坐标有单点加。那么散块我们暴力查询即可。故查询复杂度 \(O(n^{0.5})\)。
修改仅需要 \(O(1)\) 修改单点所在块信息。
总复杂度 \(O(n\sqrt m+m\sqrt n)\)。
标签：单点,log,复杂度,Ynoi,sqrt,区间,询问 From： https://www.cnblogs.com/juju527/p/17017908.html