一個動態的插入過程，還需要帶有查詢操作。

我可以把區間先分塊，然后每個塊塊用vector來維護它的插入和查詢操作，但是如果我現在這個塊里的vector太大了，我可能的操作會變的太大，所以這時候我需要把現在里面的數全部拿出來，然后進行重構，然后再進行后面的操作。

#include<map> #include<set> #include<ctime> #include<cmath> #include<stack> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define lowbit(x) (x & (-x))typedef unsigned long long int ull; typedef long long int ll; const double pi = 4.0*atan(1.0); const int inf = 0x3f3f3f3f; const int maxn = 200005; const int maxm = 400; const int mod = 10007; using namespace std;int n, m, tol, T; int block; int a[maxn]; int b[maxn]; int belong[maxn]; vector<int> v[maxn];void init() {memset(a, 0, sizeof a);memset(b, 0, sizeof b);memset(belong, 0, sizeof belong); }int L(int x) {return (x-1) * block + 1; }int R(int x) {return min(n, x*block); }pair<int, int> query(int x) {int t = 1;while(x > v[t].size()) {x -= v[t].size();t++;}return make_pair(t, x-1); }void rebuild() {int num = 1;for(int i=1; i<=belong[n]; i++) {for(auto j : v[i]) b[num++] = j;v[i].clear();}int block2 = sqrt(num);for(int i=1; i<=num; i++) belong[i] = (i-1) / block2 + 1;for(int i=1; i<=num; i++) v[belong[i]].push_back(a[i]);block = block2;n = num; }void update(int l, int r) {pair<int, int > x = query(l);v[x.first].insert(v[x.first].begin()+x.second, r);if(v[x.first].size() > 20 * block) rebuild(); }int main() {while(~scanf("%d", &n)) {block = sqrt(n);for(int i=1; i<=n; i++) {scanf("%d", &a[i]);belong[i] = (i-1) / block + 1;}for(int i=1; i<=n; i++) {v[belong[i]].push_back(a[i]);}m = n;while(m--) {int op, l, r, c;scanf("%d%d%d%d", &op, &l, &r, &c);if(op == 0) {update(l, r);} else {pair<int, int> x = query(r);printf("%d\n", v[x.first][x.second]);}}}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Jiaaaaaaaqi/p/9382330.html

總結

以上是生活随笔為你收集整理的LOJ#6282. 数列分块入门 6的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。