模板及讲解

分块是什么

主体思想是把序列分块每块长为$\sqrt n$，然后进行处理
(一般是考虑1.处理不完整块2.处理完整块3.预处理的三种情况)。
分块的调试检测技巧：可以生成一些大数据，然后用两份分块大小不同的代码来对拍，还可以根据运行时间尝试调整分块大小，减小常数。

(以下文字部分转与hzwer的博客)

分块常见题型

区间加法，单点查询(知识点：lazy标记)

给出一个长为$n$的数列，以及$m$个操作，操作涉及区间加法，单点查值。Luogu 3368
解法：把原序列分块，我们把每$\sqrt n$个元素分为一块，然后就能得到$n / \sqrt n = \sqrt n$个块。我们给每个块设置一个加法标记(就是记录这个块中元素一起加了多少)，每次操作对每个整块直接$O(1)$标记，而不完整的块由于元素比较少，暴力修改元素的值。每次询问时返回元素的值加上其所在块的加法标记。每次区间加的操作复杂度为$O(\sqrt n + \sqrt n)$(中间块的整体修改+两边不完整的块的逐一修改)。

//由于luogu题目数据范围大，无法承受sprt(n)*m的复杂度，所以本程序只有70分
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 500000 + 5;
int n, m, ai[MAXN];//输入数组 
int totblo, lazy[MAXN], bl[MAXN];//每块大小(sqrt(n))，lazy标记，每个数属于哪个块 
void add(int x, int y, int k) {
    for (int i = x; i <= min(y, bl[x] * totblo); i++) ai[i] += k;//左边的块
    if (bl[x] != bl[y]) for (int i = (bl[y] - 1) * totblo + 1; i <= y; i++) ai[i] += k;//右边的块，记得有可能[x,y]只在一个块中的情况 
    for (int i = bl[x] + 1; i <= bl[y] - 1; i++) lazy[i] += k;//中间整块只更新lazy 
}
void clean() {}
void solve() {
    clean();
    totblo = sqrt(n);
    for (int i = 1; i <= n; i++) bl[i] = (i - 1) / totblo + 1;//随便推堆公式就能出来 
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]);
    while (m--) {
        int opt; scanf("%d", &opt);
        if (opt == 1) {
            int x, y, k;
            scanf("%d%d%d", &x, &y, &k);
            add(x, y, k);
        } else if (opt == 2) {
            int x; 
            scanf("%d", &x);
            printf("%d\n", ai[x] + lazy[bl[x]]);//原数加上lazy标记值 
        }
    }
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}

扩展1：区间加法，区间查询
给出一个长为$n$的数列，以及$m$个操作，操作涉及区间加法，区间查询。
解法：还是按照上面的方法，但是要记录一个块的总元素和。很好维护，处理不完整块的时候就直接加就行；完整块直接按照块大小乘以增加量即可。代码略去。
扩展2：区间乘法，单点查询/区间查询
给出一个长为$n$的数列，以及$m$个操作，操作涉及区间乘法，单点查询/区间查询。
解法：和以上两种方法类似，不再做解释。

区间加法，查询区间小于/大于某数的总个数(知识点：块中套数据结构/STL等)

给出一个长为$n$的数列，以及$m$个操作，操作涉及区间加法，区间查询区间小于/大于某数的总个数Luogu 2801
解法：思路是将序列分成$\sqrt n$个块，然后每个块排序，每次查询非整块暴力处理，整块二分。
预处理：把序列分成$\sqrt n$个块，然后分别排序
修改：非整块直接暴力修改；整块修改lazy值即可。但是非整块修改会影响这个块的顺序，而整块不会，所以非整块要重新排序。
查询：非整块直接暴力统计；整块二分即可，记得带上lazy值即可
注意：totblo只是块长，bl[n]才是总块数

