Ynoi2016 题解

· · 个人记录

D1T1：https://www.luogu.com.cn/problem/P4688

等价于求三个区间的交，看着非常不可做，考虑bitset奇技淫巧。

这种情况我们一般怎么做？一般来说是维护一个cnt数组，维护当前区间的每种颜色的个数，但这个要做的是对每个 i 取 \min，没法bitset优化，怎么办呢？不难发现 \sum cnt_i 是 O(n) 的，所以我们可以用一个 01 字符串来表示状态，前缀 1 的个数就是 cnt_i。此时把所有位压在一起还是 O(n) 的。就可以用维护这个了。

--- D1T2：https://www.luogu.com.cn/problem/P4689 经典转dfs序，经典根号分治。 设以 $p$ 为分治点。 出现次数 $\geq p$ 的数：对每个数预处理一个出现次数前缀和，查询时直接 $O(1)$ 查询。总复杂度 $O(\dfrac{n}{p}\times n)$ 预处理加上 $O(mp)$ 查询。 出现次数 $< p$ 的数：暴力考虑每一对点权相等的数的贡献，不难发现只有 $O(np)$ 对数，问题转为二维平面上插入 $O(np)$ 个点，做 $m$ 次二位数点。考虑扫描线+根号平衡，复杂度 $np+m\sqrt{n}$。 取 $p=\sqrt{n}$，复杂度 $(n+m)\sqrt{n}$，可以接受。 --- D1T3：https://www.luogu.com.cn/problem/P4690 先考虑不带修怎么做，令 $pre_i$ 表示 $i$ 之前最靠近 $i$ 的与 $i$ 权值相等的数。答案可以转为二位数点查询 $i\in[l,r],pre_i\in[1,l-1]$ 的点数。 单点修改也很容易，$pre_i$ 的更改次数是 $O(1)$ 的，暴力修改树套树维护即可。 加上区间修改，推平这个操作很微妙，考虑颜色段均摊。不难发现均摊后 $pre_i$ 的总修改次数依然是 $O(n+m)$ 的，所以继续沿用单点修改的方法即可。 --- D2T1：https://www.luogu.com.cn/problem/P3934 根据扩展欧拉定理，查询时只有前 $O(\log V)$ 个数是有用的，暴力维护即可。 --- D2T2：https://www.luogu.com.cn/problem/P4692 对每种颜色算贡献，正着算不好算，考虑求补集。 然后你发现补集非常好算，序列间可以直接用乘法原理，序列内部也只和相邻两个同色点之间的距离有关、、 带修依然naive，拿个set维护一下每种颜色出现位置，再用 $w_{i,j}$ 表示第 $i$ 个序列中颜色 $j$ 对补集的贡献，不难发现 $w_{i,j}$ 不为 $0$ 的一共只有 $\sum c_i$ 个，map维护一下即可。 --- D2T3：https://www.luogu.com.cn/problem/P4693 不会做，呜呜呜。 呜？ 呜！