#6282. 数列分块入门 6（单点插入，单点询问）

题目链接：https://loj.ac/problem/6282

题目大意：中文题目

具体思路：用vector存，每一次查询的时候，从头开始，逐段逐段的减，更新的时候，也是从头开始。插入：q.insert(q.begin()+（长度-1），val),如果一个段里面存的值过多的话，可以考虑重新建图。

AC代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 #include<map>
 6 #include<vector>
 7 using namespace std;
 8 # define ll long long
 9 const int maxn = 2e5+100;
10 int a[maxn],n,block,tot,maxpos;
11 vector<int>q[maxn];
12 void rebuild(){
13 int cnt=0;
14 for(int i=1;i<=maxpos;i++){
15 for(int j=0;j<q[i].size();j++){
16 a[++cnt]=q[i][j];
17 }
18 q[i].clear();
19 }
20 for(int i=1;i<=cnt;i++){
21 q[(i-1)/block+1].push_back(a[i]);
22 }
23 maxpos=(cnt-1)/block+1;
24 }
25 pair<int,int>query(int pos){
26 int cnt=1;
27 while(pos>q[cnt].size()){
28 pos-=q[cnt].size();
29 cnt++;
30 }
31 return make_pair(cnt,pos-1);
32 }
33 void add(int pos,int val){
34 pair<int,int>w=query(pos);
35 q[w.first].insert(q[w.first].begin()+w.second,val);
36 if(q[w.first].size()>10*block)rebuild();
37 }
38 int ask(int pos){
39 pair<int,int>w=query(pos);
40 return q[w.first][w.second];
41 }
42 int main(){
43 scanf("%d",&n);
44 block=(int)sqrt(n);
45 for(int i=1;i<=n;i++){
46 scanf("%d",&a[i]);
47 q[(i-1)/block+1].push_back(a[i]);
48 }
49 maxpos=(n-1)/block+1;
50 int q=n;
51 int op,st,ed,val;
52 while(q--){
53 scanf("%d %d %d %d",&op,&st,&ed,&val);
54 if(op==0){
55 add(st,ed);
56 }
57 else if(op==1){
58 printf("%d
",ask(ed));
59 }
60 }
61 return 0;
62 }