复杂数据结构

复杂数据结构

一些巨大的数据结构题目

CF1336F Journey

题意：给定一棵树和 \(m\) 条链，求多少对链的交中包含的边 \(\geqslant k\)。

思路：首先对链交的情况进行分类。

第一种是 \(lca(x_1,y_1)\ne lca(x_2,y_2)\)，我们在深度较大的 \(lca\) 处统计答案，那么我们把一条链的贡献记在端点向 \(lca\) 跳 \(k\) 步的位置，将其子树加，统计答案时求两端的答案即可。

第二种是 \(lca(x_1,y_1)=lca(x_2,y_2)\) 且 \(dfn[x_1]<dfn[x_2]<dfn[y_1]<dfn[y_2]\)，那么就枚举 \(lca(x_1,x_2)=z\)，从 \(z\) 向 \(y_2\) 走 \(k\) 步，再统计答案，那么具体做法就是对于所有 \(lca=x\) 的 \((u,v)\)，建出 \(u\) 的虚树，把 \(v\) 挂在 \(u\) 上，同时维护 \(u\) 所在链，维护答案需要用线段树合并，维护链需要启发式合并。

第三种是 \(lca(x_1,y_1)=lca(x_2,y_2)\) 且 \(dfn[x_1]<dfn[y_1]<dfn[x_2]<dfn[y_2]\)，那么和第一种类似，它们的交一定是从 lca 往下 \(k\) 个，在 \(y_1\) 处子树加，在 \(x_2\) 向上走 \(k\) 步统计答案即可。

P5385 [Cnoi2019] 须臾幻境

题意：求一段区间内的边形成的连通块数。

牛逼题。对于求联通块数量，有一点小trick。

首先，如果在一棵树上断掉一些边，那么连通块是就是点数减边数。而转到图上，可以任取一颗生成树森林，此时的点数减去在生成树森林上的边数就是连通块数。

回到这道题，我们需要的是求出一段时间内存在于生成树森林上的边数，我们可以先顺序加边，用LCT实时维护生成树森林，即如果当前要加入的边的两端已经联通，就删掉路径上最早加入的边，用主席树存下每一条边存在的时间就可以了。

P4848 崂山白花蛇草水

题意：在线带插入矩形第 \(k\) 大。

思路：在线带插入矩形第k大，看起来就不可做，结果可以直接暴力，搞两个数组然后插入到小的数组里，如果大于\(\sqrt{n}\)就归并到大数组里，询问时顺次查就可以了。

P5356 [Ynoi2017] 由乃打扑克

题意：区间加，区间 kth。

思路：算分块维护kth的经典trick：维护每一块排好序后的数组，查询时在每一块上二分。可以做到 \(O(n\sqrt{n}\log n)\)。

P7963 [NOIP2021] 棋局

思路：终于来写棋局了。

其实思路不难，就对于每类边分别维护一下。

对于第一类边，可以直接维护；

对于第二类边，可以用并查集，然后维护一下段头、段尾。

对于第三类边，用线段树合并即可。

关于去重，第一类点的去重比较容易，第二类点的去重稍微有点麻烦，不过因为这一类点在横或纵坐边上是连续的，因此在线段树上是一个区间，这样也好处理。

然后就是吃子的问题。对于第一类边，比较容易。对于第二类边，会被吃的最多只有 4 个，可以直接判。对于第三类边，我们在维护线段树的同时维护一下与当前连通块相邻的棋子集合，然后查询就是一个前缀查询。

P8868 [NOIP2022] 比赛

题意：给出两个序列 \(a,b\)，每个区间的贡献是 \(a\) 序列中的最小值乘上 \(b\) 序列中的最大值，多次询问一个区间的所有子区间的权值和。

思路：以前以为是什么单调栈 + 线段树的神仙题，结果发现就是个用线段树暴力维护半群信息的题目。

