数据结构综合选做

高妙分块都塞进分块选做了

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

扫描线是肯定的, 考虑扫描 $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)$ 的. 不能用线段树的结构因为结构不对应.

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

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

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

picture 2

picture 1

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$.

线段树即可.