题解：P13981 数列分块入门 6

· · 题解

思路分析

我选择根号重构。

我们有一种非常暴力的思路：直接使用 vector 暴力模拟题目要求的过程。

事实上，STL 里面的 vector 的 insert 或者 emplace 操作本质上还是在将数据向后移动，单次时间复杂度仍然是 O(n) 的。

我们观察题目名称，首先可以考虑将原序列按照一定的大小分段存储到 vector 中。

不过看起来并没有什么用，毕竟后期单个块的大小仍然可以成长到 O(n) 级别。

这时候，我们就可以请出神秘的根号重构了。你有两种大方向可以选择：

  1. 定期重构

具体的来说，每经过 O(\sqrt n) 次修改操作，就将序列拍扁，然后重新分块。这种技巧在很多地方也可以见到。

我们不难发现，每一次查询操作的时间复杂度维持在 O(\sqrt n) 级别，而修改操作则因为单个块的大小也维持在 O(\sqrt n) 级别而有了 O(\sqrt n) 的下界。

实际上，重构是一个非常耗时的操作，因此建议重构间隔可以拉的大一些，实测 20\sqrt n 是比较优的，不过针对这道题。实际上要想较为严谨的时间复杂度保障建议取 3 到 8 倍。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[600005], lc, rb; vector<int>v[1005];
inline vector<int>::iterator at(int p) {
    int ns = 0;
    for (int i = 0;; ++i)
        if (ns + v[i].size() < p) ns += v[i].size();
        else return v[i].begin() + (p - ns - 1);
}
inline int av(int p) {
    int ns = 0;
    for (int i = 0;; ++i)
        if (ns + v[i].size() < p) ns += v[i].size();
        else return i;
}
signed main() {
    ios::sync_with_stdio(0); cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    rb = sqrt(n);
    for (int i = 1; i <= n; ++i) v[i / rb].emplace_back(a[i]);
    for (int i = 1, o, l, r; i <= n; ++i)
        if (cin >> o >> l, o & 1) cout << *at(l) << endl;
        else {
            cin >> r, v[av(l)].emplace(at(l), r); lc++;
            if (lc == 10 * rb) {
                lc = 0;
                for (int i = 0; v[i].size(); ++i)
                    for (int j : v[i]) a[++lc] = j;
                for (int i = 0; v[i].size(); ++i) v[i].clear();
                rb = sqrt(lc);
                for (int i = 1; i <= lc; ++i) v[i / rb].emplace_back(a[i]);
                lc = 0;
            }
        }
}
  1. 不平衡时重构

类似的技巧可在替罪羊树中见到。比如在这道题中，我们可以将“不平衡”定义为某一块的长度超过了给定的阈值，比如说 2\times\sqrt n。

对于不平衡的块，我们将其暴力重构。每一次查询操作的时间复杂度维持在 O(\sqrt n) 级别，而修改操作则因为单个块的大小也维持在 O(\sqrt n) 级别而有了 O(\sqrt n) 的下界。

很显然，这种不平衡时重构的方法比定期重构的常数要小很多。

不过需要注意到此时存在向整个序列中间插入新的块的可能性。对应的解决方案是将所有的块的对象指针存入 vector，或者使用 list。

由于块本身信息多数情况下很大，因此一般来说不将块信息本身存进 vector 里面，否则时间复杂度可能退化。

没实现代码，那就不贴代码了。

提醒一点：有的题目初始时有 n 个元素，然后进行 m 次操作。注意不要将块长设置为 \sqrt n。如果我令 n=1,m=10^5，那你不就炸了吗？

所以这种情况还是比较推荐定长分块的。