题意

给出一个长为 n n 的数列，以及 nn 个操作，操作涉及单点插入，单点询问，数据随机生成。

题解

我直接用的vector来维护。这里需要用到块重构，即进行插入操作的过多，会导致某一块的数量非常的多。这样会使得块之间不平衡，复杂度不能得到保证。这时候就要对所有的元素重新分块，以保证复杂度。

代码

#include<bits/stdc++.h> using namespace std; const int nmax = 2e6+100; const int INF = 0x3f3f3f3f; const int mm = sqrt(2e6+100) + 10; int n,m; vector<int> v[mm]; int belong[nmax],num,block; int a[nmax<<1]; void init(){ block = 2*sqrt(n); num = n / block; if(num % block) num++; } void rebuild(){ int cur = 1; for(int i = 1;i<=num;++i) {for(int j = 0;j<v[i].size();++j) {a[cur++] = v[i][j];} v[i].clear();} cur --; block = 2*sqrt(cur); num = cur / block; if(num % block) num++; for(int i = 1;i<=cur;++i) { belong[i] = (i-1) / block + 1; v[belong[i]].push_back(a[i]); } } int main() { scanf("%d",&n);int temp; init(); for(int i = 1;i<=n;++i){ scanf("%d",&temp); belong[i] = (i-1) / block + 1; v[belong[i]].push_back(temp); } int op,l,r,w; for(int j = 1;j<=n;++j){ scanf("%d%d%d%d",&op,&l,&r,&w); if(op == 0){ int group = 0,pos = 0; for(int i = 1;i<=num;++i) if(l - (int)v[i].size() >0 ) l -= (int)v[i].size(); else{ group = i, pos = l; break;} v[group].insert(v[group].begin() + pos - 1,r); if(v[group].size() > 7 * block) rebuild(); }else{ int group,pos; for(int i = 1;i<=num;++i){ if(r - (int)v[i].size() > 0) r -= (int)v[i].size(); else {group = i, pos = r; break;} } printf("%d\n",v[group][pos-1]); } } return 0; }