Ynoi 2014-2015 做题记录
在太阳西斜的这个世界里，
置身天上之森。
等这场战争结束之后，
不归之人与望眼欲穿的众人，
人人本着正义之名，
长存不灭的过去、逐渐消逝的未来。
我回来了，
纵使日薄西山，
即便看不到未来，
此时此刻的光辉，
盼君勿忘。
————世界上最幸福的女孩
P5064 [Ynoi2014] 等这场战争结束之后
简要题意
双倍经验：LOJ 519 给定一个 $n$ 个点的无向图，点有点权，最开始没有边，需要进行以下操作 $m$ 次：
- 在 $x$ 和 $y$ 之间加一条边。
- 撤回到第 $x$ 次操作之后的状态。
- 询问在 $x$ 所在连通块中第 $k$ 小的点权。
$1\le n,m\le 10^5,1\le a_i\le10^9$。
时间限制：$\bf{500ms}$，内存限制：$\bf{20MB}$。 LOJ 上时空限制略宽。
解法
线段树合并应该不能可持久化，因为线段树合并复杂度是均摊的。
值域分块
不考虑内存限制，进行值域分块。强行将点权离散化成一个长为 $n$ 的排列，在相等时也要钦定一个顺序，这样离散化完每个值都唯一对应一个点。在值域上每 $B$ 个分为一块，使用并查集维护联通性，在并查集的根上开一个 $O(\dfrac nB)$ 的数组，记录在每一块内的数在当前连通块内分别出现的次数。合并时将两个根上的数组对应位置相加。查询时从小到大枚举每个块，即可确定 $k$ 出现在的块。然后枚举这个块内所有数，判断这个数对应的点是否和查询的点在同一联通块内，容易求出第 $k$ 小所对应的点权。现在考虑回退版本。离线所有操作，将一个操作与依赖的版本之间连边，能构成一棵树，称之为操作树。在操作树上进行 dfs，进入一个点的时候执行对应位置的操作，在离开这个点的时候如果对应操作为修改，撤销对应的修改。这样只需维护可撤销并查集，使用按秩合并或启发式合并，每次记录修改的内容到一个栈中，撤回时将栈顶的操作撤销即可。时间复杂度 $O(nB\log n+\dfrac{n^2}{B})$，当 $B=\sqrt{\dfrac{n}{\log n}}$ 时复杂度最优，为 $O(n\sqrt{n\log n})$，对应的空间复杂度为 $O(n\sqrt{n\log n})$。在本题内存限制下难以通过。
现在考虑优化内存，枚举块，每次仅记录一个块的信息，遍历操作树进行操作，判断是否在这个块内，如果是则枚举每个数，检查是否在同一连通块中。我们发现对于每个块来说，在并查集上的操作相同，只是维护的内容不同，需要预处理出每次合并及查询的点的根，否则时间复杂度会退化到 $O(n\sqrt n\log n)$，这样空间复杂度被优化到 $O(n)$，由于要多次遍历操作树，建议使用操作树的 dfs 序，此处应选用出栈入栈序。该种做法可以通过此题。
考虑进一步优化时间复杂度。处理出第 $k$ 小所在的块同上述。在块内查询时，弃用并查集，对于操作树进行树分块，此处需要的树分块应满足关键点是整个块内深度最浅的点，并且块内每个点都距离关键点不超过 $O(B)$。进行每个关键点到根节点的路径上所有连边操作，不难通过一次 dfs 或 bfs 来获得每个点所属的连通块，每次询问时将这个询问到关键点所有的连边操作也进行，只需遍历这 $O(B)$ 条边即可得到每个点在此次询问的时候的所属连通块信息，只要逐块处理空间即为 $O(n)$，时间复杂度为 $O(nB+\dfrac{n^2}{B})$，当 $B=\sqrt n$ 时取到最优，为 $O(n\sqrt n)$。
bitset
同样的将点权离散化为一个长为 $n$ 的排列，不难想到找第 $k$ 小可以拿 bitset 优化（需要手写 bitset，STL 中的 bitset 不支持）。仍然离线建操作树，使用可撤销并查集维护连通性，在并查集的根维护一个 bitset，合并时将两个 bitset 取并集，撤销时两个 bitset 取差集，查询时直接在 bitset 中查。时间复杂度 $O(\dfrac{n^2}{w})$，空间复杂度 $O(\dfrac{n^2}{w})$。在本题内存限制下难以通过。
考虑一种朴素的暴力。在并查集的根维护一个链表，每次合并的时候直接将链表拼接到一起，并且记录长度，在撤回的时候根据长度分裂为两个链表。查询的时候将这个并查集根的链表所有元素拿出来，使用 nth_elemant 找第 $k$ 小。不难发现，一个元素只会出现在一个链表里，空间复杂度 $O(n)$，时间复杂度 $O(n^2)$。
考虑数据分治，设阈值 $S=\dfrac nw$。如果一个连通块内元素个数少于 $S$，则使用链表维护，当超过 $S$ 时使用 bitset 维护，由于单个 bitset 中元素至少为 $S$，所以至多只用 $\dfrac nS=w$ 个 bitset，空间复杂度 $O(\dfrac nw\times w)=O(n)$，由于链表内元素至多 $S$ 个，所以时间复杂度 $O(nS)=O(\dfrac{n^2}{w})$。
Code
在实现时需要注意特判回退到的版本的最后一次操作仍然是一个回退操作的情况。此份代码为时间 $O(n\sqrt{n\log n})$，空间 $O(n)$ 的做法。
1 | |
P5068 [Ynoi2015] 我回来了
简要题意
你需要维护一个可重集，需要进行以下两种操作 $m$ 次：
- 加入一个数 $x$，保证 $1\le x\le n$。
- 定义关于 $x$ 的一次操作为将可重集内所有数都减去 $x$。如果在操作后可重集内的正数个数减少，则会继续操作，否则停止。询问一个区间 $[l,r]$，将在这个区间内等概率的随机出一个整数 $x$，求关于 $x$ 的操作次数的期望乘上 $r-l+1$，询问之间是独立的。
$1\le n\le 10^5,1\le m\le 10^6$。
时间限制 $\rm{1s}$，内存限制 $\rm{256MB}$。
解法
首先查询就是 $[l,r]$ 内所有数的操作次数之和。关于 $x$ 的操作次数的本质，查找 $[1,x],[x+1,2x],[2x+1,3x]\cdots[\lfloor\frac{n}{x}\rfloor\times x+1,n]$ 中从第一个没有数出现的区间。我们发现总的区间个数为 $O(\frac n1 +\frac n2+\cdots+\frac nn)=O(n\log n)$。
在线
随着数的加入，对于每个数 $x$ 来说，关于 $x$ 的操作次数单调不降，对于每个数 $x$ 维护一个双指针状物，每次加入一个值后，把所有当前没有数出现的区间中包含这个数的区间标记为已有数，同时更新那个区间对应的 $x$ 的指针，即将 $x$ 的指针往后移动，直到遇到一个没有被标记过的区间。由于需要区间查询操作次数，维护一棵树状数组，更新完 $x$ 的指针后在树状数组上更改 $x$ 对应的值为新的操作次数。由于每个区间只会被标记一次，所以最多 $O(n\log n)$ 次后移指针和修改树状数组上值的操作，时间复杂度为 $O(n\log^2n)$。查询直接在树状数组上区间查，时间复杂度 $O(m\log n)$。
考虑如何快速维护包含某个数的区间，方法较多，此处介绍一种比较容易实现的。开 $n$ 个 vector，将区间 $[l,r]$ 放到 $l$ 对应的 vector，vector 内按 $r$ 排序，用一棵线段树维护每个 vector 中最后一个区间的 $r$ 的区间最大值。每次查询时在线段树上查询 $[1,x]$ 对应的最大值是否大于 $x$，如果是则找到最大值对应的 $l$，取出最后一个，更新线段树上的信息，并且继续操作。每个区间至多被取出一次，时间复杂度 $O(n\log^2 n)$。至此，我们有了一个 $O(n\log^2 n+m\log n)$ 的在线做法。
离线
离线，处理出 $a_i$ 表示 $i$ 第一次出现的时刻，记 $f_{i,j}$ 表示对于 $i$ 的第 $j$ 个区间第一次有数的时刻，即为这个区间内 $a$ 的最小值，使用 ST 表维护。由于一个区间有贡献必须前面的区间都有值，所以计算 $g_{i,j}=\min_{k=1}^jf_{i,k}$，只要时刻大于 $g_{i,j}$，则就会给包含 $i$ 的询问贡献 $1$，按照 $g_{i,j}$ 加入区间，使用树状数组统计贡献即可。时间复杂度 $O(n\log^2 n+m\log n)$。
Code
离线做法
1 | |