题解：P13981 数列分块入门 6
Lonelyhacker
·
·
题解
题意
给出一个长为 n 的数列，以及 n 个操作，操作有两种（\mathrm{opt}\in\{0,1\}），涉及：
- 单点插入（\mathrm{opt}=0），在第 l 个数字前插入数字 r。
- 单点询问（\mathrm{opt}=1），求 a_c。
## 题解
我们之前的思路是：对于一个下标 $i$，存储其所在块的编号，然后进行整块 or 散块（散点）的修改。但是，这里的插入操作会打乱我们的顺序。例如在第 $i$ 个位置插入 $x$，那么对于 $\forall i \in [i,n+1],a_i$ 的所在块的编号都可能发生改变，真的去修改显然会是线性的，显然无法通过。
既然记录点所在块的编号行不通，那我们就反其道而行之，记录每个块所包含的下标。对于修改，我们直接暴力查找，在 $\sqrt{n}$ 个块中找到位置 $l$ 对应的是哪个块的哪个位置，然后直接插入。这样插入就是 $O(\sqrt{n})$ 的；对于查询，我们照样暴力查找，找到下标 $c$ 所在的块的编号以及在这个块的位置，直接输出，也是 $O(\sqrt{n})$ 的。那么总的时间复杂度就是 $O(\sqrt{n})$ 的了？这么优秀？
显然不是。“查询下标 $c$ 所在的块的编号以及在这个块的位置”的复杂度确实是 $O(\sqrt{n})$ 的，但是你插入的复杂度是**下标所在块的块长**。也就是说，我们上面插入部分的复杂度的计算是默认块长一直都是 $\sqrt{n}$ 的，但这显然不可能。很容易构造数据，使得每次插入都在同一个块内的第一个位置，这个块的块长可以被卡到 $n$ 且每次插入的复杂度都是卡满的，单次插入的复杂度就会由 $O(\sqrt{n})$ 变成 $O(n)$，可能会炸。因此，我们需要进行优化。
优化也很粗暴，当某个块的块长超过阈值的时候直接全部重构，复杂度是 $O(n)$ 的。显然我们不能一直重构，所以这个阈值设定比较关键，我设的是十倍的块长。
## 代码
保留详细注释。
```cpp
#include <iostream>
#include <cmath>
#include <vector>
#define pii pair <int, int>
#define fs first
#define sc second
#define mp make_pair
using namespace std;
const int N = 3e5+5;
int n, blo, m, st[2*N]; // 有可能全部都是修改，要开两倍
vector <int> vec[2*N];
pii query(int x){ // 查询位置x为第pos个分块的第几个
int pos = 1;
while (x > vec[pos].size()) x -= vec[pos].size(), pos++;
return mp(pos, x-1); // 这里减一是因为vector下标为0
}
void rebuild(){
int top = 0;
for (int i = 1; i <= m; i++){ // 首先把所有的点全部打散到st里面
for (auto j : vec[i])
st[++top] = j;
vec[i].clear(); // 记得清空
}
blo = sqrt(top); // 重新设置blo
for (int i = 1; i <= top; i++) // 重新加入点
vec[(i-1)/blo+1].push_back(st[i]);
m = (top-1)/blo+1; // 将m更新为当前分块总数
}
void ins(int a, int b){
pii c = query(a); // 先查询
vec[c.fs].insert(vec[c.fs].begin()+c.sc, b); // 再插入
if (vec[c.fs].size() >= 10*blo) // 若该块长度超过预设值
rebuild(); // 整个全部重构
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
blo = sqrt(n);
for (int i = 1, x; i <= n; i++){
cin >> x;
vec[(i-1)/blo+1].push_back(x);
}
m = (n-1)/blo+1; // 这个m就是分块的总数了
for (int i = 1, f, a, b, c; i <= n; i++){
cin >> f;
if (f == 0) cin >> a >> b, ins(a, b);
else{
cin >> c;
pii t = query(c);
cout << vec[t.fs][t.sc] << '\n';
}
}
return 0;
}
```
## 后日谈
虽然但是 [不重构也能通过此题](https://www.luogu.com.cn/record/234840274)，而且居然和 [重构了的代码跑得一样快](https://www.luogu.com.cn/record/234464343)。
我算了一下，当 $n=3\times10^5$ 时，$\sqrt{n}\approx548$，因此如果要将块长卡到 $n$ 必须要插 $n-548$ 次，而且就算卡到了 $n$，也只剩下 $548$ 次操作了，继续插的复杂度也不会太慢。忽略块长的继续变化，算出来是 $548\cdot n = 1.644\times10^8$，还是可通过的。