数据结构综合选做

高妙分块都塞进分块选做

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神秘数 [主席树] [复杂度]

若当前可表示的值域为 [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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
for (int i = 1; i <= n; i++) {
int v = a[i]; //a是原数组
vector<int> vec; //vec是我们单独拿出来的21个数的位置
int up = 0, down = 0; //上下两个连续段的延伸长度

if (v == a[i - 1]) { //对于相邻两个值相等的特殊处理,否则按照我的垃圾写法会把一个值加两遍
bs[1].add(i, 1); //bs是答案树状数组,bs[i]表示连续段长i的左端点出现次数数据结构
bs[1].add(i + 1, -1);
goto query;
}

memset(vis, 0, sizeof(vis)); //vis是这个值是否有值
for (int j = max(v - 11, 0); j <= v + 11; j++) { //对于x+10,x-10更新的时候会碰到的边界条件,所以加上11
if (lastpos[j] && lastpos[j] > lastpos[v]) { //lastpos是一个值的上次出现位置
vec.push_back(lastpos[j]);
}
}
//乱七八糟边界条件
vec.push_back(max(0, lastpos[v])); //标定了待更新左端点区间的左端点(好绕啊,就是从左往右第一个要更新的左端点)
vec.push_back(i); //要先把自己插入进去,相当于修改以i为左端点的答案
sort(vec.begin(), vec.end(), greater<int>());
for (int k = 0; k < vec.size() - 1; k++) {
int j = vec[k], jv = a[j];
vis[jv - v + C] = true; //C是一个偏移,避免下标负数
for (; vis[up + C + 1]; up++)
;
for (; vis[-down + C - 1]; down++)
;
int len = up + down + 1;

int ml = vec[k + 1] + 1, mr = j; //当前这个值的出现情况是对于区间在[ml,mr]中的左端点的

//注意长度区间不在1-10的不用管
if (up >= 1 && up <= 10)
del(ml, mr, up); //这个辅助函数就是bs[up]的区间删除
if (down >= 1 && down <= 10)
del(ml, mr, down);
if (len >= 1 && len <= 10) {
bs[len].add(ml, 1);
bs[len].add(mr + 1, -1);
}
}

query:
for (Q q : queries[i]) {
query(q.l, q.id);
}
lastpos[a[i]] = i;
}

P5354 [Ynoi2017] 由乃的 OJ

大家肯定都做过那个经典的序列上全局的版本, 那么对于这个题可以相同方式考虑.

由那个题我们知道位运算每一位是独立的, 只要从高位往低位看每一位能不能是1就行了.

首先考虑序列上的区间询问, 那么容易发现可以简单线段树维护, 每个点记录在每一位1进去出来什么和0进去出来什么.

然后搬到树上可以合并方式不变的变成LCT和树剖, 此时要注意要记录两个方向(到序列上就是从左往右和从右往左)走的进出映射, 因为一条链又有向上的又有向下的.

然后被卡常了, 需要用位运算优化, 可以把每一位进去1出来什么这种压成一个int, 直接位运算, 然后就能过了.

由于合并操作比较复杂且询问的时候也要用这种合并操作, 一般就把线段树存的数据写成结构体了. 这里只放合并信息的关键代码:

1
2
3
4
5
6
7
8
9
//Dat是记录的信息,zero,one,rzero,rone每一位分别表示这一位正着走一开始是0,正着走一开始是1,反着走一开始是0,反着走一开始是1四种情况.
Dat merge(const Dat& a, const Dat& b) {
Dat ans;
ans.zero = (a.zero & b.one) | ((~a.zero) & b.zero);
ans.one = (a.one & b.one) | ((~a.one) & b.zero);
ans.rzero = (b.rzero & a.rone) | ((~b.rzero) & a.rzero);
ans.rone = (b.rone & a.rone) | ((~b.rone) & a.rzero);
return ans;
}

树剖查询的时候注意分清向上向下的细节.

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 ∣V∣, \sum∣E∣\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题, 一直没记录.

扫描线是肯定的, 考虑扫描 $x$ , 线段树维护一条竖线.

那么我们会若干次添加一个颜色, 在扫描线上相当于区间赋值, 但显然这里下传标记是不可能的. 甚至没法上传.

考虑标记永久化, 每个节点开一个set存所有完整覆盖自己的颜色, 因为上下传我们都做不到, 所以此时一个颜色被看到的条件是存在一个从根到叶子的路径其所有set中的最大值是这个颜色. 那么可以维护每个节点向下到根的路径中最大值的最小值 $mind$ .

此时如果所有矩形在 $x$ 轴上都是一个后缀我们已经会做了, 只要每次区间修改看是否能被看到即可. 但问题是有可能一个颜色在横轴上结束的比较早, 露出了本来看不见的, 考虑该怎么处理.

我们考虑set里只存没被统计过答案的, 那么 $mind$ 就成了子树中已经看到过的最小值.

暴力回收下放的标记是不现实的, 考虑只有在这个颜色没了之后露出一个新颜色的情况是有用的, 且假设其在多个区间分别露出同一个颜色只需要取一次. 于是维护每个节点子树中未被看到的颜色且大于对应 $mind$ 中的最大值, 就能知道是否有可能获得新的颜色, 然后查一下全局是否能获得新颜色, 如果能就把这个颜色加入考虑, 再暴力回收这个颜色的所有标记(一个颜色的标记只有 $\log$ 个), 重算这些节点的信息即可.

因为套了个set所以最后复杂度是 $O(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)$ 的, 如果我们用线段树代替st表结构就可以到修改 $q\log n \alpha(n)$ , 查询 $n\alpha (n)$ 吧.

能优化的本质是我们本来连了一个稠密图, 现在从顶上一层一层向下的过程中我们保证了每次都仅连最少的边. 于是每一层的复杂度贡献都是线性的.

顺手写一发, 发现我像个智障. 码力没了.

ABC238G

给定一个序列 $a_n$ , $q$ 次判断一个区间的乘积是否是完全立方数.

忘了数据范围所以福建OI

降智题, 和qyc一起降大智.

每个数拆成小于 $V^{\frac{1}{3}}$ 的质因数和一个质数, 那么小的直接前缀和, 大的莫队, 就是根号的.

然后发现我们是智障, 它相当于判断两个前缀的所有质因数次数膜3相同, 直接hash///fn复杂度是 $n\log v$ 的.

然后可以进一步再分治, 小于 $\dfrac{\log v}{\log \log v}$ 的前缀和, 剩下的用上面的hash, 复杂度就是 $n\dfrac{\log v}{\log \log v}+q\dfrac{\log v}{\log v\log v}$

然后你想了想, 你这个实际上是分析了不同质因数的个数, 所以原来复杂度就是这个.

我们是智障! ///fn

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$

第一眼看成在内向基环树森林上做这个问题///fn, 好吧其实是一堆环.

那么第三个操作会把环断开或合并, 稍微考虑一下发现断开和合并是十分”自由”的, 也就是说找不到多大性质.

$8s$ 提醒我们根号复杂度.

于是通过根号分治, 序列分块与一堆平衡树可以想到各种根号log.

考虑假设没有对环的修改, 你直接时间分块, 那么可以直接维护所有环, 加就直接加到环上, 区间和可以直接遍历被加的所有环去算对这个区间的贡献, 每根号个重构. 那现在有了对环的修改, 考虑在根号个修改的情况下, 你只切了根号刀, 所以实际上可以看成一共只有根号个点集, 那么加就直接遍历环包含的每个点集加, 询问考虑被加的每个点集的贡献, 这里不需要二分, 而是直接处理出每个数在这个块里被询问分成的根号段中的哪一段, 那么直接对每个环前缀和即可. 最后复杂度单根号.

我们糊出了不用时间分块的做法!

考虑根号分治, 那么在没有3操作的情况下, 小块加法直接暴力加到序列上, 大块加法把标记打在大块上, 那么查询的时候就查询序列上的和, 遍历每一个大环, 就行了.

现在有了合并/分裂, 仍然根号分治, 考虑对于一个大环, 维护的结构是一个块状链表, 链表上每一块维护其在原序列上的每一块的元素个数, 及其前缀和. 于是考虑:

  • 查询
    • 分成整块和散块
      • 整块部分和遍历每一个大环的块状链表上的每一块, 就能 $O(1)$ 查询这一块其对序列上整块的和的贡献
      • 散块部分若属于某个大环, 就直接查每个位置所属的大环的那个块的加法标记.
  • 加法
    • 大环: 遍历大环上的每一块, 打加法标记, 复杂度根号
    • 小环: 暴力加到序列上
  • 合并
    • 就是把两个块状链表接起来, 可能会合并块状链表上的两块, 合并是根号的.
  • 拆分
    • 把一个块状链表拆成两个, 可能会把大块中间劈开.

合并拆分都是块状链表经典操作, 不再赘述.

注意复杂度分析的时候, 块状链表的块的总个数是根号的, 因为一个大环的块状链表上小于根号的块左右必然都是大于根号的, 而小环我们不开块状链表. 所以复杂度正确.

CF某题

给定 $a_n$ , $q$ 次询问区间 $l, r$ 中是否所有数都出现 $k$ 的倍数次.

$n, q\le 3\times 10^5$

直接hash, 对于每个数进行一个随机映射, 那么如果这个区间的和不是 $k$ 的倍数就说明不是, 是的话发现有 $\dfrac{1}{k}$ 的概率错, 所以跑30遍. 复杂度2log.

然后有一些我们想的离奇做法.

对数的出现次数根号分治, 多于 $\sqrt n$ 的部分每个开一个BIT直接查询, 小于的对 $k$ 根号分治, 考虑 $k, n$ 都小于 $\sqrt n$ 的部分. 给每个 $k$ 开一个BIT存满足条件的所有数, 那么修改一次会影响这个小于根号的数的所有因数的位置, 于是是根号以内的因数个数, 对它们暴力修改即可. 大于根号的部分是 $q$ 次修改, $q\sqrt n$ 次查询, 小于的部分是 $q$ 次查询, $qd(\sqrt n)$ 次修改, 所以分别给一个根号平衡的序列分块就行了.

$k$ 大 $n$ 小的部分, 大于的可能的出现次数只有 $\sqrt n$ 种? 不对, 考虑不仅要满足出现次数是一个大于 $\sqrt n$ 的数的倍数, 还要满足它们的等差数列求和是 $n$ , 所以只有四次根号种, 那么你遍历一遍, 只对有值的用BIT查, 复杂度应该是 $\sqrt n+\sqrt[4] n \log n$ .

平衡不动了, 这个就是根号log的垃圾.

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编号与权值的乘积的和即可. 这个题信息看看维护虚子树信息显然是免不了了.

欸, 这是哪的题? 为什么是dp? 发现是打错题号进来的, 应该是482C///kx