先把询问离线下来，然后对 \(r\) 进行扫描线，维护当前所有 \(l\) 的答案。我们对 \(A,B\) 同时维护单调栈，这样对于两边都是一个区间覆盖，然后我们维护 \(S_{l,r}=\sum\limits_{r'=l}MaxA_{l,r'}\times MaxB_{l,r'}\)，这样的话查询就是区间和。

考虑怎么动态维护这个信息。我们发现标记其实就是区间覆盖和区间 \(+=X\times Y\) 的复合，那么我们可以维护 \(sx,sy\) 表示 \(x,y\) 的区间覆盖标记， \(a_x,a_y,a_{x,y},a\) 分别表示区间和会增加多少，这样就差不多了。

P9247 [集训队互测 2018] 完美的队列

题意：有 \(n\) 个队列，每个队列有长度 \(a_i\)，操作是往区间的每个队列中加入一个权值，求每个时刻队列中的权值种数。

思路：分块好题。

首先，可以转化成对于每一次 \(\text{push}\) 的操作，求出其最晚的被 \(\text{pop}\) 的时间。然后我们对序列分块。对于整块，我们用 \(\text{two\_pointers}\) 求出第 \(i\) 次操作后最早的时刻 \(j\) 满足 \((i,j]\) 中的操作可以让每个位置插入次数超过 \(a\)。对于散块，可以扫描线 + 树状数组上二分。块长取 \(\sqrt n\over \log n\) 时最优，复杂度是 \(m\sqrt{n}\log n\)。

P8360 [SNOI2022] 军队

题意：有两个数组 \(a,b\)，有给 \(a\) 区间赋值，给区间中所有 \(a_i=x\) 的位置在 \(b\) 序列中加 \(y\)，和查询 \(b\) 区间的区间和。

思路：考虑分块。

对于整块，可以考虑维护森林。初始颜色相同的点有相同的父节点，然后区间赋值操作就是合并这些颜色。

合并时，如果这个颜色块内没有，就需要新建一个点代表这个颜色，然后再合并。

对于区间加，在树上打标记即可。

对于散块，可以暴力下放标记，然后暴力维护操作和重构森林。

复杂度 \(O(n+q\sqrt{n})\)。

「JOISC 2016 Day 3」回转寿司

题意：给出一个有 N 个点的环，环上各点有一个初始权值 \(a_i\)。

给出 Q 个询问，每次询问给出一个区间 \([l,r]\) 和一个值 A ，对于 A 的变动定义如下（r 可能会小于 l 因为是环形）：

for (int i = l; i <= r; i++) if(a[i] > A) swap(a[i],A);

对于每个询问，回答遍历完区间 \([l,r]\) 后 A 的最终值。

思路：先考虑 \(l=1,r=n\) 的部分分。假如我们只进行一次操作，那么我们最后得到的 A 一定是 A 和序列最大值中较大的那个，如果 A 比序列的最大值要小那么 A 会加入序列中，最大值会出来。如果进行多次操作，我们发现在这个情况下我们并不需要知道序列最终是什么样，我们只用知道这个序列中元素组成的可重集，就可以求出每次操作后 A 会是什么，于是我们用堆来维护即可。

然后考虑拓展到一般的情况。我们此时的目的肯定是想办法尽量只关注序列的可重集，而题目的数据范围不大，时限却很大，不难想到分块。

我们将序列分块，每一块维护元素的可重集和每次会将对整个块进行操作的 A 有哪些。对于每次操作，整块可以直接把 A 加入可重集，然后把最大值弹出，这就是操作完的 A。

重点是散块如何处理。我们顺次考虑每个数，然后顺次考虑 A，如果当前的 \(a_i>A\)，这样 \(a_i\) 会变成 A，A 会变成 \(a_i\)，然后会继续找到下一个比 \(a_i\) 小的 A，继续进行下去。不难发现，\(a_i\) 最终会变成 A 中最小值和 \(a_i\) 中较小的那个，如果 \(a_i\) 比 A 中最小的数还大就会和这个数交换。

设块长为 B，那么我们一次修改整块的复杂度是 \(O(\dfrac{n}{B}\log n)\)，散块的复杂度是 \(O(B\log n)\)，于是总复杂度就是 \(O(Q\sqrt{n}\log n+n\log n)\)。

P6109 [Ynoi2009] rprmq1

题意：有一个 \(n \times n\) 的矩阵 \(a\)，初始全是 \(0\)，有 \(m\) 次修改操作和 \(q\) 次查询操作，先进行所有修改操作，然后进行所有查询操作。

一次修改操作会给出 \(l_1,l_2,r_1,r_2,x\)，代表把所有满足 \(l_1 \le i \le r_1\) 且 \(l_2 \le j \le r_2\) 的 \(a_{i,j}\) 元素加上一个值 \(x\)。

一次查询操作会给出 \(l_1,l_2,r_1,r_2\)，代表查询所有满足 \(l_1 \le i \le r_1\) 且 \(l_2 \le j \le r_2\) 的 \(a_{i,j}\) 元素的最大值。

思路：因为是先加再询问，可以想到离线处理。那么可以想到枚举查询的左端点，然后扫描线，把加操作差分一下，那么就变成了求区间历史最值，这样做是 \(O((n^2+q)\log n)\)。

我们来分析一下这样做的实质。我们做的是加入 \([1,l)\) 的操作，不维护历史最值，然后加入 \([l,r]\) 的操作，维护历史最值，于是可以考虑用分治优化。

这里我们用猫树分治，因为这样只用把一个区间拆成 2 个而不是 log 个。处理区间 \([l,r]\) 时，我们先加入 \([l,mid]\) 的操作，然后打清空历史最值的标记，然后处理 \([r,mid]\) 的操作和询问，处理完后回退到打标记的状态，递归处理右子树，然后再处理 \([l,mid]\) 的操作和询问，最后递归左子树。

复杂度 \(O(n\log^2n+q\log n)\)。