分块1-9(未完) | Kyons'Blog 


 




分块1-9(未完)

发表于 | 分类于 | | 阅读次数:

序

感谢@hzwer大佬出的练习题
题目链接LOJ
本蒟过弱,实在不知道怎么压缩代码量了->_->

数列分块入门 1

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，单点查值。

将$n$个数,按照每$\sqrt{n}$为一个块标记.

1
2
3
belong[x]:元素x所在的块的编号，样例代码中为bl[x];
start[x]:编号为x的块的最左边的点，样例代码中为st[x];
end[x]:编号为x的块的最右边的点，样例代码中为ed[x];

每次对所给的$[l,r]$区间进行讨论,分为”单蹦”和”块”,对于不满块的数,直接暴力修改.
对于满足块的数,直接打一个标记,当访问的时候再进行修改即可,类似于线段树$lazy$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
belong[x]:元素x所在的块的编号，样例代码中为bl[x];
start[x]:编号为x的块的最左边的点，样例代码中为st[x];
end[x]:编号为x的块的最右边的点，样例代码中为ed[x];
*/
const int MAXN = 1e5 + 10;

int belong[MAXN], tot = 1, a[MAXN], n, cnt;
struct block {
    int lazy;
    int start, end;
} p[MAXN];

int main() {
    cin >> n;
    cnt = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);  // cin >> a[i];
        belong[i] = tot;
        if (i % cnt == 1)
            p[tot].start = i;
        if (i % cnt == 0)
            p[tot++].end = i;
    }
    if (n % cnt) {
        p[tot].start = p[tot - 1].end + 1;
        p[tot++].end = n;
    }

    for (int i = 1; i <= n; i++) {
        int opt, l, r, c;
        scanf("%d %d %d %d", &opt, &l, &r, &c);  // cin >> opt>> l >> r >> c;
        if (opt)
            cout << p[belong[r]].lazy + a[r] << endl;
        else {
            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l)
                    p[belong[l]].lazy += c;
                else
                    for (int j = l; j <= p[belong[l]].end; j++) 
                        a[j] += c;
                if (p[belong[r]].end == r)
                    p[belong[r]].lazy += c;
                else
                    for (int j = p[belong[r]].start; j <= r; j++) 
                        a[j] += c;
                for (int j = belong[l] + 1; j < belong[r]; j++) 
                    p[j].lazy += c;
            } else if (p[belong[l]].start == l && p[belong[r]].end == r)
                p[belong[l]].lazy += c;
            else
                for (int j = l; j <= r; j++) 
                    a[j] += c;
        }
    }

    return 0;
}

数列分块入门 2

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的元素个数。

区间加法仿照$1$即可.
对于每一个块内的数据,为了方便查询,我们分便对每一个块内的数据进行排序.
对于不满足块的数据,我们暴力处理,再将这个块内的数据排序,
满足块的区间,我们依然是打标记即可.
查询的时候,二分查找即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
const int MAXN = 1e5 + 10;

/*
belong[x]:元素x所在的块的编号，样例代码中为bl[x];
start[x]:编号为x的块的最左边的点，样例代码中为st[x];
end[x]:编号为x的块的最右边的点，样例代码中为ed[x];
*/

int belong[MAXN], tot = 1, n, cnt, a[MAXN],b[MAXN];
struct block {
    int lazy;
    int start, end;
} p[MAXN];

void rechange(int l, int r)
{
    for(int i = l; i <= r; i++)
        b[i] = a[i];
    sort(b + l, b + r + 1);
}

int lowerbound(int *array, int size, int key, int lazy) {
    int first = 0, middle;
    int half, len;
    len = size;

    while (len > 0) {
        half = len >> 1;
        middle = first + half;
        if (array[middle] + lazy < key) {
            first = middle + 1;
            len = len - half - 1;  //在右边子序列中查找
        }
        else
            len = half;  //在左边子序列（包含middle）中查找
    }
    return first;
}