这里用vector来存块的排序

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 1000000 + 5, MAXK = 1000 + 5;
LL n, Q, ai[MAXN], totblo, bl[MAXN], lazy[MAXK]; 
//输入的n，Q，序列ai, 总块数totblo, 每个数属于哪个块，lazy标记
vector<LL> vec_sortedBlo[MAXK];//每个块的排序后的有序区间
void add(LL x, LL y, LL c) {
    for (LL i = x; i <= min(y, totblo * bl[x]); i++) ai[i] += c;
    vec_sortedBlo[bl[x]].clear();
    for (LL i = totblo * (bl[x] - 1) + 1; i <= totblo * bl[x]; i++) vec_sortedBlo[bl[x]].push_back(ai[i] += lazy[bl[x]]);
    lazy[bl[x]] = 0;
    sort(vec_sortedBlo[bl[x]].begin(), vec_sortedBlo[bl[x]].end());
    //处理非整块(前)

    if (bl[x] != bl[y]) {
        for (LL i = (bl[y] - 1) * totblo + 1; i <= y; i++) ai[i] += c;
        vec_sortedBlo[bl[y]].clear();
        for (LL i = (bl[y] - 1) * totblo + 1; i <= bl[y] * totblo; i++) vec_sortedBlo[bl[y]].push_back(ai[i] += lazy[bl[y]]);
        lazy[bl[y]] = 0;
        sort(vec_sortedBlo[bl[y]].begin(), vec_sortedBlo[bl[y]].end());
    }//处理非整块(后)

    for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) lazy[i] += c;//处理整块
}
LL query(LL x, LL y, LL c) {
    LL ret = 0;
    for (LL i = x; i <= min(y, totblo * bl[x]); i++) if (ai[i] + lazy[bl[x]] >= c) ret++;
    if (bl[x] != bl[y]) for (LL i = (bl[y] - 1) * totblo + 1; i <= y; i++) if (ai[i] + lazy[bl[y]] >= c) ret++;
    //处理非整块
    for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) {
        //LL les = lower_bound(vec_sortedBlo[i].begin(), vec_sortedBlo[i].end(), c - lazy[i]) - vec_sortedBlo[i].begin();
        LL ans = -1, l = 0, r = vec_sortedBlo[i].size(); 
        while (l < r) {
            LL mid = (l + r) >> 1;
            if (lazy[i] + vec_sortedBlo[i][mid] < c) ans = mid, l = mid + 1; else r = mid; 
        }
        ret += (LL)vec_sortedBlo[i].size() - ans - 1;
    }//处理整块
    return ret;
}
void clean() {
    ms(bl, 0); 
}
void solve() {
    clean();
    totblo = sqrt(n);
    for (LL i = 1; i <= n; i++) bl[i] = (i - 1) / totblo + 1;
    for (LL i = 1; i <= n; i++) {
        scanf("%lld", &ai[i]);
        vec_sortedBlo[bl[i]].push_back(ai[i]);
    }
    for (LL i = 1; i <= bl[n]; i++) sort(vec_sortedBlo[i].begin(), vec_sortedBlo[i].end());//预处理，排序。totblo只是块长，bl[n]才是总块数
    char ch[10];
    while (Q--) {
        scanf("%s", ch);
        if (ch[0] == 'M') {
            LL l, r, w;
            scanf("%lld%lld%lld", &l, &r, &w);
            add(l, r, w);
        } else {
            LL l, r, c;
            scanf("%lld%lld%lld", &l, &r, &c);
            printf("%lld\n", query(l, r, c));
        }
    }
}
int main() {
    scanf("%lld%lld", &n, &Q), solve();
    return 0;
}

扩展1：区间加法，区间添加/删除元素/求前驱/后继
给出一个长为$n$的数列，以及$m$个操作，操作涉及区间加法，区间添加/删除元素/求前驱/后继
解：可以和上面的做法一样，不用vector而是使用set即可

区间开方，区间求值(知识点：块中标记优化)

给出一个长为$n$的数列，以及$m$个操作，操作涉及区间开方，区间求值SPOJ GSS4
解：非整块还是暴力更新。由于一个数sqrt很少次数变为0或1，因为一个块的开方和不能直接得到，那么只能是如果一个块全是1或0，标记这个块不再处理，否则无论是整块还是非整块都暴力更新。每个数更新的次数非常小。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5, MAXK = 400 + 5;
LL n, Q, totblo, bl[MAXN], ai[MAXN];
//输入n,Q,块的大小，每个元素属于的块，序列ai
LL sum[MAXK], mark[MAXK];
//块元素和，标记(是否都为1或0)
void solveSqrt(LL x) {//处理
    if (mark[x]) return ;
    int flag = true; 
    for (LL i = (x - 1) * totblo + 1; i <= x * totblo; i++) {
        if (ai[i] != 0 || ai[i] != 1) {
            sum[x] -= ai[i], ai[i] = sqrt(ai[i]), sum[x] += ai[i];
            if (ai[i] != 0 && ai[i] != 1) flag = false;
        }
    }
    if (flag) mark[x] = 1;//标记
}
void update(LL x, LL y) {
    for (LL i = x; i <= min(y, totblo * bl[x]); i++) sum[bl[x]] -= ai[i], ai[i] = sqrt(ai[i]), sum[bl[x]] += ai[i];
    if (bl[x] != bl[y]) for (LL i = totblo * (bl[y] - 1) + 1; i <= y; i++) sum[bl[y]] -= ai[i], ai[i] = sqrt(ai[i]), sum[bl[y]] += ai[i];
    for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) solveSqrt(i);
}
LL query(LL x, LL y) {
    LL ret = 0;
    for (LL i = x; i <= min(y, totblo * bl[x]); i++) ret += ai[i];
    if (bl[x] != bl[y]) for (LL i = totblo * (bl[y] - 1) + 1; i <= y; i++) ret += ai[i];
    for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) ret += sum[i];
    return ret;
}
void clean() {
    ms(sum, 0), ms(mark, 0);
}
void solve() {
    clean();
    totblo = sqrt(n);
    for (LL i = 1; i <= n; i++) {
        scanf("%lld", &ai[i]);
        bl[i] = (i - 1) / totblo + 1, sum[bl[i]] += ai[i];
    }
    scanf("%lld", &Q);
    while (Q--) {
        LL x, l, r;
        scanf("%lld%lld%lld", &x, &l, &r);
        if (l > r) swap(l, r);
        if (x == 1) {
            printf("%lld\n", query(l, r));
        } else {
            update(l, r);
        }
    }
}
int main() {
    LL kase = 0;
    while (scanf("%lld", &n) == 1) printf("Case #%lld:\n", ++kase), solve(), printf("\n");
    return 0;
}

