6.数列分块入门 6

😊 | Powered By HeartFireY | 分块例题

#6282. 数列分块入门 6 - 题目 - LibreOJ (loj.ac)

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

由于操作涉及单点插入，因此分块的长度会发生变化，因此采用 v e c t o r vector vector储存每个分块的数据，在更新的时将数据暴力取出更新后放回，对分块结构进行重构。

需要注意的是，并不是每次更新都需要重构，只需要在某个分块的 s i z e size size变得非常大时，我们才对分块进行暴力重构。如果变动不大，我们可以近似认为每个分块均摊插入后的 s i z e size size。

#include 
#define ll int
#define pii pair
using namespace std;

const int N = 200005;
int blo, lst;
ll a[N], tmp_storage[N];
vector block[N];

void refresh(){
    int tot = 0;
    for(int i = 1; i  20 * blo) refresh();
}

inline int read(){
    int f = 1, x = 0; char s = getchar(); 
    while(s  '9'){ if(s =='-') f = -1; s = getchar(); } 
    while(s >= '0' && s  a[i];
    for(int i = 1; i