int main() {
    cin >> n;
    cnt = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i]=a[i];
        belong[i] = tot;
        if (i % cnt == 1)
            p[tot].start = i;
        if (i % cnt == 0)
            p[tot++].end = i;
    }
    if (n % cnt) {
        p[tot].start = p[tot - 1].end + 1;
        p[tot++].end = n;
    }
    for (int i = 1; i < tot; i++) 
        sort(b + p[i].start, b + p[i].end + 1);

    for (int i = 1; i <= n; i++) {
        int opt, l, r, c;
        scanf("%d %d %d %d", &opt, &l, &r, &c);
        if (opt) {
            int ans = 0;
            c *= c;

            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l)
                    ans += lowerbound(b + l, p[belong[l]].end - l + 1, c, p[belong[l]].lazy);
                else
                    for (int j = l; j <= p[belong[l]].end; j++)
                        if (a[j] + p[belong[j]].lazy < c)
                            ans++;

                if (p[belong[r]].end == r)
                    ans += lowerbound(b + p[belong[r]].start, r - p[belong[r]].start + 1, c, p[belong[r]].lazy);
                else
                    for (int j = p[belong[r]].start; j <= r; j++)
                        if (a[j] + p[belong[j]].lazy < c)
                            ans++;

                for (int j = belong[l] + 1; j < belong[r]; j++)
                    ans += lowerbound(b + p[j].start, p[j].end - p[j].start + 1, c, p[j].lazy);
            }
            else if (p[belong[l]].start == l && p[belong[r]].end == r)
                ans += lowerbound(b + l, r - l + 1, c, p[belong[l]].lazy);
            else 
                for (int j = l; j <= r; j++)
                    if (a[j] + p[belong[j]].lazy < c)
                        ans++;

            cout << ans << '\n';
        }
        else
            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l)
                    p[belong[l]].lazy += c;
                else {
                    for (int j = l; j <= p[belong[l]].end; j++)
                        a[j] += c;
                    rechange(p[belong[l]].start, p[belong[l]].end);
                }
                if (p[belong[r]].end == r)
                    p[belong[r]].lazy += c;
                else {
                    for (int j = p[belong[r]].start; j <= r; j++)
                        a[j] += c;
                    rechange(p[belong[r]].start, p[belong[r]].end);
                }
                for (int j = belong[l] + 1; j < belong[r]; j++)
                    p[j].lazy += c;
            }
            else if (p[belong[l]].start == l && p[belong[r]].end == r)
                p[belong[l]].lazy += c;
            else {
                for (int j = l; j <= r; j++)
                    a[j] += c;
                rechange(p[belong[l]].start, p[belong[l]].end);
            }
    }

    return 0;
}

数列分块入门 3

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）。

和$2$类似.

出题人的想法:
可以在块内维护其它结构使其更具有拓展性，比如放一个 set ，这样如果还有插入、删除元素的操作，会更加的方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
const int MAXN = 1e5 + 10;

/*
belong[x]:元素x所在的块的编号，样例代码中为bl[x];
start[x]:编号为x的块的最左边的点，样例代码中为st[x];
end[x]:编号为x的块的最右边的点，样例代码中为ed[x];
*/

int belong[MAXN], tot = 1, n, cnt, a[MAXN], b[MAXN];
struct block {
    int lazy;
    int start, end;
} p[MAXN];

void rechange(int l, int r)
{
    for (int i = l; i <= r; i++)
        b[i] = a[i];
    sort(b + l, b + r + 1);
}

int lowerbound(int *array, int size, int key, int lazy) {
    int first = 0, middle;
    int half, len;
    len = size;

    while (len > 0) {
        half = len >> 1;
        middle = first + half;
        if (array[middle] + lazy < key) {
            first = middle + 1;
            len = len - half - 1;  //在右边子序列中查找
        }
        else
            len = half;  //在左边子序列（包含middle）中查找
    }
    return first;
}

