分块------定期重构

定期重构

讲真的，定期重构这东西在网上博客蛮少的

hzwer出了数列分块入门1-9，其中数列分块入门6就是定期重构

你需要支持的操作是：单点插入，单点查询a[r]是多少，这道题目虽然数据随机，但是想要拿全分那肯定还是得要写个定期重构的。

定期重构要干嘛？

大佬的说法：将每根号 n 个操作分为一组,每次每组结束后将当前所有组的修改放到数列中去 ------曹hl

每次询问考虑剩余的修改操作对当前询问的影响，分次进行数列重构

定期重构我认为就是在每单位个（根号n个）操作完成后对于分块数列进行重组，以维持算法的时间复杂度，保证结构稳定，（类似于“splay”）不会出现一种单块超级长的情况，否则毒瘤数据会卡得你的分块算法超时。

定期重构怎么实现：

你首先确定多少次操作后重构一次（大多数情况是根号n，但是具体情况要具体分析），然后每单位个修改操作之后就进行一次重构，维护数列的稳定（蛮容易的，看代码，唯一复杂点就是信息的复制）

分块对列六---CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200005], n, l[1005], r[1005], block, t = 0, q = 0;
int k[1000];
int c[1000][1005], cc[1000][1005];
int insert(int L, int R);
int ask(int R);
int deb();

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int R;
    block = (int)(sqrt(n));  //确定块长
    while (R != n) {
        t++;
        l[t] = (t - 1) * block + 1;
        r[t] = min(t * block, n);
        R = r[t];
        k[t] = r[t] - l[t] + 1;
    }
    //初始化分块以及记录每一块里面元素个数
    for (int i = 1; i <= t; i++)
        for (int j = l[i]; j <= r[i]; j++) c[i][j - l[i] + 1] = a[j];
    //初始化每个块里面的元素
    for (int i = 1; i <= n; i++) {
        int op, L, c;
        cin >> op >> L >> R >> c;
        if (op == 0) {
            q++, insert(L, R);  //插入
            if (q == block)
                deb(), q = 0;  //重构
        } else
            ask(R);
    }
    return 0;
}
int deb() {
    int num = 0, tt = 0, qq = 0, kk[1040], now1 = 1, now2 = 1;
    for (int i = 1; i <= t; i++) num += k[i];  //求出现在一共有多少个数，确定块长
    memset(kk, 0, sizeof(kk));
    int R = 0, z = 0;
    block = (int)(sqrt(num));  //确定块长,其实现在l和r都没用了，因为这个题目不需要
    while (R != num) {
        R++;
        qq++;
        if (R > block * now2)
            kk[now2] = block, now2++, qq = 1;
        z++;
        if (z > k[now1])
            now1++, z = 1;          //这是一个基本的指针用法
        cc[now2][qq] = c[now1][z];  //直接暴力的复制一份原来的数组
    }                               //"三指针法"（滑稽）
    if (kk[now2] == 0)
        kk[now2] = num - block * (now2 - 1);
    t = now2;
    for (int i = 1; i <= t; i++) k[i] = kk[i];
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= k[i]; j++) c[i][j] = cc[i][j];
    }
    return 0;
}
int ask(int R) {
    int now = 1, ttt = 0;
    while (ttt + k[now] < R) ttt += k[now], now++;
    R -= ttt;
    cout << c[now][R] << endl;
    return 0;  //直接查询就行了，也运用了分块的思想，每次跳都跳一个块的长度
}
int insert(int L, int R) {
    int now = 1, ttt = 0;
    while (ttt + k[now] < L) ttt += k[now], now++;
    L -= ttt;  // L减去ttt后代表的就是插入当前块的编号了
    for (int i = k[now]; i >= L; i--) c[now][i + 1] = c[now][i];
    k[now]++;
    c[now][L] = R;  //直接挪，反正块长是根号n
    return 0;
}