数据结构选做
数据结构综合选做
高妙分块都塞进分块选做了
P3714 树的难题 [点分治] [线段树] [单调队列]
线段树解法
用线段树维护之前的子树中, 与当前子树颜色相同和不同的情况, 把颜色排序, 可以保证先前碰到的颜色不相同后后面不会再相同, 每次到新颜色则把相同颜色插入到不相同颜色中.
单调队列合并
to do
P3345 幻想乡战略游戏 [点分树] [线段树]
- 重心的性质, 可以利用对当前答案移动一条边的方式证明答案既是全树点带权重心(边权无影响), 每次会走向自己儿子中点权和大于一半的儿子,
解法1: 线段树
由于所有大于一半的儿子形成了由根开始的一条链可以直接在线段树中二分出重心, 问题变为求所有点到重心的距离, 设重心为u, 点到根距离为dis, 则答案为:
- $$ \sum dis_u+dis_v-dis_{lca(u, v)}\\=\sum dis_u + \sum dis_v - \sum dis_{lca(u, v)}$$
其中前两个式子可以直接求解, 最后一个式子则考虑首先 lca 一定在u到根的链上, 其中考虑边 e 被 dis_{lca(u, v)} 计算的次数为 e 较深端点的子树大小 (这个子树中的每个 v 都可以和 u 构成一个 lca 在e下的点对), 所以对每个点维护父边边权和子树大小的乘积, 注意这里大小都是点权和
解法2: 动态点分治
to do
P632 9震波 [点分树]
每层维护两棵线段树, 下标 i 表示到父亲或当前点的距离为i的点的和, 查询从叶子出发向上跳, 算上当前层的, 容斥掉父亲的
P4587神秘数 [主席树]
一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数. 例如 $S={1, 1, 1, 4, 13}$, 有: $1 = 1$, $2 = 1+1$, $3 = 1+1+1$, $4 = 4$, $5 = 4+1$, $6 = 4+1+1$, $7 = 4+1+1+1$.
$8$ 无法表示为集合 $S$ 的子集的和, 故集合 $S$ 的神秘数为 $8$.
现给定长度为 $n$ 的正整数序列 $a$, $m$ 次询问, 每次询问包含两个参数 $l, r$, 你需要求出由 $a_l, a_{l+1}, \cdots, a_r$ 所组成的可重集合的神秘数.
对于 $100%$ 的数据点, $1\le n, m\le {10}^5$, $\sum a\le {10}^9$.
若当前可表示的值域为 [1, x] , 升序加入值v后, 若v>x+1, 则x+1一定无法表示, 答案为 x+1 , 否则答案为 x+v
发现若一个区间中数均不大于 x+1 , 则这个区间的数可以一起加进去, 答案更新为x+区间和
于是可以用线段树优化, 在值域上建线段树, 每次线段树查出所有未被加入的数中不大于 x+1 的数的和, 若为0说明无数可加, 答案为x+1, 否则把这个和加进答案, 暴力重复这个过程
对于复杂度, 设 $b_i$ 表示第 i 次的x+1, 那考虑对于得到 $b_{i+1}$ 的过程中, 由于我们加入的区间中至少有一个数, 而且这个数上次没被加入说明这个数大于 $b_{i-1}$ 所以 $b_{i+1} = b_i + sum_i > b_i + b_{i-1}$ b的增长是严格大于斐波那契的, 斐波那契增长是指数的, 所以我们最多进行 log(v) 次这个操作
P4197 Peaks [Kruskal重构树] [线段树合并]
如标签, 过于模板
P2839 middle [主席树]
中位数性质, 对中位数把所有大于它的设1, 小于的设-1, 答案是0, 然后主席树维护区间大于小于个数即可
P6071 TreeQuery [虚树] [主席树]
相当于p到[l, r]中点构成虚树的最短距离, 分几种情况:
p在虚树根的子树内, 则距离为把p添加到虚树后p到其父亲的距离, 有一个结论是一个点在虚树中的父亲是该点和所有点中它dfs序的前驱或后继的lca根据这个用主席树找区间前驱后继.
p在虚树根的子树外, 此时最短路径就是它和虚树根的lca.
虚树包含p, 答案为0.
P5069 [Ynoi2015] 纵使日薄西山 [线段树]
发现如果位置 $i$ 被操作, 那么位置 $i+1$ 和 $i-1$ 一定不会被操作, 因为它们永远不会比 $i$ 大了, 于是 $i$ 位置会被操作恰好 $a_i$ 次.
所以题目就成了给定一个序列求所有被操作位置的和.
发现合并两个区间时, 只要看左区间右端点和右区间左端点是否被选了去分类讨论, 如果都被选了就强制两个中小的那个不能选. 又因为我们会有钦定一个端点不能选的情况, 所以每个节点要记录4个情况, 分别表示是否忽略左右端点, 记录每个情况下的被操作位置和, 左/右端点是否被选.
拿着这个去讨论, 以得到父亲是两个端点都被选的为例, 发现:
- 若左区间右端点和右区间左端点未被同时选中, 则和可以直接相加, 左右端点是否选中直接照搬左右区间完整情况的左右端点信息.
- 若同时选中, 则比较两个端点谁的值更大, 若左端点的更大, 则合并左端点完整区间情况和右端点忽略左端点情况. 右端点更大的同理
于是可以写出线段树的更新, 接下来可以单点修改, 区间赋值, 区间加, 区间查. . . 然而这题只要写个单点修改就行了.
P5070 [Ynoi2015] 即便看不到未来 [树状数组] [性质]
首先有比较明显的莫队做法, 维护一个值域数组, 在连续值域段的左右端点记录对应的另一个端点位置, 添加一个元素时像第十分块一样合并俩连续区间, 回滚
然后 $O(\sqrt n)$ 会时间炸飞, 显然 $10^6$ 次方是个单 log 做法, 3s是个大常数, 而且毒瘤肯定不会无端只问你1到10的, 一定要用这个条件
另一个维护序列区间的常用套路是右端点向右扫描数据结构维护左端点, 首先, 若记位置 $i$ 上一次出现位置为 $last_i$ , 则新增右端点 $r$ 只会影响 $(last_r, r]$ 这一个区间的左端点的答案.
然后再因为利用1-10的这个条件, 可以考虑把值在 $[a_r-10, a_r+10]$ 这个区间的数的最后一次出现位置拿出来, 按出现位置从大到小排序扫描, 取最后一个原因是这个数是否在区间 $[l, r]$ 中出现取决于 $l$ 和这个数最后一次出现的大小关系, 从右往左扫是意味着出现的值只会增加而不会减少, 可以用莫队的 $O(1)$ 维护方式.
于是相当于这21个数把 $(last_r, r]$ 区间划分成若干段, 每个段值的出现情况相同, 由于每次是算出这个区间的左端点增加了多少, 所以数据结构只要单点查和区间加, 可以用一个树状数组, 而且是对每个答案分别开一个树状数组维护.
然后你发现莫队的O(1)方式是毫无必要的, 码量大细节多, 而因为你在扫这个区间的过程中始终只计算某一时刻 $x$ 的贡献, 所以只要记两个指针表示x往上/往下连续段最大到哪就均摊 $O(1)$ .
代码不多, 但有一堆一堆细节, 放段核心代码:
1 | for (int i = 1; i <= n; i++) { |
P5354 [Ynoi2017] 由乃的 OJ
大家肯定都做过那个经典的序列上全局的版本, 那么对于这个题可以相同方式考虑.
由那个题我们知道位运算每一位是独立的, 只要从高位往低位看每一位能不能是1就行了.
首先考虑序列上的区间询问, 那么容易发现可以简单线段树维护, 每个点记录在每一位1进去出来什么和0进去出来什么.
然后搬到树上可以合并方式不变的变成LCT和树剖, 此时要注意要记录两个方向(到序列上就是从左往右和从右往左)走的进出映射, 因为一条链又有向上的又有向下的.
然后被卡常了, 需要用位运算优化, 可以把每一位进去1出来什么这种压成一个int, 直接位运算, 然后就能过了.
由于合并操作比较复杂且询问的时候也要用这种合并操作, 一般就把线段树存的数据写成结构体了. 这里只放合并信息的关键代码:
1 | //Dat是记录的信息,zero,one,rzero,rone每一位分别表示这一位正着走一开始是0,正着走一开始是1,反着走一开始是0,反着走一开始是1四种情况. |
树剖查询的时候注意分清向上向下的细节.
P5068 [Ynoi2015] 我回来了
首先显然乘上区间长度后问的就是每个 $d$ 的次数之和.
由于两个血量相同的小兵和一个是等价的, 可以把小兵按血量映射到一个数轴上.
而对于一个 $d$ , 这个答案次数就等价于把数轴分成若干长为 $d$ 的块, 求一个最长的前缀使得每一块里都至少有一个数.
考虑对于每个 $d$ , 可能的答案只有 $\frac {n} {d}$ 种, 调和级数分析一下发现, 总数是 $n \log n$ 的, 那么答案变大一, 或者说前缀向后拓展一块的次数也是 $n \log n$ 的.
于是插入一个点时, 我们要能快速找到包含一个点的区间, 并支持插入和删除区间.
一开始想了一种建出线段树, 把一个区间拆成 $\log n$ 段挂到节点上标记永久化, 发现这玩意删除是困难的
正确的做法是, 考虑开 $n$ 个 set , 第 $i$ 个里面有以 $i$ 为左端点的区间的右端点, 再开一棵线段树算区间内set里面放的右端点的最大值, 查包含 $p$ 的所有区间时只要查左端点在 $1-p$ 的最大右端点, 并把这个区间删了加新的, 不断重复这个过程, 直到右端点在 $p$ 左侧.
这样就能做了, 但还有个很厉害的离线做法.
考虑反向考虑, 要求 $[l, r]$ 的和, 可以考虑哪些小兵会贡献一个答案, 发现仍然应该转化成数轴模型, 那么算出每个块最早开始有数的时间 $t$ , 插入点 $(d, t)$ , 查询就是查时间在询问之前的并且伤害 $d\in[l, r]$ .
这是个静态二维数点, 由于有 $n \log n$ 个点所以复杂度 $n \log^2 n$ , 而每个块最早有数的时间只要先处理每个位置最早开始有数的时间就可以ST表或猫树 $n \log n$ 解决了.
写的第二种做法, 不怎么卡常, 不用快读快写不很稳, 如果放个fread/fwrite基本就很没问题.
Frog 2022一轮省集
给一个序列 $a$ , 每次查询区间 $[l, r]$ 中最短的区间 $[l’, r’]$ 满足 $[l, r]$ 中出现的数都在 $[l’, r’]$ 出现.
std:
考虑序列上扫描线扫描答案右端点, 开一个set维护所有数的最后一次出现都位置, 记 $last_i$ 表示 $i$ 的上一次出现位置, 那么对于位置 $r$ 作为右端点时, 只有询问的 $l$ 在 $(pre(last_i), last_i]$ 中时答案才可能比 $r-1$ 更优, 记这个区间为 $rg_r$ , 且这一段答案是一样的, 为 $ans_r=r-succ(last_i)+1$ , pre表示一个数在set中的前驱. 所以我们对每个询问处理出它的 $r_0$ 表示 $r’$ 只有在 $r_0$ 右边才能包含区间中所有的数, $r_0$ 可以简单线段树求. 接下来就变成了对于一个询问 $[l, r]$ , 求 $\min_{r’=r_0}^r ans_r’, \ s. t. \ i\in rg_r’$ , 这个可以再跑第二遍线段树扫描线解决.
zsy 吊打 std:
直接维护答案, 在序列上扫描线扫描询问的右端点, 开一个线段树, 维护 $r_i$ , $len_i$ , 表示以 $i$ 为答案左端点时对应答案右端点的位置和答案长度, 显然 $len_i=r_i-i+1$ . 那么若当前位置为 $r$ , $a_r$ 上一次出现在 $a_pre$ , 则 $a_r$ , $a_pre$ 中的答案左端点对应的答案右端点一定要包含 $a_r$ 所以都设成 $a_r$ .
每次查询的时候, 查的就是区间 $\min len_i\ s. t. i\in[l_0, r]$ , 其中 $l_0$ 表示 $[l, r]$ 中最短的后缀包含其中所有元素的左端点, 或者说区间里所有数的最后一次出现位置的min, 这个可以用线段树做不影响复杂度. 也可以并查集卡个常.
ZSContest5 [主席树]
给定一个长 $n$ 的排列, $q$ 次选定长度相同的两个区间 $a$ , $b$ , 保证第二个区间在第一个区间右侧(不相交), 询问第二个区间的重排中有多少种使得每一位都大于第一个区间对应位. $n, q\le 10^5$ . 排列逆序对数不超过 $10^5$ . 3s
这个逆序对很突兀啊, 一看就是复杂度相关, 然而仍然不会做啊.
记 $cnt_i$ 表示 $b_i$ 大于 $a$ 中的 $cnt_i$ 个数. 答案显然为 $\prod (cnt_i-i+1)$ , 这里 $i$ 顺序任意.
那么考虑利用逆序对的条件, 两个区间形成的逆序对个数为 $\sum (m-cnt_i)\le k$ , 所以 $m-cnt_i$ 和 $cnt_i$ 只有 $\sqrt k$ 种取值, 需要相同 $cnt$ 一起计算, 由于顺序任意按照 $cnt$ 从小到大也是值从小到大计算, 那么就要支持查等于某 $cnt$ 的有多少种.
用主席树求即可. 仍然值域上建, 实现一下rank和kth即可每次动态跳不同 $cnt$
最后复杂度 $(n+q\sqrt k)\log n$ , 可能因为 $\sqrt n$ 不满能跑 $10^5$ 吧.
CF639F Bear and Chemistry [虚树] [tarjan]
给定一张 $n$ 个点 $m$ 条边的初始无向图.
$q$ 次询问, 每次询问给定一个点集 $V$ 和边集 $E$ .
你需要判断, 将 $E$ 中的边加入初始无向图之后, $V$ 中任意两个点 $x$ , $y$ 是否都能在每条边至多经过一次的情况下从 $x$ 到 $y$ 再回到 $x$
$n, m, q, \sum \vert V\vert , \sum\vert E\vert \le 3\times 10^5$ , 强制在线.
众所周知绕一圈回来这个相当于 $V$ 的点位于同一边双. 而 $V$ 这个询问方式让人想到虚树. . . 之类的东西.
于是显然边双缩点变成一棵树, 然后可以用NOI2021庆典的做法去求虚树用虚树上的点建图跑tarjan解决问题.
[NOI2020山东省队集训 Day7]货车运输
$n$ 点 $m$ 条边, $q$ 次查询任意把一条边改成 $inf$ 后, 两点之间边权最小值最大.
$n, m, q\le 3\times 10^5$
建kruskal重构树, 二分答案, 那么相当于我们同时从起点和终点向上跳, 然后查询这两棵子树内是否有边. 这个可以直接二维数点, 或者线段树合并. 复杂度 $n\log^2 n$
考虑整体二分的思想, 离线询问后将每一轮二分的值拿出来, 从小到大排序, 并模拟kruskal的过程, 并查集维护连通性, 那么就可以知己并查集知道两棵子树是否有边了.
CF983D Arkady and Rectangles
给定平面上 $n$ 个矩形, 标号大覆盖标号小的, 求最后平面上能看到的颜色个数.
$n\le 10^5$ , 值域 $10^9$ .
暑假和杜赢看的ds题, 一直没记录.
rewrite 2024. 3. 1
扫描线, 区间覆盖颜色段均摊掉, 另外肯定有线段树套东西. 每个点开个set存当前节点上的颜色覆盖标记, 则一个点真实颜色是其到根的路径的set中的最大值. 颜色应该在其第一次出现时统计, 则覆盖时要知道这个颜色有没有露出来, 比较其和 当前子树内所有叶子到根路径上最大值的最小值 即可.
此外可能会若干次删除一个颜色, 会露出被覆盖的颜色, 每个颜色只有 $\log n$ 个标记, 考虑均摊的每次合并一个. 考虑维护每个set中最大的没看到的颜色 $mc$, 和子树中最大的没看到的颜色 $tc$, 则可以快速判断一个子树是否存在新颜色, 于是可以以 $\log n$ 的代价移除一个标记, 总复杂度 $n\log^2 n$
P3295 [SCOI2016]萌萌哒
给定序列长度和限制个数, 每个限制 $(l_1, r_1, l_2, r_2)\ s. t. \ r_2-l_2=r_1-l_1$ 表示序列 $[l_1, r_1]$ 和 $[l_2, r_2]$ 完全相同, 序列每个数都在 $[0, 9]$ 中, 求序列个数.
膜 $10^9+7$ , $n\le 10^5, m\le 10^5$ .
同样是和杜赢看的题.
单独考虑每一位的可能, 发现我们的问题相当于区间 $l_1+i$ 对应连边 $l_2+i$ , 最后求连通块个数. 那么一个 $n^2$ 是暴力并查集.
考虑现在要优化这个暴力, 我们用st表结构把每个区间拆成2个的并, 而一个长度为 $2^k$ 的显然有可以再合并到两个长度为 $2^{k-1}$ 的.
于是我们一开始只直接合并每个区间拆出来的那两个, 再所有合并都结束之后, $k$ 从大到小遍历: 对于一个 $k$ 的一个连通块, 每一个节点拆成两部分在 $k-1$ 连成一个连通块, 就到了 $k-1$ 这一层, 发现这样做是线性的, 你就做完了.
那么这个题现在是修改 $q\alpha(n)$ , 查询 $n\log n \alpha(n)$ 的. 不能用线段树的结构因为结构不对应.
能优化的本质是我们本来连了一个稠密图, 现在从顶上一层一层向下的过程中我们保证了每次都仅连最少的边. 于是每一层的复杂度贡献都是线性的.
顺手写一发, 发现我像个智障. 码力没了.
ABC238G
给定一个序列 $a_n$ , $q$ 次判断一个区间的乘积是否是完全立方数.
忘了数据范围所以福建OI
降智题, 和qyc一起降大智.
每个数拆成小于 $V^{\frac{1}{3}}$ 的质因数和一个质数, 那么小的直接前缀和, 大的莫队, 就是根号的.
然后发现我们是智障, 它相当于判断两个前缀的所有质因数次数膜3相同, 直接hash复杂度是 $n\log v$ 的.
CF1588F Jumping Through the Array
给定 $a_n$ 和排列 $p_n$ , 对每个 $i$ 建有向边 $(i, p_i)$ , $q$ 次操作:
- 询问 $a$ 区间和
- 对点 $u$ 能走到的所有点加 $x$ .
- 交换 $p_x$ 与 $p_y$
$n\le 2\times 10^5, 8s$
第一眼看成在内向基环树森林上做这个问题, 好吧其实是一堆环.
那么第三个操作会把环断开或合并, 稍微考虑一下发现断开和合并是十分”自由”的, 也就是说找不到多大性质.
$8s$ 提醒我们根号复杂度.
于是通过根号分治, 序列分块与一堆平衡树可以想到各种根号log.
考虑假设没有对环的修改, 你直接时间分块, 那么可以直接维护所有环, 加就直接加到环上, 区间和可以直接遍历被加的所有环去算对这个区间的贡献, 每根号个重构. 那现在有了对环的修改, 考虑在根号个修改的情况下, 你只切了根号刀, 所以实际上可以看成一共只有根号个点集, 那么加就直接遍历环包含的每个点集加, 询问考虑被加的每个点集的贡献, 这里不需要二分, 而是直接处理出每个数在这个块里被询问分成的根号段中的哪一段, 那么直接对每个环前缀和即可. 最后复杂度单根号.
我们糊出了不用时间分块的做法!
考虑根号分治, 那么在没有3操作的情况下, 小块加法直接暴力加到序列上, 大块加法把标记打在大块上, 那么查询的时候就查询序列上的和, 遍历每一个大环, 就行了.
现在有了合并/分裂, 仍然根号分治, 考虑对于一个大环, 维护的结构是一个块状链表, 链表上每一块维护其在原序列上的每一块的元素个数, 及其前缀和. 于是考虑:
- 查询
- 分成整块和散块
- 整块部分和遍历每一个大环的块状链表上的每一块, 就能 $O(1)$ 查询这一块其对序列上整块的和的贡献
- 散块部分若属于某个大环, 就直接查每个位置所属的大环的那个块的加法标记.
- 分成整块和散块
- 加法
- 大环: 遍历大环上的每一块, 打加法标记, 复杂度根号
- 小环: 暴力加到序列上
- 合并
- 就是把两个块状链表接起来, 可能会合并块状链表上的两块, 合并是根号的.
- 拆分
- 把一个块状链表拆成两个, 可能会把大块中间劈开.
合并拆分都是块状链表经典操作, 不再赘述.
注意复杂度分析的时候, 块状链表的块的总个数是根号的, 因为一个大环的块状链表上小于根号的块左右必然都是大于根号的, 而小环我们不开块状链表. 所以复杂度正确.
CF1746F Kazaee
给定 $a_n$ , $q$ 次询问区间 $l, r$ 中是否所有数都出现 $k$ 的倍数次.
$n, q\le 3\times 10^5$
直接hash, 对于每个数进行一个随机映射, 那么如果这个区间的和不是 $k$ 的倍数就说明不是, 是的话发现有 $\dfrac{1}{k}$ 的概率错, 所以跑30遍. 复杂度2log.
CF482E ELCA
给定 $T=Tree(n)$ , 根为 $1$ , $i$ 的父亲为 $f_i$ , 点有点权 $a_i$ , $m$ 次修改, 每次单点修改或者把以 $u$ 为根的子树挂到 $B$ 上(作为儿子), 每次修改后输出任意两个点的lca的权值的期望.
$n, m\le 5\times 10^4$
做dp的时候打错题号进来的. . .
先考虑静态怎么做, 以一个点 $u$ 为 lca 的方案数就是 ${siz_u}^2-\sum {siz_v}^2$ , $v$ 是 $u$ 的儿子. 那么子树接上去这个操作就是, 受影响的只有它到根的这条链, 看看是怎么影响的: 发现是减去 $2siz_v\cdot (siz_u-siz_w)$ , 其中 $w$ 是 $u$ 子树包含 $v$ 的儿子.
影响含有 $w$ 不好维护, 但直接重新合并可是简单的很, 但答案不能每次重新统计, 所以就再记录个 $ans$ 表示子树内所有方案的lca编号与权值的乘积的和即可. 这个题信息看看维护虚子树信息显然是免不了了.
CF1550F Jumping Around
注意到这个玩意是可以左右跳的, 所以不能用一些简单dp.
考虑维护当前连通块, 按 $k$ 递增的顺序处理, 显然不能去尝试新点.
考虑维护每个连通块 $v$ 表示最小的 $k$ 使得其能扩张. 问题变成如何确定合并两个连通块时新的 $v$. 根本不会.
停, 注意到起点固定的, 那就只需要维护一个连通块, 那反过来对每个点维护它距离当前连通块的最小 $k$.
直接考虑函数 $f(x)$ 表示位置 $x$ 距离当前连通块的最短距离 $-d$ 后的绝对值, 那么每次加入一个点相当于把一部分减等差数列, 然后要求最小的点, 这个可以ktt冲对吧
但是注意到每次凹下去的那个线斜率绝对值都是 $1$, 相当于取min, 所以每个直接维护每个位置被取min的直线的截距的最大最小值即可.
另一个方法是求Brovka求完全图MST, 可以支持 $s$ 不一样的.
重点就在于如何求与当前点距离最近的不在连通块里的点.
一个方法是, 按照连通块编号顺序扫点, 一个点的贡献是插入几条斜率绝对值为 $1$ 的直线, 用数据结构维护, 正反扫两遍就能排除档期那连通块了.
不知名典题.
给一棵 $n$ 点树, 定义 $f(l, r)$ 表示把编号在 $[l, r]$ 之间的点连通的最小边数, 求 $\sum_{l, r}f(l, r)$
$n\le 10^5$
考虑一条边有贡献当且仅当两边都有点, 于是统计只有一边有点的区间个数, 方式是维护子树内编号连续段并树上启发式合并, 在过程中计算即可.
启发式合并的时候如果用splay就优化到单log.
GYM102586A
$a$ 强制在线. $n, m\le 2\times 10^5$
qyc的题解:
QOJ #5098. 第一代图灵机
给定 $a_n, c_n$, $q$ 次操作, 每次单点改 $c$ 或者询问 $[l, r]$ 中没有重复颜色且数字和最大的子区间的数字和.
$n, q\le 2\times 10^5, a_i>0$
考虑没有重复颜色, 维护每个位置上一次/下一次出现的 $lst, nxt$, 则对于每个 $i$, 答案 $[l, r]$ 不能满足 $l<lst_i, r>i$.
把区间表示成点画到平面上, 每个 $i$ 排除了一个左上角的2-side矩形, 于是答案是一条左上方的包络线.
考虑要能带删除插入的维护包络线, 它就是后缀min, 使用类楼房重建线段树维护即可.
线段树部分, 对每个点维护其答案, $calc(u, k)$ 定义为在 $u$ 节点右边添加一个 $k$ 后, 它的答案和最右边的点, 算它的时候如果 $k$ 比右二子最小值小就递归到左儿子, 否则就合并维护好的 $calc(lson, rson_{min})$ 递归右边.
CF1712F Triameter
WJQ给的题
-不是, 我是说, 我们的目标是什么?
-去整点找直径问题.
你有一棵树, 树上的每条边权值都为 $1$. 现在有若干次询问, 每次询问一个整数 $x$, 并将叶子结点全部相连上权值为 $x$ 的边(操作不会保留). 问每次操作后图的直径是多少. 图的直径定义为 $\underset{ 1 \leq u < v \leq n }{ \max } d(u, v)$.
O(nq)
容易想到对每个点 $u$ 求出最近的叶子距离 $h_u$, 设深度为 $d_u$, 于是答案是 $\max_{u, v} \min (h_u+h_v+x, d_u+d_v-2d_{\mathrm{lca}(u, v)})$.
那么启发式合并双log爆炸, fingersearch启发式合并单log常数爆炸, 长链剖分直接过了.
另一个想法是, 考虑这是最大化最小值, 转化为判定题, 那么枚举 $u$, 判定 $h_v+x+h_u\ge mid$ 的 $v$ 中是否存在 $u\to v$ 距离不小于 $mid$. 然后继续转化, 满足第一个条件的 $v$ 是按 $h_v$ 排序后的一个后缀, 那么就成了问点到区间距离最大值, 众所周知直径可以 $O(1)$ 合并, 于是上个 $O(1)$ lca.
CF1303G Sum of Prefix Sums
前缀和的和不就是数组 $\sum_i ia_i$ 吗, 那么想到点分治, 对于当前根 $u$, 处理 $f_v$ 表示 $u$ 走到根路径上 $ia_i$, $g_v$ 表示根走到 $u$ 上 $ia_i$, $s_v$ 表示权值和, $l_v$ 表示距离, 那么 $x\to y$ 就是 $f_x+g_y+l_xs_y$, 看到两个相乘, 李超树优化即可. 复杂度 $n\log^2 n$
CF1446D2 Frequency Problem (Hard Version)
结论是, 这两个值中一定有一个是全局众数. 因为如果不是, 你一定可以扩展使得其与全局众数一样多.
于是只要求另一个数在区间中数量相等且最大, 发现最大是不必要的, 如果其中有另一个数比这个区间的全局众数和它都大, 那么全局众数就会和另一个数构成答案. 那么只要数量相等的话就很好做了吧, 对全局众数前缀和, 看到出现次数想根号分治, 大于根号的有根号个, 直接扫整个序列hash掉前缀和之差, 对于小于根号的, 枚举出现次数, 双指针看是否有另一个数达到这个次数, 每次加一个数删一个数可以用桶维护其出现次数并统计答案.
CF1316F Battalion Strength
容易想到把相邻贡献拿出来, 答案写成 $2^n \sum_{p_i<p_j}p_ip_j2^{-{s_i-s_j}}$ 的形式, 其中 $s$ 是排名. 然后再拆成 $(\sum_i p_i2^{-s_i})(\sum_{j<i} p_j2^{s_j})$, $j<i$ 怎么办, 考虑对值域分治, 那么现在就只要维护两边这两团式子的和, 写个值域线段树即可.
CF484E Sign on Fence
给定一个长度为 $n$ 的数列, 有 $m$ 次询问要你在区间 $[l, r]$ 内选一个长度为 $k$ 的区间, 求区间最小数的最大值
$n, m\le 10^5$
此时你应该想到二分, 把大于答案的数设为 $1$, 小于答案的数设为 $0$, 然后求区间最长连续段长度, 主席树以维护每个二分答案的值.
怎么这破ds都能降智啊.
CF997E Good Subsegments
给定排列 $p_n$, $q$ 次询问 $[l, r]$ 内满足值域连续的区间个数.
$n\le 1. 2\times 10^5$
首先肯定要把值域连续换一个不这么全局而只和少数数字相关的性质:
[trick] 值域连续等价于 $max-min=r-l$
这就好很多, 于是你开始扫描线答案区间的 $r$, 区间更新前面每个点的 $max-min+l$ 是简单的, 但是现在要求等于 $r$ 的个数? 哦你仔细想一下, 这是个排列, 保证了 $max-min\ge r-l$, 于是 $r\le max-min+l$, 就成了求最小值个数了, 要求历史和的话, 都可以写成矩阵, 复杂度1log.
P4688 [Ynoi2016] 掉进兔子洞
3s 1e5的数据结构有xxx, xxx和bitset(
考虑求被删掉的公共元素之和, 但这里元素出现次数取min不能直接bitset and, 离散化, 并且把值相同的元素 $a_1\ldots a_k$ 映射到 $p\ldots p+k-1$, 然后区间的bitset满足若这个值出现了 $x$ 次bitset上 $p\ldots p+x-1$ 的位置为 $1$, 这样直接与起来就是公共元素数了.
区间bitset提取上莫队是套路.
P3934 [Ynoi2016] 炸脖龙 I
根据扩展欧拉定理指数上是模 $\varphi(p)$ 做再可能需要加 $\varphi(p)$, 于是每递归一次 $p\to \varphi(p)$, 那么递归两次至少减半(偶数必定减半), 于是只会递归 $\log n$ 次每次暴力做就是对的.
P5355 [Ynoi2017] 由乃的玉米田
区间差, 和都可以bitset
区间乘积直接枚举因数
区间商考虑根号分治, 对大于根号的询问 $x$ 对每个 $a_i$ 只有 $\sqrt n$ 个可能的值和他对应直接处理, 对于小于根号的询问 $x$ 对每个 $p$ 预处理第一个 $l_p$ 表示左边第一个位置满足 $a_{l_p}$ 和 $a_p$ 的商是 $x$ 即可.
复杂度单根号加 $\dfrac{n^2}{w}$
P4692 [Ynoi2016] 谁的梦
跟数据结构没啥关系, 算贡献秒了, 就是对每个颜色分别算贡献, 单个颜色的贡献就是随便选减去不包含, 不包含用set维护出现位置即可单log.
P5062 [Ynoi2014] 在太阳西斜的这个世界里
P9000 [CEOI2022] Measures
小清新题.
每个人从 $0$ 时刻开始方向固定且走路时间是一个前缀, 所以看出点对贡献独立, 即答案为 $\max_{i, j} (i-j)*d-\vert p_i-p_j\vert$.
线段树即可.
P5064 [Ynoi2014] 等这场战争结束之后
可以离线显然操作树, 支持加边/撤销/查询连通块第 $k$ 大. 值域分块, 维护每块数的个数, 再按块维护链表存块内数, 时间空间都是 $n\sqrt n$, 容易想到的, 然后一看20MB.
打开题解, 块长40/fn
大概因为正解是bitset, 注意要 $\dfrac{n}{w}$ 分治, 少于这个的可以直接链表存起来.
P7983 [JRKSJ R3] practiceZ
颜色段均摊修改都可以变成区间加
对 $b$ 分块, 修改时如果我们维护了 $a$, 则对 $b$ 修改是区间加. 对 $a$ 修改时一块增加的值是 $\sum_i \sum_{j=l}^r [b_i\ge j]x$, 维护 $b$ 的值域桶, 就成了 $\sum_i c_i\min(r-l+1, i-l+1)x$ 的值, 只需要维护 $c_i$ 和 $ic_i$ 的前缀和吧.
然后下放标记直接暴力, 散块区间加是暴力, 散块询问也是暴力. 需要一个 $O(\sqrt n)-O(1)$ 区间加区间和的分块是简单的.
这题卡空间, 要逐块处理.
P6782 [Ynoi2008] rplexq
假设没有编号限制, 显然是 $siz_x^2-\sum_{i\in son(x)} siz_i^2$, 则满足条件下 $siz_x$ 如果单独算显然是个二维数点, 考虑对点度数根号分治, 小于的每个拆成 $\sqrt n$ 个询问, 二维数点平衡一下. 发现空间开不下, 不过对于一个 $x$ 询问的区间是连续递增的,
难点在于不能差分啊, 考虑直接对子树染色, dfs序提出来, 相当于询问区间不同数对数的典题, 莫队是 $\sqrt n n \sqrt m$ 爆炸, 爆炸在于所有这类点的儿子子树和是 $n\sqrt n$, 那如果每个都拿走前 $\sqrt n$ 大的按照上面做法跑, 分析复杂度, 就是分析 $\sqrt n$ 叉重链剖分的轻子树大小和, 显然是 $n\log_{\sqrt n} n=O(n)$ 的, 就做完了.
P7448 [Ynoi2007] rdiq
考虑拓展区间逆序对, 区间逆序对简单做法是二次离线莫队, 复习一下, 移动时要计算 $f(l, r, x)$, 差分成 $f(1, r, x)$ 和 $f(1, l, x)$, 其中形如 $f(1, r, r)$ 可以预处理, 形如 $(1, l, x)$ 的离线下来是 $n$ 个 $l$ 相同的 $x$ 的区间的和, 扫描线扫 $l$ 即可.
本质不同, $f(l, r, x)$ 就是和 $x$ 贡献的颜色数, 数颜色经典方法是考虑上次出现位置 $p$, 则若 $p$ 在 $l, r$ 外就查询 $f(l, r, x)$, 否则查询 $p, x$ 这个区间的贡献, 下标和值两维的4side矩形贡献不好做, 考虑离线, 扫掉一维, 差分一维, 变成 $n$ 次插入和 $n\sqrt m$ 次查询的单点插入矩形和问题.
然后上个trick: 单根号的在线二维数点, 先按大小 $n^{0. 75}\times n^{0. 75}$ 的矩形分块, $\sqrt n$ 块. 对一行($n\times n^{0. 75}$)按大小 $n^{0. 75}\times n^{0. 25}$ 的矩形分块, 是 $\sqrt n$ 个, 竖着同理. 再对剩下的 $n^{0. 5}\times n^{0. 5}$ 分块, 也是 $\sqrt n$ 块. 全都维护二维前缀和.
最后是散块, 枚举散块内的一维坐标去查对应另一维是否在范围内, 复杂度是单根号.
P6019 [Ynoi2010] Brodal queue
首先看到这个, 一打眼肯定是要求 $\sum_i c_i^2$, $c$ 为出现次数. 那么第二步肯定是差分掉, $\sum_i (s_{i, l}-s_{i, r})^2=\sum_i s_{i, l}^2 + \sum_i s_{i, r}^2 -2\sum_i s_{i, l}s_{i, r}$.
修改都先颜色段均摊, 也就变成一种颜色替换成另一种颜色. 分块的时候颜色段均摊好像和对只有一种颜色的块跳过做是等价的. 所以只有一个颜色的单独拿出来可以在询问的时候统计. 而现在问题就是维护整块的 $f_{l, r}=\sum_l s_{i, l}s_{i, r}$. 总的修改一块的次数是 $O(n)$ 的.
修改第 $x$ 块的值 $k$ 增加 $v$ 次, 本来 $v$ 在 $[1, l], [1, r]$ 的出现次数分别为 $a, b$, 则对 $l, r\ge x$, $f_{l, r}=g_{l, r}+(a+b)v+v^2$, 对 $l, r<x$ 没影响, 对 $l\ge x, r<x$, $g_{l, r}=g_{l, r}+bv$. 一次修改看起来要影响 $n$ 个值肯定不行, 考虑对 $l$ 相等的记录 $av+v^2$ 的贡献, 对 $r$ 相等的记录 $bv$ 的贡献, 只需要修改 $O(\sqrt n)$ 次, 用修改 $O(1)$ 查询 $O(\sqrt n)$ 的数据结构维护即可.
散块修改暴力重构, 散块询问暴力扫描.
P5063 [Ynoi2014] 置身天上之森
考虑一棵正常的线段树, 同层的区间长度只有两种. 长度相同的节点一定不交.
于是把每个长度的节点排序分别维护, 问题变成区间加, 区间小于一个数个数, 后面这个复杂度是众所周知的 $n\sqrt {n\log n}$ 的.
然后对每个的复杂度都是这个的话, 累加一下似乎是 $\sum_{i=0} \dfrac{n}{2^i} 2^i\sqrt {i2^i}=n\sum_i \sqrt {i2^i}$, 注意这玩意相邻两项做比显然小于 $1/2$, 拿等比数列放缩一下最大是 $n\sqrt {n\log n}$ 不变.
P5065 [Ynoi2014] 不归之人与望眼欲穿的人们
分块, 每块从端点向内只有 $\log n$ 个 or 和变化的位置, 询问的时候块间双指针 $\sqrt n\log n$ 个位置, 块内直接维护每个长度的答案, 单点修改时要重构一块, 复杂度是 $n\sqrt n\log V$
但是这题可以 $nPoly(\log n)$, 线段树, 每个区间维护从前往后, 从后往前的 $\log V$ 个位置, 然后组合出 $\log^2 V$ 个新区间记到这个节点上, 修改时暴力更新复杂度是 $n\log n\log^2 V$, 然后为了统计答案再对每个长度开一个可删堆, 再用线段树维护这些堆堆顶的值, 查询的时候在线段树上二分. 因为有堆所以是 $n\log^2 n\log^2 V$ 了.
还有神秘的三log做法.
P5066 [Ynoi2014] 人人本着正义之名
好像已经成套路了, 平衡树维护连续段移动.
P5067 [Ynoi2014] 长存不灭的过去、逐渐消逝的未来
对于没有括号的信息是容易合并的, 维护左右两边乘法连续段当前值, 除最左最右乘法连续段以外中间项的和即可.
考虑怎么合并信息, 对于一条分界线, 考虑跨过它匹配的若干对括号, 从深到浅依次合并, 也是能做的, 此时需要记录向左, 向右的未匹配括号位置去合并
正解是fhq treap直接维护表达式树.
tocheck
P5310 [Ynoi2011] 遥远的过去
字符串相等就是rank数组相等, 考虑对 $a$ 做滚动哈希, 平衡树/线段树维护一下, 你发现你怎么做完了.
P5311 [Ynoi2011] 成都七中
考虑用点分树维护联通块, 那么对于当前询问的点 $x$, 一定存在点分树上最浅的祖先 $y$ 满足 $y\to x$ 路径完全被 $[l, r]$ 包含, 则 $x$ 所在连通块被当前子树包含且包含根节点, 这样只要考虑处理分治中心的问题, 预处理每个点 $u$ 到 $y$ 路径上最大值 $mx_u$ 和最小值 $mn_u$, 则限制是二维数颜色, 那么对一个分治中心扫描 $r$, 维护每个颜色最右出现的位置即可.
复杂度是 $n\log^2 n$
P5312 [Ynoi2011] 竞赛实验班
考虑把数组分成有序部分和无序部分, 排序时把无序部分插入到有序部分就能保证复杂度, 无序部分用拆位线段树, 有序部分用01trie, 那么现在问题只有三操作可能改变有序部分的顺序, 发现若异或 $x$ 时 $x$ 第 $i$ 位是 $1$, 相当于翻转了在这一层的先后顺序, 只要记录一下有没有被翻转, 决定询问时往哪边走.
复杂度是 $n\log^2 V$
P5313 [Ynoi2011] WBLT
要求以 $b$ 为公差的等差数列长度, 注意值域不大.
考虑bitset, 则莫队提取区间bitset, 然后每 $b$ 个一块, 从前往后与起来直到没有 $0$ 了, 复杂度是 $\dfrac{qV}{b}+n\sqrt q$
则只要考虑 $b<w$ 的情况, 此时直接把 $b$ 的每个同余类开一个莫队, 仍然莫队提取区间bitset就做完了.
P5314 [Ynoi2011] ODT
看起来要单log啊, 然而并不是这样.
首先容易想到的做法是直接树剖, 开数据结构维护轻儿子支持单点加和查询kth, 是好做的. 复杂度是修改 $\log^2 n$ 查询 $\log n$ 的.
考虑优化, 每个点开 $b$ 个重儿子, 那么一个点到根的路径上最多有 $\log_{b+1}^n$ 个轻边, 于是复杂度是修改 $\log_{b+1}^n\log n=\dfrac{\log^2 n}{\log b}$, 查询 $b\log n$, 平衡一下.
P5524 [Ynoi2012] NOIP2015 充满了希望
如果只有赋值, 从大到小扫描 $l$, 维护每个查询操作的贡献, 在用线段树或ODT来找还没被赋值的查询操作, 查答案就是区间和.
发现从后往前扫的情况下, 交换两个位置的值就相当于在这两个位置上还没有被覆盖的查询操作换一下, 覆盖情况换一下, 就做完了.
P5525 [Ynoi2012] WC2016 充满了失望
容易发现一个圆满足条件当且仅当它完全在凸包内. 即圆心距离任意凸包的边距离大于 $r$, 那么把圆从小到大排序, 考虑凸包不断向内收缩(每条边向内平移 $r$), 发现可能会有两边的直线把中间的干掉的情况, 于是要算两边的把中间的干掉的时间点, 此时两边的直线的交点到三条直线相等, 即角平分线交点. 现在已经有某时刻凸壳形状, 要判定圆心是否在里面怎么做? 二分处对应线段即可.
可以用并查集维护边集支持删掉一个元素, 求前驱后继.
P5526 [Ynoi2012] 惊惶的 SCOI2016
考虑要算一个颜色贡献相当于算不经过该颜色点对数量, 那么直接删掉这些点, 维护连通块大小平方和. lct维护树大小, 问题是改一个点可能断度数条边, 不考虑常数的话可以三度化或拆点吧, 但题解区好像都是用的把点上移到边, 特殊处理连通块根的方法.
不过先想到的是另一个东西, 考虑一个dp, 相当于每个连通块可以选两个点, 于是, $f_{u, 1/2}$ 表示已经选了 $1/2$ 个点的方案数, 则 $f_{u, 1}=\sum_v f_{v, 1}+1$, $f_{u, 2}=\sum_v f_{v, 2}+2f_{x, 1}(1+\sum_{w\ne v} f_{w, 1})+\sum_{i\ne x}\sum_{j\ne i, j\ne x} f_{i, 1}f_{j, 1}$, 那么都可以矩阵转移.
于是离线询问, 枚举颜色 $c$, 拿出所有对颜色 $c$ 的修改算即可, 全局平衡二叉树复杂度 $(n+m)\log n$.
感觉全局平衡二叉树还是leafy的比较正常.
P5607 [Ynoi2013] 无力回天 NOI2017
std的差分再 $n\log n\log^2 V$ 线段树维护线性基感觉是板子
但是怎么有逆天俩log做法/xia todo
P5612 [Ynoi2013] Ynoi
考虑和 P5312 [Ynoi2011] 竞赛实验班 一样, 01trie维护有序段, 然后异或就是把若干层子树翻转, 记一下整体异或多少就行了吧.
P5609 [Ynoi2013] 对数据结构的爱
记 $x$ 经过 $[l, r]$ 出来的值为 $f_{l, r}(x)$
注意到若 $x>y$, 则经过相同区间 $x$ 一定不比 $y$ 减去更少的 $p$, 于是 $f_{l, r}(x)$ 是 $r-l+1$ 段分段一次函数, 形如 $x+sum_{l, r}-kp$.
那么问题就是如何合并两个这样的一次函数 $f(x)$ 和 $g(x)$, 从小到大枚举减去几个 $k$ 确定出这个分界点所在的 $f$ 的区间, 注意到 $x$ 增加 $p$ 最多多减一个 $p$, 于是就做完了.
复杂度是 $n\log n+m\log^2 n$(求值需要二分所在段)
P5611 [Ynoi2013] D2T2
如果没有空间限制, 考虑序列分块, 对一个块只有 $O(n)$ 种本质不同的 $L, R$ 区间, 那么维护 元素和 最大前缀/后缀和 和 块内答案.
块内答案怎么处理? 考虑在序列维分治, 那么现在已经算出 $[l, mid]$ 和 $[mid+1, r]$ 的各 $\dfrac{len^2}{4}$ 上面四个信息, 对于 $L, R$ 的答案只要在左右两个区间中找到最大的值域区间然后合并. 复杂度是 $T(n)=O(n^2)+2T(n/2)=O(n^2)$. 需要离散化端点.
散块是暴力.
现在卡空间, 只要维护这个询问的四个信息, 每次处理一块, 再把这块的信息合并上去即可.
P5399 [Ynoi2018] 駄作
先拍一个topcluster树分块, 则一个邻域会被拆成若干个块内的邻域, 其中除了只有一个不以界点为中心, 把贡献分成同一块内的和跨块的:
对同一块内的, 如果两个邻域中心都是界点可以预处理, 处理就是枚举一个深度分别为 $a<b$ 点对, 然后在 $(a, b)$ 处加上贡献, 再跑二维前缀和即可. 复杂度是 $n\sqrt n$. 如果有至少一个邻域中心不是界点, 这样的情况只有 $O(m)$ 次, 考虑对一个点集建虚树, 枚举另一个点集的点, 那么这个点到虚树上点的距离和是可以计算的. (每个点维护虚树上所有点到它的距离和子树里所有点到它的距离即可吧).
对不在同一块的, 考虑都需要先到自己的界点然后经过中间一段, 发现只要预处理界点邻域内所有点到界点距离和和点的个数, 设 $a$ 的答案分别为 $d_a, c_a$, 另一个界点的是 $d_b, c_b$, 那么答案是 $c_ad_b+c_bd_a+dis(a, b)c_ac_b$. 现在要一起算, 那么跑树形dp就行了.
复杂度是 $(n+m)\sqrt n$
P6106 [Ynoi2010] Self Adjusting Top Tree
问题显然是可以差分的, 先变成只有右边和上边的2side矩形询问.
只考虑斜率为正的线段, 则处理右边上边2side矩形时, 完全在矩形内的线段的贡献是二维数点.
其他的线段可以分成交于右边界或交于上边界, 然后分别扫描线即可. 特殊处理同时交于右上角的.
对于斜率为负的反过来再做一遍就好了.
P6108 [Ynoi2009] rprsvq
考虑方差的式子是
$$
\begin{gathered}
\dfrac{1}{n}\sum_i a_i^2-(\dfrac{\sum_i a_i}{n})^2
=\dfrac{n-1}{n^2}a_i^2-\dfrac{1}{n^2}\sum_{i\ne j}a_ia_j
\end{gathered}
$$
$$
\begin{gathered}
ans=\sum_S \dfrac{\vert S\vert-1}{\vert S\vert^2}\sum_{i\in S} a_i^2-\sum_S \dfrac{1}{\vert S\vert^2}\sum_{i, j\in S, i\ne j}a_ia_j\
=\sum_i a_i^2\sum_k \dfrac{k-1}{k^2}\binom{len-1}{k-1}+\sum_{i\ne j} a_ia_j\sum_k \binom{len-2}{k-2}\dfrac{1}{k^2}\
\because (k-1)\binom{len-1}{k-1}=(len-1)\binom{len-2}{k-2}\
\therefore ans=((len-1)\sum_i a_i^2+\sum_{i\ne j} a_ia_j)\sum_k \binom{len-2}{k-2}\dfrac{1}{k^2}
\end{gathered}
$$
现在只要能对每个 $n$ 求
$$
\sum_{k=0}^n \binom{n}{k}\dfrac{1}{(k+2)^2}
$$
考虑 $\sum_k \dfrac{1}{(k+2)^2}x^k=\dfrac{1}{x^2}\int\dfrac{1}{x}\int x\dfrac{1}{1-x}$ 怎么积不出来
直接NTT吧.
P6107 [Ynoi2010] Worst Case Top Tree
看到这个连边条件想到建出大根笛卡尔树, 发现连到往上走左边/右边第一个祖先, 相当于当前区间向左右扩展得到.
[conclusion] 完全想不到, 结论是, 树上任意四个点组成的连通块, 以及连通块的根向上连的点, 构成六元环.
对连通块分类讨论证明是容易的.
然后再考虑修改, 把一个数变大在笛卡尔树结构上相当于不断上旋直到它小于父亲, 发现一段连续的左右链只会改变 $O(1)$ 条边, 修改 $O(1)$ 的信息, 那么考虑左右链切换次数, 发现经过一段连续左右左右这样的切换后, 会把所有左链放在一边, 所有右链放在一边, 于是若一个切换所在的链的长度每次变成一半, 总切换次数是 $(n+q)\log n$ 的.
[trick] 结论: $n$ 个点的树, 每次把一个点上旋到一个位置, 经过左链/右链切换次数是 $(n+q)\log n$.
P6778 [Ynoi2009] rpdq
点分治, 则对每个分治中心求 $\sum_{i\ne j} s_i(tot-c_i)$, $s_i, c_i$ 表示子树 $i$ 在 $[l, r]$ 内点的深度和, 个数.
这么做肯定不行, 考虑点分治分块, 即点分树大小大于等于 $B$ 的子树分一块, 注意要三度化保证每个块大小在 $B\ldots 2B$ 之间.
每次询问块间可以用上面的方法枚举每一块算一个 $n$ 个点, $\dfrac{nq}{B}$ 次询问的二维数点, 块内直接枚举点对是 $\dfrac{n}{B} \cdot B^2$ 个点, $q$ 次询问的二维数点, 分别平衡一下就好了.
另一个做法是莫队, 二次离线后是 $n$ 次加点 $n\sqrt n$ 次查询当前集合内的所有点到一个点的距离, 考虑topcluster分块, 每个块维护这个块内的在集合内的点到所有其他簇的界点的距离, 到块内每个点的距离. 那么询问是 $O(1)$, 加入一个点时块内可以一遍换根dp块间暴力更新.
额, 其实这里有个经典转化, $\sum_{u\in S} dis(u, v)=\sum_{u\in S} dep_u+dep_v+\sum_{u\in S}-2dep_{lca(u, v)}$, 二后面这部分是经典的:
[trick] 将 $S$ 中的点到根的路径上加上父边边权, $u$ 到根的路径和即是 $\sum_{u\in S} dep_{lca(u, v)}$.
然后后面一样二次离线或点分治分块.
P4118 [Ynoi2018] 末日时在做什么? 有没有空? 可以来拯救吗?
序列分块, 考虑块间答案肯定是要前缀和max, 后缀和max, 块内总和, 设块被整体加了 $x$, 则前两个显然是 $x$ 的分段下凸一次函数, 要维护它们的凸包. 每次查询的时候在凸包上二分, 散块修改时分治再合并凸包, 复杂度是 $n\sqrt n\log n$. 现在要去掉 $\log n$
先考虑散块怎么办, 不能每次都重头建线段树. 被区间加后拆到 $\log n$ 个节点上, 那么往上合并这 $\log n$ 个节点复杂度是线性的, 这些节点上打上标记就行了.
然后查询的时候需要在凸包上二分, 考虑逐块处理, 则可以把相邻两个散块修改之间的部分拿出来离线, 使得每次只加正数, 这样指针单调移动复杂度就线性了. 这个排序要卡大常鸡排.
题解区好像维护的凸包下标是区间长度? 感觉维护加了多少能简单点?
P6779 [Ynoi2009] rla1rmdq
相当于一个序列每个位置时一个指针指向数上一个点, 每次让指针指向父亲或者查询深度最小值.
考虑序列分块, 对于一块的指针不断向上跳的过程中若存在某时刻两个指针有祖先关系则深的那个一定没用了, 那么也可以认为, 当一个指针在另一个指针曾经存在的位置时这个指针就没用了, 即树上每个点只会被指针覆盖一次, 那么做法就简单了, 每个块维护到现在还有用的指针, 维护所有点是否被经过的标记, 维护懒标记应该被加了多少, 维护这个块的答案. 区间修改时修改懒标记, 让有用的指针往上跳并更新答案, 标记经过的点然后可能从有用指针集合中删去一些.
散块修改/查询暴力下传懒标记(树剖即可, 每个点总共往上只会跳 $\log n$ 条重链复杂度正确), 然后暴力统计答案/重建.
为了卡空间逐块处理.
复杂度 $n\sqrt n$.
P6780 [Ynoi2009] pmrllcsrms
注意 $c$ 是固定的, 按照 $c$ 分块. 询问只有一块内和两块之间的.
对于一块内的直接就做完了. 对于两块之间的, 设左边块长 $i$ 的后缀和为 $l_i$, 右边块长 $i$ 的前缀和为 $r_i$, 就要求 $\max_{i+j\l. e c} l_i+r_j$.
考虑这个范围画到平面上是一个三角形内的区域, 那么分治, 拿出中间 $\dfrac{c}{2}\times \dfrac{c}{2}$ 的一个正方形, 会递归到两个小三角形. 因为有修改还多测对这个建线段树, 维护节点(三角形)范围内的答案其中 $s_l, s_r$ 的最大值即可合并.
修改一块时只影响前后两个块间和自己块内, 然后更新答案, 还需要拿个线段树维护全局答案. 复杂度 $m\log n$.
P6781 [Ynoi2008] rupq
容易想到括号匹配完了一定是剩下若干个右括号紧接着若干个左括号, 考虑如果没有 $3$ 操作就直接线段树, 维护每个节点左右括号部分分别信息, 合并的时候左边左部和右边右部不用变, 中间的一定是一边剩下了若干个, 也就是求线段树区间的左部/右部的一个后缀的信息, 递归下去即可.
复杂度是 $n\log n+m\log^2 n$.
P6783 [Ynoi2008] rrusq
扫描线扫右端点, 维护每个点最后一次被覆盖时间, 那么就是矩形内点赋值, 全局小于 $x$ 的数的权值和.
那么建KDT, 开一个 $O(1)-O(n^\epsilon)$ 单点改区间和分块维护覆盖时间为 $i$ 处的点的权值和, 矩形赋值时打标记并回收子树内所有标记, 可以在回收/打标记时去修改分块. 则标记一共打了 $n\sqrt n$ 个(KDT复杂度), 回收复杂度相同.
另一个考虑, 把点按 $x$ 排序分块, 块内按纵坐标排序, 散块重构整块操作用颜色段均摊, 那么一开始有 $O(n)$ 段, 每次操作增加 $O(\sqrt n)$ 段(散块), 操作次数是对的但是时间复杂度多log.
KDT那个东西可以认为实现了二维颜色段均摊吧.
P7124 [Ynoi2008] stcm
直接照着 换根重剖/长剖 的思路编.
考虑树剖, 有经典结论所有轻子树大小之和是 $n\log n$, 那么直接加入所有轻子树递归重儿子, 然后加入重儿子处理轻儿子, 则考虑缺一分治, 但这样复杂度是俩log. 但注意按照子树大小建哈夫曼树, 然后用缺一思路(进入一个子树的时候加入另一个子树的)复杂度就是单 $\log n$ 了.
但是重剖再建哈夫曼树就是静态toptree把rake tree建出来了吧.
P8511 [Ynoi Easy Round 2021] TEST_68
考虑全局最大值是 $a_x\operatorname{xor} a_y$, 则 $x, y$ 到根链上以外的点答案全都有了. 只要求两条链上的, 考虑对 $x$ 那条链的直接dfs+01trie, 每个点只被加一次, 就做完了.
P7126 [Ynoi2008] rdCcot
对于这种数某种条件连通块的题, 考虑构造有限信息, 我们钦定一个连通块里点的大小关系, 只数每个连通块中最小的点. 记对 $u$ 在这个大小关系中小于 $v$ 记为 $u<<v$.
我们希望若 $u\ \text{is connected with}\ v$, 则 $u\to v$ 可以只经过 $u<<w<<v$ 的 $w$. 这个目的是, 一个点是代表元 $u$ 只要求不存在 $v<<u$ 与 $u$ 连通. 等价于对 $u<<v<<w$, 若 $u\leftrightarrow w, v\leftrightarrow w$ 则 $u\leftrightarrow v$
这样对点 $u$ 找到 $l_u<u, l_u<<u, l_u\ \text{is connected with}\ u$ 和 $r_u<u, r_u<<u, r_u\ \text{is connected with}\ u$, 则只有包含 $u$ 不包含 $l_u, r_u$ 的点可以贡献, 简单数点.
考虑如何构造偏序信息, 发现 深度 是一个, 在深度相同的情况下任意偏序信息好像都行, 比如我们选择编号. 或者很难注意到直接把bfs序作为偏序信息也是对的.
然后就要看怎么求 $l_u, r_u$, 只考虑 $l_u$, 点分治, 对一个分治中心处理出每个点的距离 $d_u$, 按照点原树深度从小到大加点, 就要查 $d_u\le x$ 的编号前驱后继, 在平衡树上二分即可.
P7446 [Ynoi2007] rfplca
分块, 每次都是往前跳, 查询 $u, v$ 时那么从后往前枚举块, 查 $u, v$ 进入这个块时是否到了同一个点, 如果是那么找到 $u$ 上一次出现的块和 $v$ 上一次出现的块, 记这两个块里第一次出现位置分别是 $u’, v’$, 显然 $u’, v’$ 暴力跳是 $O(\sqrt n)$ 的.
要支持区间减, 查一个位置跳出这个块会到哪, 以及一个点跳一步到哪. 于是维护减法标记, 最后两个点暴力跳时只经过 $1$ 个块.
设 $i$ 跳出一个块时会到 $p_i$, 那么重构一块时从前往后扫一遍就能求, 区间减 $x$ 时, 设这块为 $[l, r]$: 对 $a_i<l$ 是 $p_i\gets p_i-x$, 对剩下的点我们不会做, 但注意到一个点最多减 $\sqrt n$ 次就变成第一类点, 所以如果存在剩下的点直接暴力重构复杂度就对的.
最后是 $n\sqrt n$
P7897 [Ynoi2006] spxmcq
这是区间最大子段和上树啊.
考虑一个点的答案凸包, 设 $f_u(x)$ 表示了 $u$ 子树内加 $x$ 后最大与 $u$ 连通的连通块权值, 则 $f_u(x)=val_u+x+\sum_{v\in son_u} \max(f_v(x), 0)$.
对 $f$ 的合并只需要支持加法(所有函数都是非负的不会有和 $0$ 取max), 维护差分即可吧.
或者维护 $f_u(x)$ 表示 $u$ 子树内大小为 $x$ 的连通块, 与 $u$ 连通的, 最大权值, $g$ 表示不要求连通的. $f_u$ 是 $(max, +)$ 卷积, 用平衡树维护差分是不是就行了.
复杂度 $O(n\log n)$
P7721 [Ynoi2007] rvrewsus
显然 $r(k)$ 是第 $k$ 小的数值(即相同的算一个).
信息在值域维可合并, 值域分块, 对每个块内分治, 注意长 $l$ 的根号, 设要算 $[l, r]$ 的 $O((r-l)^2)$ 个信息(有 $r-l+1$ 个点, 那么只有 $(r-l+1)^2$ 个本质不同区间), 那么递归算 $[l, mid]$ 和 $[mid+1, r]$ 的信息, 然后暴力合并, 复杂度就是 $O(n)$ 的. 总复杂度是 $n\sqrt n$.
然后因为有重复的数所以要处理一些细节, 比如要按照数的出现次数和分块, 有些数次数超过 $\sqrt n$ 的要拿出来单独做, 在递归 $[l, r]$ 的时候找不到好的 $mid$, 只能变成递归到 $[l, mid)$, $mid$, $(mid, r]$ 三部分同事保证两边部分都小于一半.
