LOJ數列分塊入門 6 題解 重新分塊（重構）

題目連結：​​https://loj.ac/p/6282​​

涉及操作：

1. 單點插入；
2. 單調詢問。

解題思路：

每 \(\sqrt n\) 次插入後，重新把數列平均分一下，重構需要的時間複雜度為 \(O(n)\)，重構的次數為 \(O(\sqrt n)\)，可以解決這個問題。

#include <bits/stdc++.h>
using namespace std;
int n, m, blo, a;
vector<int> vec[1010], tmp;

void rebuild() {
    tmp.clear();
    for (int i = 1; i <= m; i ++) {
        for (auto x : vec[i])
            tmp.push_back(x);
        vec[i].clear();
    }
    int sz = tmp.size();
    int blo2 = sqrt(sz);
    for (int i = 0; i < sz; i ++)
        vec[i/blo2+1].push_back(tmp[i]);
    m = (sz - 1) / blo2 + 1;
}
pair<int, int> query(int p) {
    int x = 1;
    while (vec[x].size() < p) {
        p -= vec[x].size();
        x ++;
    }
    return { x, p-1 };
}
void add(int p, int val) {
    pair<int, int> pi = query(p);
    int x = pi.first, y = pi.second;
    vec[x].insert(vec[x].begin() + y, val);
    if (vec[x].size() > 20*blo)
        rebuild();
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    blo = sqrt(n);
    for (int i = 1; i <= n; i ++) {
        cin >> a;
        vec[(i-1)/blo+1].push_back(a);
    }
    m = (n - 1) / blo + 1;
    for (int i = 0; i < n; i ++) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (op == 0) add(l, r);
        else {
            pair<int, int> pi = query(r);
            int x = pi.first, y = pi.second;
            cout << vec[x][y] << endl;
        }
    }
    return 0;
}