int main() {
    cin >> n;
    cnt = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];    //cin >> a[i];//scanf("%d", &a[i]);
        belong[i] = tot;
        if (i % cnt == 1)
            p[tot].start = i;
        if (i % cnt == 0)
            p[tot++].end = i;
    }
    if (n % cnt) {
        p[tot].start = p[tot - 1].end + 1;
        p[tot++].end = n;
    }
    for (int i = 1; i < tot; i++)
        sort(b + p[i].start, b + p[i].end + 1);

    for (int i = 1; i <= n; i++) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;// scanf("%d %d %d %d", &opt, &l, &r, &c);
        if (opt) {
            int ans = -1;

            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l) {
                    int t = lowerbound(b + l, p[belong[l]].end - l + 1, c, p[belong[l]].lazy);
                    if (t)
                        ans = max(ans, b[p[belong[l]].start+t-1] + p[belong[l]].lazy);
                }
                else
                    for (int j = l; j <= p[belong[l]].end; j++)
                        if (a[j] + p[belong[j]].lazy < c)
                            ans = max(ans, a[j] + p[belong[j]].lazy);

                if (p[belong[r]].end == r) {
                    int t = lowerbound(b + p[belong[r]].start, r - p[belong[r]].start + 1, c, p[belong[r]].lazy);
                    if (t)
                        ans = max(ans, b[p[belong[r]].start + t - 1] + p[belong[r]].lazy);
                }
                else
                    for (int j = p[belong[r]].start; j <= r; j++)
                        if (a[j] + p[belong[j]].lazy < c)
                            ans = max(ans, a[j] + p[belong[j]].lazy);

                for (int j = belong[l] + 1; j < belong[r]; j++) {
                    int t = lowerbound(b + p[j].start, p[j].end- p[j].start + 1, c, p[j].lazy);
                    if (t)
                        ans = max(ans, b[p[j].start + t - 1] + p[j].lazy);
                }
            }
            else if (p[belong[l]].start == l && p[belong[r]].end == r) {
                int t = lowerbound(b + l, r - l + 1, c, p[belong[l]].lazy);
                if (t)
                    ans = max(ans, b[l + t - 1] + p[belong[l]].lazy);
            }
            else
                for (int j = l; j <= r; j++)
                    if (a[j] + p[belong[j]].lazy < c)
                        ans = max(ans, a[j] + p[belong[j]].lazy);

            cout << ans << '\n';
        }
        else
            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l)
                    p[belong[l]].lazy += c;
                else {
                    for (int j = l; j <= p[belong[l]].end; j++)
                        a[j] += c;
                    rechange(p[belong[l]].start, p[belong[l]].end);
                }
                if (p[belong[r]].end == r)
                    p[belong[r]].lazy += c;
                else {
                    for (int j = p[belong[r]].start; j <= r; j++)
                        a[j] += c;
                    rechange(p[belong[r]].start, p[belong[r]].end);
                }
                for (int j = belong[l] + 1; j < belong[r]; j++)
                    p[j].lazy += c;
            }
            else if (p[belong[l]].start == l && p[belong[r]].end == r)
                p[belong[l]].lazy += c;
            else {
                for (int j = l; j <= r; j++)
                    a[j] += c;
                rechange(p[belong[l]].start, p[belong[l]].end);
            }
    }

    return 0;
}

数列分块入门 4

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，区间求和。

求和预处理一下就阔以了,打标记的时候是长度$*$加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

typedef long long ll;
const int MAXN = 1e5 + 10;

/*
belong[x]:元素x所在的块的编号，样例代码中为bl[x];
start[x]:编号为x的块的最左边的点，样例代码中为st[x];
end[x]:编号为x的块的最右边的点，样例代码中为ed[x];
*/
ll cnt, a[MAXN];
int belong[MAXN], tot = 1, n;
struct block {
    ll lazy;
    ll sum;
    int start, end;
} p[MAXN];

int main() {
    cin >> n;
    cnt = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];    //scanf("%d", &a[i]);
        belong[i] = tot;
        p[tot].sum += a[i];
        if (i % cnt == 1)
            p[tot].start = i;
        if (i % cnt == 0)
            p[tot++].end = i;
    }
    if (n % cnt) {
        p[tot].start = p[tot - 1].end + 1;
        p[tot++].end = n;
    }

    for (int i = 1; i <= n; i++) {
        int opt, l, r;
        ll c;
        cin >> opt >> l >> r >> c;// scanf("%d %d %d %d", &opt, &l, &r, &c);
        if (opt) {
            ll ans = 0;

            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l)
                    ans = (ans + (p[belong[l]].lazy*(p[belong[l]].end - p[belong[l]].start + 1)) % (c + 1) + p[belong[l]].sum % (c + 1)) % (c + 1);
                else
                    for (int j = l; j <= p[belong[l]].end; j++)
                        ans = (ans + a[j] % (c + 1) + p[belong[j]].lazy % (c + 1)) % (c + 1);

                if (p[belong[r]].end == r)
                    ans = (ans + (p[belong[r]].lazy*(p[belong[r]].end - p[belong[r]].start + 1)) % (c + 1) + p[belong[r]].sum % (c + 1)) % (c + 1);
                else
                    for (int j = p[belong[r]].start; j <= r; j++)
                        ans = (ans + a[j] % (c + 1) + p[belong[j]].lazy % (c + 1)) % (c + 1);

                for (int j = belong[l] + 1; j < belong[r]; j++)
                    ans = (ans + (p[j].lazy*(p[j].end - p[j].start + 1)) % (c + 1) + p[j].sum % (c + 1)) % (c + 1);
            }
            else if (p[belong[l]].start == l && p[belong[r]].end == r)
                ans = (ans + (p[belong[l]].lazy*(p[belong[l]].end - p[belong[l]].start + 1)) % (c + 1) + p[belong[l]].sum % (c + 1)) % (c + 1);
            else
                for (int j = l; j <= r; j++)
                    ans = (ans + a[j] % (c + 1) + p[belong[j]].lazy % (c + 1)) % (c + 1);

            cout << ans << '\n';
        }
        else
            if (belong[l] != belong[r]) {
                if (p[belong[l]].start == l)
                    p[belong[l]].lazy += c;
                else
                    for (int j = l; j <= p[belong[l]].end; j++) {
                        a[j] += c;
                        p[belong[l]].sum += c;
                    }
                if (p[belong[r]].end == r)
                    p[belong[r]].lazy += c;
                else
                    for (int j = p[belong[r]].start; j <= r; j++) {
                        p[belong[r]].sum += c;
                        a[j] += c;
                    }
                for (int j = belong[l] + 1; j < belong[r]; j++)
                    p[j].lazy += c;
            }
            else if (p[belong[l]].start == l && p[belong[r]].end == r)
                p[belong[l]].lazy += c;
            else
                for (int j = l; j <= r; j++) {
                    a[j] += c;
                    p[belong[l]].sum += c;
                }
    }

    return 0;
}

