Ynoi 做题记录

原来我逻辑也这么差！！！数据结构能说什么呢。。细节自己多想想。

$Ynoi2011-$竞赛实验班/$loj517-$计算几何瞎暴力

不真的全局异或，而是：

• 加入新值，异或上当前 xor 和，丢到等待队列里；
• 排序时把等待队列的值都插到 Trie 里；
• 异或就异或到当前 xor 和上；
• 查询如果涉及到一部分有序一部分无序，就是全局和；否则如果全有序，Trie 上考虑「上次全有序时的 xor 和」下的前 k 项，差分。

维护每个子树各位出现次数和。

坑点：查询，在 Trie 上走的时候按「上次全有序时的 xor 和」，但查子树各位的时候按「当前 xor 和」来。

其实如果你考虑清楚了，这题一点都不坑，甚至还比较小清新。

$Code$

五彩斑斓的世界

离线询问，对每个块单独做。这样空间就不会炸。

对下标开并查集，权值相同的并一块儿；开一个数组记录每种权值的根的位置。

散块，不支持全局打标记，就暴力改，并趁机重构，清空 $tag$。

整块：

• $maxn \leq 2x$：暴力改所有 $> x$ 的，用 $O(\alpha * (maxn - x))$ 的代价让最大值减少了 $maxn - x$
• $maxn > 2x$：可以看作整体减少 $x$ 再给 $\leq 0$ 的加上 $x$，用 $O(\alpha * x)$ 的代价让最大值减少了 $x$

值域与 $n$ 同阶，单块的复杂度是 $O(n)$ 的，总体 $O(n \sqrt{n} * \alpha)$。

镜中的昆虫

区间数颜色的标准套路：$pre_i$ 表示 $i$ 前一个和 $i$ 颜色相同的位置，那么询问 $[L, R]$ 就是在统计 $pre_i < L$ 的个数。静态就是二维数点。

单点修改怎么做？$pre$ 总修改次数只有 $O(n + m)$，是个带修改二维数点问题。树状数组套线段树可以做，空间也不是很紧。 仅能过 loj 的数据！！ಥ_ಥ

如果加一维时间，看作在每个时间点做完左边的所有修改后查询，就可以 cdq 分治了，每次统计 $[l, mid]$ 的修改对 $(mid, r]$ 的询问的贡献。

区间修改呢？把相同颜色看成一块，考虑均摊分析，如果修改区间不相交显然 $pre$ 的总修改次数是 $O(n)$，如果相交也只会改端点 $O(1)$，总的是 $O(n + 2m)$

为了计算出所有实际的修改，需要开一个 set 维护所有块、颜色数个 set 维护该颜色的块, $O((n + 2m) logn)$

loj-Code

cdq 的不想写了。。下次一定

未来日记

因为这是 Ynoi，值域 $1e5$ 必有其用意。

二分啊主席树的没法和分块有机结合。所以要序列分块套值域分块（

$cnt1_{i, j}$ 表示序列前 $i$ 块在值域第 $j$ 块里出现的次数，$cnt2_{i, j}$ 表示序列前 $i$ 块第 $j$ 个数出现的次数。查询 $kth$ 就先扫值域块确定块，再挨个儿扫过去。

修改呢？散块暴力。整块怎么做？

注意到修改不会增加每块内的颜色种类。这超有用。

块内 $x$、$y$ 同时有的就暴力改，颜色种类减少 $O(n)$ 次，总复杂度 $O(n\sqrt{n})$；否则并查集即可。

这题唯一打标记的就是整块的并查集，而只要在散块重构的时候下推就好了。所以还比较清真？我是超级受不了巨大多 tag 的题 /kk

为了方便在下推的时候快速得到所有的真实颜色，还要记录每个根对应的真实颜色是什么。

$id_{x, c}$ 表示块 $x$ 内颜色 $c$ 的根，$rid_{x, d}$ 表示块 $x$ 内根 $d$ 对应的颜色，$pos_i$ 记录第 $i$ 个位置上的颜色对应的根。把颜色 $y$ 的根指向颜色 $x$ 的根，并清空颜色 $x$ 的根即可。本质是个离散化。

$Code$