区间众数(知识点：预处理i块/i点到j块/j点区间)

题意：强制在线不修改求区间众数。Bzoj 2724
我们将原数列分块，预处理$i$块到$j$块区间的众数，直接开桶统计，用于求解整块的区间。
用vector把相同的数的位置按顺序存储下来，求众数可以用询问区间的每个数字去求他出现次数，比较即可。
对于整块，我们预处理了$i$块到$j$块区间的众数，直接询问这个数字在询问区间出现次数即可；
对于不完整的块，我们暴力每个数字在询问区间出现次数即可
最后输出即可，时间复杂度$O(m \cdot logn+\frac nm)$, 其中$n$为数列长，$m$为每个块长，根据均值不等式，在$m \cdot logn=\frac nm$时和有最小值，$m=\sqrt{\frac{n}{logn}}$，即得到最优分块大小

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 40000 + 5;
int n, q, whw, ai[MAXN], key = 0, tax[MAXN], tax1[MAXN], blolen, bl[MAXN], s[1005][1005];
vector<int> hh[MAXN];
int cx(int v, int x, int y) {
    return upper_bound(hh[v].begin(), hh[v].end(), y) - upper_bound(hh[v].begin(), hh[v].end(), x - 1);
}
int query(int x, int y) {
    int mks = cx(s[bl[x] + 1][bl[y] - 1], x, y), ret = s[bl[x] + 1][bl[y] - 1];
    for (int i = x; i <= min(y, bl[x] * blolen); i++) {
        int tmp = cx(ai[i], x, y);
        if (tmp > mks) ret = ai[i], mks = tmp; else if (tmp == mks && ai[i] < ret) ret = ai[i];
    }
    if (bl[x] != bl[y]) for (int i = (bl[y] - 1) * blolen + 1; i <= y; i++) {
        int tmp = cx(ai[i], x, y);
        if (tmp > mks) ret = ai[i], mks = tmp; else if (tmp == mks && ai[i] < ret) ret = ai[i];
    }
    return ret;
}
void clean() {}
int solve() {
    clean();
    blolen = (int)sqrt((db)n / log2(n));
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax1[i] = ai[i], bl[i] = (i - 1) / blolen + 1;
    sort(tax1 + 1, tax1 + 1 + n), whw = unique(tax1 + 1, tax1 + 1 + n) - tax1 - 1;
    for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax1 + 1, tax1 + 1 + whw, ai[i]) - tax1, hh[ai[i]].push_back(i);
    bool f = n % blolen;
    for (int i = 1; i <= n / blolen + f; i++) {
        ms(tax, 0); int mks = 0;
        for (int j = i; j <= n / blolen + f; j++) {
            s[i][j] = s[i][j - 1];
            for (int k = (j - 1) * blolen + 1; k <= min(n, j * blolen); k++) {
                tax[ai[k]]++;
                if (tax[ai[k]] > mks) mks = tax[ai[k]], s[i][j] = ai[k]; else if (tax[ai[k]] == mks && ai[k] < s[i][j]) s[i][j] = ai[k];
            }
        }
    }
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + key - 1) % n + 1, r = (r + key - 1) % n + 1;
        if (l > r) swap(l, r);
        printf("%d\n", key = tax1[query(l, r)]);
    }
    return 0; 
}
int main() {
    scanf("%d%d", &n, &q), solve();
    return 0;
}