数列分块入门 5

给出一个长为 $n$ 的数列 ，以及 $n$ 个操作，操作涉及区间开方，区间求和。

这个题目其实比较搞人==
对于一个数,其属于${-2^{31},2^{31}-1}$,最多开方不超过$4$次.
还是和之前一样,单个暴力,整块标记.
对于一个块,如果开方次数超过$4$次,或者整个块只有$1$或$0$,我们就可以认为不需要对其处理了,只记下和即可.
自己代码实现的时候,注意细节.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
typedef long long ll;
const int MAXN = 1e5 + 10;

/* 
   belong[x]:元素x所在的块的编号，样例代码中为bl[x];
   start[x]:编号为x的块的最左边的点，样例代码中为st[x];
   end[x]:编号为x的块的最右边的点，样例代码中为ed[x]; */
int cnt, a[MAXN];
int belong[MAXN], tot = 1, n;
struct block {
  int lazy;
  ll sum;
  int start, end;
  bool f;
    block() {
    lazy = start = end = sum = 0;
    f = false;
}} p[MAXN];

void built() {
  cin >> n;
  cnt = sqrt(n);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];                // scanf("%d", &a[i]);
    belong[i] = tot;

    if (a[i] != 0)
      p[tot].sum++;

    if (i % cnt == 1)
      p[tot].start = i;
    if (i % cnt == 0)
      p[tot++].end = i;
  }
  if (n % cnt) {
    p[tot].start = p[tot - 1].end + 1;
    p[tot++].end = n;
  }
}

void print(int l, int r) {
  ll ans = 0, c;
  cin >> c;

  if (belong[l] != belong[r]) {
    if (p[belong[l]].start == l)
      if (p[belong[l]].lazy > 4 || p[belong[l]].f)
        ans += p[belong[l]].sum;

      else {
        p[belong[l]].f = true;
        for (int i = p[belong[l]].start; i <= p[belong[l]].end; i++) {
          int lazy = p[belong[l]].lazy, x = a[i];
          while (lazy) {
            if (x == 0 || x == 1)
              break;
            x = sqrt(x);
            lazy--;
          }
          if (x != 1 && x != 0)
            p[belong[l]].f = false;
          ans += x;
        }
    } else
      for (int i = l; i <= p[belong[l]].end; i++) {
        int lazy = p[belong[l]].lazy, x = a[i];
        while (lazy) {
          if (x == 0 || x == 1)
            break;
          x = sqrt(x);
          lazy--;
        }
        ans += x;
      }

    if (p[belong[r]].end == r)
      if (p[belong[r]].lazy > 4 || p[belong[r]].f)
        ans += p[belong[r]].sum;

      else {
        p[belong[r]].f = true;
        for (int i = p[belong[r]].start; i <= p[belong[r]].end; i++) {
          int lazy = p[belong[r]].lazy, x = a[i];
          while (lazy) {
            if (x == 0 || x == 1)
              break;
            x = sqrt(x);
            lazy--;
          }

          if (x != 1 && x != 0)
            p[belong[r]].f = false;
          ans += x;
        }
    } else
      for (int i = p[belong[r]].start; i <= r; i++) {
        int lazy = p[belong[r]].lazy, x = a[i];
        while (lazy) {
          if (x == 0 || x == 1)
            break;
          x = sqrt(x);
          lazy--;
        }
        ans += x;
      }

    for (int i = belong[l] + 1; i < belong[r]; i++)
      if (p[i].lazy > 4 || p[i].f)
        ans += p[i].sum;
      else {
        p[i].f = true;
        for (int j = p[i].start; j <= p[i].end; j++) {
          int lazy = p[i].lazy, x = a[j];
          while (lazy) {
            if (x == 0 || x == 1)
              break;
            x = sqrt(x);
            lazy--;
          }

          if (x != 1 && x != 0)
            p[i].f = false;
          ans += x;
        }
      }
  }

  else if (p[belong[l]].start == l && p[belong[r]].end == r)
    if (p[belong[l]].lazy > 4 || p[belong[l]].f)
      ans += p[belong[l]].sum;
    else {
      p[belong[l]].f = true;
      for (int i = p[belong[l]].start; i <= p[belong[l]].end; i++) {
        int lazy = p[belong[r]].lazy, x = a[i];
        while (lazy) {
          if (x == 0 || x == 1)
            break;
          x = sqrt(x);
          lazy--;
        }

        if (x != 1 && x != 0)
          p[belong[l]].f = false;
        ans += x;
      }
    }

  else
    for (int i = l; i <= r; i++) {
      int lazy = p[belong[l]].lazy, x = a[i];
      while (lazy) {
        if (x == 0 || x == 1)
          break;
        x = sqrt(x);
        lazy--;
      }
      ans += x;
    }

  cout << ans << '\n';
}

