分块（单点插入，单点查询

大意是让一个数插入某个数之前，然后在让你查询某点的值

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1e5 + 10;
 6 const int inf = 0x3f3f3f3f;
 7 int dir[10][10] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 8 int a[maxn], b[maxn];
 9 int opt, l, r, c, m, t, n;
10 vector<int > v[1010];
11 struct st
12 {
13     int x, y;
14 };
15 
16 inline int read()
17 {
18     char ch = getchar(); ll k = 0, f = 1;
19     while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
20     while(ch >= '0' && ch <= '9') {k = (k << 1) + (k << 3) + ch - '0'; ch = getchar();}
21     return k * f;
22 }
23 
24 inline st findy(int x)
25 {
26     int i = 1;
27     while(x > v[i].size())
28         x -= v[i].size(), ++i;
29     return (st) {i, x - 1} ;
30 }
31 
32 inline void rebuild()  // 重新分块
33 {
34     int cnt = 0;
35     for(int i = 1; i <= m; ++i)
36     {
37         int s = v[i].size();
38         for(int j = 0; j <= s - 1; ++j)
39         {
40             b[++cnt] = v[i][j];
41         }
42         v[i].clear();
43     }
44     t = sqrt(cnt), m = (cnt - 1) / t + 1;
45     for(int i = 1; i <= cnt; ++i)
46     {
47         v[(i - 1) / t + 1].push_back(b[i]);
48     }
49 }
50 inline void inser(int l, int r)
51 {
52     st k = findy(l);
53     int x = k.x, y = k.y;
54     v[x].insert(v[x].begin() + y, r);
55     if(v[x].size() > 10 * t) rebuild();  //体现分块的思想，如果一直往一个块插入数据那不和暴力没区别了吗，因此块内数据过多时要重新分块。
56 }
57 
58 int main()
59 {
60     std::ios::sync_with_stdio(false);std::cin.tie(0);
61     n = read();
62     for(int i = 1; i <= n; ++i)
63     {
64         a[i] = read();
65     }
66 
67     t = sqrt(n); m = (n - 1) / t + 1;
68     for(int i = 1; i <= n; ++i)
69     {
70         v[(i - 1) / t + 1].push_back(a[i]);
71     }
72 
73     for(int i = 1; i <= n; ++i)
74     {
75         opt = read(); l = read(); r = read(); c = read();
76         if(opt == 0) inser(l, r);
77         else
78         {
79             st ch = findy(r);
80             cout<< v[ch.x][ch.y] <<endl;
81         }
82     }
83     return 0;
84 }

这题数据很水，直接vector insert暴力就能过，当然我不建议。。

分块 （单点插入，单点查询

分块（单点插入，单点查询