生活随笔
收集整理的這篇文章主要介紹了
LOJ 数列分块入门6
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
LOJ 數列分塊入門6
題目：
題解：
- 我都不懂這題為什么要用分塊... ...
- 直接vector就好了...
- 但是如果有區間修改的話就不行了。所以這題是啟示我們也可以動態分塊。具體就是每次插入時先找到位置所在的塊，再暴力插入，把塊內的其它元素直接向后移動一位。如果對于一個塊插入過多元素時，需要重構（重新分塊），從而使分塊擁有更高的性能。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#define N 2000005
using namespace std;vector<int> a;
struct Blo {int l, r;} blo[N];
int n, num, size;
int bel[N];int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x *= f;
}void build(int len) {size = (int)sqrt(len), num = len / size;if (len % size) num++;for (int i = 1; i <= len; i++) bel[i] = (i - 1) / size + 1;for (int i = 1; i <= num; i++) {blo[i].l = (i - 1) * size;blo[i].r = i * size;}blo[num].r = len;
}void update(int pos, int val) {blo[bel[pos]].r++;for (int i = bel[pos] + 1; i <= num; i++) {blo[i].l++;blo[i].r++;}a.insert(a.begin() + pos, val);
}int ask(int pos) {return a[pos];
}int main() {cin >> n;a.push_back(-1);for (int i = 1; i <= n; i++) a.push_back(read());build(n);for (int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(!op) update(l, r);else printf("%d\n", ask(r));}return 0;
}
轉載于:https://www.cnblogs.com/BigYellowDog/p/11243433.html
總結
以上是生活随笔為你收集整理的LOJ 数列分块入门6的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