void update(int l, int r) {
  ll c;
  cin >> c;
  if (belong[l] != belong[r]) {
    if (p[belong[l]].start == l)
      p[belong[l]].lazy++;
    else
      for (int i = l; i <= p[belong[l]].end; i++)
        a[i] = sqrt(a[i]);
    if (p[belong[r]].end == r)
      p[belong[r]].lazy++;
    else
      for (int i = p[belong[r]].start; i <= r; i++)
        a[i] = sqrt(a[i]);
    for (int i = belong[l] + 1; i < belong[r]; i++)
      p[i].lazy++;
  } else if (p[belong[l]].start == l && p[belong[r]].end == r)
    p[belong[l]].lazy++;
  else
    for (int i = l; i <= r; i++)
      a[i] = sqrt(a[i]);
}

int main() {
  built();
  for (int i = 1; i <= n; i++) {
    int opt, l, r;
    cin >> opt >> l >> r;       // scanf("%d %d %d %d",
    // &opt,
    // &l, &r, &c);
    if (opt)
      print(l, r);
    else
      update(l, r);
  }

  return 0;
}

数列分块入门 6

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

到了喜闻乐见的动态分块了$23333$.
$c++$的$vector$大法好,我是不会用指针写链表的,拒绝
每次插入一个数,就找到对应的块,扔进去就行.
将插入的次数记下来,当次数超过$\sqrt n$的时候就进行重构,也就是重新分块.
然后就没有然后了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
const int MAXN = 1e6 + 10;
const int INF = 1e8 + 10;
const int MOD = 998244353;
const int ans = 11;
typedef long long ll;

int a[MAXN];
vector<int>p[MAXN];
int n, tot = 0, m, optt;

void find(int k)
{
    int num = 0;
    for (int i = 0; i < tot; i++) {
        num += p[i].size();
        if (num >= k) {
            num -= p[i].size();
            k = k - num - 1;
            cout << p[i][k] << '\n';
            break;
        }
    }
}

void rebuild()
{
    int num = 0;
    for (int i = 0; i < tot; i++) {
        for (int j = 0; j < p[i].size(); j++)
            a[++num] = p[i][j];
        p[i].clear();
    }

    n = num, m = sqrt(n), tot = 0;
    for (int i = 1; i <= n; i++) {
        p[tot].push_back(a[i]);
        if (i%m == 0)
            tot++;
    }
    if (n%m != 0)
        tot++;
}

void insert(int k, int x)
{
    int num = 0;
    for (int i = 0; i < tot; i++) {
        num += p[i].size();
        if (num >= k) {
            num -= p[i].size();
            k = k - num - 1;
            p[i].insert(p[i].begin() + k, x);
            optt++;
            break;
        }
    }
    if (optt == m) {
        rebuild();
        optt = 0;
    }
}

int main()
{
    cin >> n;
    m = sqrt(n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d",&x);
        p[tot].push_back(x);
        if (i%m == 0)
            tot++;
    }
    if (n%m != 0)
        tot++;

    int opt, l, r, c, q = n;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if (opt)
            find(r);
        else
            insert(l, r);
    }

    return 0;
}

未完待续








 




 


 


 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载