原题地址：https://loj.ac/problem/6282 题意：给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问，数据随机生成。 思路：在这题中,单纯的数组分块难以实现插入的功能，因为你插入一个元素，为了影响次序，必须将这个元素之后的元素都往后移动一位，这太浪费时间。 所以这里考虑每一个分块的数据用vector来维护，这样便于实现插入操作，并且往后挪移一位元素的复杂也不会太高。另外如果插入元素太多的话，可以考虑重新分块，m每一次重新分块的时间复杂度O（n）.
同样引入hzwer的话： 先说随机数据的情况，之前提到过，如果我们块内用数组以外的数据结构，能够支持其它不一样的操作，比如此题每块内可以放一个动态的数组，每次插入时先找到位置所在的块，再暴力插入，把块内的其它元素直接向后移动一位，当然用链表也是可以的。查询的时候类似，复杂度分析略。
但是这样做有个问题，如果数据不随机怎么办？如果先在一个块有大量单点插入，这个块的大小会大大超过√n，那块内的暴力就没有复杂度保证了。还需要引入一个操作：重新分块（重构） 每根号n次插入后，重新把数列平均分一下块，重构需要的复杂度为O(n)，重构的次数为√n，所以重构的复杂度没有问题，而且保证了每个块的大小相对均衡。 当然，也可以当某个块过大时重构，或者只把这个块分成两半。
#include <bits/stdc++.h> using namespace std; typedef pair<int, int>pii;//first 表示位于第i个分块,且是第second 个位置(位置从0开始) typedef long long ll; const int maxn = 1e5 + 5; int n, block, belog[maxn*10], opt, l, r, c, m,top; //m是最大块数 int a[maxn]; int st[maxn * 10]; vector<int>v[maxn]; vector<int>::iterator it; inline int read() { int ret = 0, c, f = 1; for(c = getchar(); !(isdigit(c) || c == '-'); c = getchar()); if(c == '-') f = -1, c = getchar(); for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0'; if(f < 0) ret = -ret; return ret; } pii query(int num) {//计算第num个元素是位于哪个vector以及哪个位置 int x = 1; while(num > v[x].size()) { num -= v[x].size(); x++; } return make_pair(x, num - 1); //-1是因为vector的元素是从0开始的 } void rebuild() { top = 0; for(int i = 1; i <= m; i++) { for(it = v[i].begin(); it != v[i].end(); it++) { st[++top] = *it; //把所有vector中的元素取出，再重新分块，++top是将范围定位[1,top] } v[i].clear();//千万别忘了清空 } int block = sqrt(top); m = (top - 1) / block + 1; for(int i = 1; i <= top; i++) { belog[i] = (i - 1) / block + 1;//belog数组在这题作用不大 v[belog[i]].push_back(st[i]); } } void updata(int l, int r) { pii t = query(l); v[t.first].insert(v[t.first].begin() + t.second, r);//vector的插入操作 if(v[t.first].size()>10*block) rebuild(); } int main() { n = read(); block = sqrt(n); for(int i = 1; i <= n; i++) { a[i] = read(); belog[i] = (i - 1) / block + 1; v[belog[i]].push_back(a[i]); } m = (n - 1 / block) + 1; for(int i=1;i<=n;i++){ opt = read(); l = read(); r = read(); c = read(); if(opt) { pii t = query(r); printf("%d\n", v[t.first][t.second]); } else updata(l, r); } return 0; }