Virtual PTS 2020 Day 1 总结

``` --- layout: post title: Virtual PTS 2020 Day 1 总结 date: 2020-06-15 updated: 2020-06-15 katex: true categories: 总结 tags: [总结, Virtual PTS, 数据结构, 计数] --- ``` 如题，PTS = **P**rovincial **T**eam **S**election。 这套题总体难度较高，~~出到省选很容易就 GG~~。 ### [教科书般的亵渎](http://csp.ac/problem/173) 题意：有一个初始为空的序列，进行 $Q$ 次操作：在当前的第 $y$ 个元素后插入一个正整数 $x$；或者给出一个区间，求区间 $\operatorname{mex}$（这个 $\operatorname{mex}$ 与通常的定义不同，求的是最小的没有出现的**正整数**）。 由于这些元素的位置不固定，难以用数据结构维护，因此最好能先确定每个元素最终的位置（称为“绝对位置”），并把所有操作的位置参数都改为绝对位置。 如何实现呢？在线做上面的事并不容易，如果能离线就方便多了。 先把插入的所有的元素（的位置）都插入到平衡树中，再倒序处理操作，对最后一个操作，假设它插入到的位置是“第 $t$ 个元素之后”，那么就找出第 $t+1$ 小的位置，就是它的绝对位置；做完之后把这个绝对位置从平衡树中删除即可。 由于只需要进行插入、删除和查询第 $k$ 大，且值域很小，因此可以用树状数组实现平衡树。 找出了绝对位置，使用 `set` 暴力查找的方法也自然不难实现了。值得一提的是，由于这题的数据很弱，因此使用 `vector` 暴力查找就可以通过本题；也即， `vector<int>::insert(vector<int>::lower_bound(...),x)` 在随机数据上的表现还是很不错的。 标算用到整体二分，这里不进行叙述，只描述一个部分分的做法——先进行所有修改操作再进行查询操作。 这个部分分就相当于查询区间 $\operatorname{mex}$，有以下两种离线做法（如果愿意，也可以把线段树改成可持久化线段树做到在线）。 1. 莫队 这个问题与区间数颜色有些许相似之处，因此可以用莫队维护。 在端点移动时维护每个数的出现次数，那么到了查询时应该怎么办呢？难道要一个一个找吗？这样的复杂度并不正确。 一种可能的做法是用线段树维护每个数的出现次数，查询时在线段树上找最小的没有出现的数；但区间端点移动的次数是 $\mathrm{O}(n\sqrt{n})$，而查询的次数只有 $\mathrm{O}(m)$，二者极不平衡；让端点移动和查询的附属复杂度相同就显得不明智了。 这时我们可以用分块来“移动复杂度平衡”，让平衡朝着加快端点移动速度的方向移动。具体地说，把值域分成 $\sqrt{n}$ 个块，每个块维护“这个块有几个数出现”，这样端点移动的时间就是 $\mathrm{O}(1)$；查询时先找到第一个没有到齐的块，再在块中找 $\operatorname{mex}$，时间复杂度 $\mathrm{O}(\sqrt{n})$。这样就实现了两个操作的复杂度平衡，总复杂度 $\mathrm{O}((n+m)\sqrt{n})$。 如果把莫队改成带修莫队，还可以完成带修改的部分。 2. 线段树 我们把操作用另一种方式离线，右端点从左到右排序。当查询的右端点右移时把新的数加入，那么某个数在区间中出现就等价于它最后一次出现的位置不小于区间的左端点。于是我们可以用线段树维护每个数最后一次出现的位置，查询时在线段树上找第一个小于 $l$ 的数即可。 ### [有向无环图](http://csp.ac/problem/174) 题意：有一张 $n$ 个点 $m$ 条边的 $\mathrm{DAG}$，每个点有一个点权，初始时都为 $0$。需要支持 $q$ 次如下操作： 1. 给出 $u,x$，把 $\mathrm{DAG}$ 上点 $u$ 能到达的所有点的点权设为 $x$。 2. 给出 $u,x$，把 $\mathrm{DAG}$ 上点 $u$ 能到达的所有点的点权对 $x$ 取 $\min$。 3. 给出 $u$，询问点 $u$ 的点权。 $1\le n,m,q \le 10^5$。 也没有什么特别的思路，就是暴力。 注意多次遍历的时候可以用时间戳标记 `visited`，也就是 `visited` 中存储“第几次遍历”；这个技巧在需要多次 dfs 的题目中很常用。 ### [小水题](http://csp.ac/problem/175) 给出一棵 $n\ (1\le n\le 10^5)$ 个点的树，树上每个点的度数不超过 $500$；要进行 $q\ (1\le q\le 10^5)$ 次查询。 每次查询给定两个点 $u,v\ (u\neq v)$、一个正整数 $k\ (1\le k\le 500)$ 和一个参数 $\alpha\ (\alpha\in \{0,1\})$。求选出 $k$ 条树上路径的方案数（$x\to y$ 和 $y\to x$ 算同一条路径）。若 $k=1$，则要求 $u\to v$ 是选出的路径的子路径；若 $k\ge 2$，则要求选出的路径中，任意（不同的）两条路径的交集都**等于** $u\to v$。另外，若 $\alpha=1$，那么这 $k$ 条路径的端点均不重复。 这道题看上去要求繁多，比较复杂；实际计数上并不是十分困难，但在排列时要多加注意。 另外有一个小细节：如果每个点的预处理时间复杂度是 $\mathrm{O}(d^2)$，那么总的复杂度最坏可以达到 $\mathrm{O}(n^2)$，最坏情况是菊花图。当然，最好时间复杂度是 $O(n)$，因为根据柯西不等式，$(d_1^2+d_2^2+\cdots+d_n^2)(1^2+1^2+\cdots+1^2)\ge (d_1+d_2+\cdots+d_n)^2$，也就是 $\sum_{i=1}^{n}d_i^2\ge \dfrac{4n^2}{n}=4n$。顺便说一句，这个式子在数学竞赛的图论证明中有可能用到。 但这道题有最大度数限制，因此复杂度不会超过 $\mathrm{O}(500n)$。证明如下： 设度数为 $a_1$ 的点有 $b_1$ 个，度数为 $a_2$ 的点有 $b_2$ 个，一直到度数为 $a_t$ 的点有 $b_t$ 个，且 $a_1<a_2<\cdots<a_t$，那么总计算量为 $a_1^2b_1+a_2^2b_2+\cdots+a_t^2b_t$。根据度数的性质，我们有 $a_1b_1+a_2b_2+\cdots+a_tb_t=2n$。 于是可设 $c_k=a_kb_k$，那么总计算量为 $a_1c_1+a_2c_2+\cdots+a_tc_t$，且 $c_1+c_2+\cdots+c_t=2n$。这时可以容易看出 $a_1c_1+a_2c_2+\cdots+a_tc_t<a_tc_1+a_tc_2+\cdots+a_tc_t=2na_t$；由于 $a_t\le 500$，因此复杂度不会超过 $\mathrm{O}(500n)$。