大佬总结
数列分块入门 1
#include<bits/stdc++.h>
#define L(i) (bl[i] - 1) * blo + 1
#define R(i) bl[i] * blo
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 5e4 + 10;
int a[MAXN], bl[MAXN], tag[MAXN];
int blo, n, m;void add(int l, int r, int k)
{if(bl[l] == bl[r]){_for(i, l, r) a[i] += k;return;}_for(i, l, R(l)) a[i] += k;_for(i, L(r), r) a[i] += k;_for(i, bl[l] + 1, bl[r] - 1) tag[i] += k;
}int main()
{scanf("%d", &n); blo = sqrt(n);_for(i, 1, n){scanf("%d", &a[i]);bl[i] = (i - 1) / blo + 1;}while(n--){int op, l, r, c; scanf("%d%d%d%d", &op, &l, &r, &c);if(op == 0) add(l, r, c);else printf("%d\n", a[r] + tag[bl[r]]);}return 0;
}数列分块入门 2
可以对每一个块进行排序，用vector存储每一个块的信息
可以发现lowerbond的值恰好就是小于x的个数
#include<bits/stdc++.h>
#define L(i) (i - 1) * blo + 1
#define R(i) min(i * blo, n)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 5e4 + 10;
const int MAXM = 250;
int a[MAXN],bl[MAXN], tag[MAXN];
int blo, n, m;
vector<int> ve[MAXM];inline void s(int k)
{ ve[k].clear();_for(i, L(k), R(k)) ve[k].push_back(a[i]);sort(ve[k].begin(), ve[k].end());
}inline void add(int l, int r, int k)
{if(bl[l] == bl[r]){_for(i, l, r) a[i] += k; s(bl[l]);return;}_for(i, l, R(bl[l])) a[i] += k; s(bl[l]);_for(i, L(bl[r]), r) a[i] += k; s(bl[r]);_for(i, bl[l] + 1, bl[r] - 1) tag[i] += k;
}inline int query(int l, int r, int k)
{int res = 0;if(bl[l] == bl[r]){_for(i, l, r) if(a[i] + tag[bl[l]] < k)res++;return res;}_for(i, l, R(bl[l])) if(a[i] + tag[bl[l]] < k) res++;_for(i, L(bl[r]), r) if(a[i] + tag[bl[r]] < k) res++;_for(i, bl[l] + 1, bl[r] - 1)res += lower_bound(ve[i].begin(), ve[i].end(), k - tag[i]) - ve[i].begin();return res;
}void init()
{blo = sqrt(n);for(int i = 1; i <= n; i++) bl[i] = (i - 1) / blo + 1;_for(i, 1, bl[n]) s(i);
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);init();REP(i, 0, n){int op, l, r, c; scanf("%d%d%d%d", &op, &l, &r, &c);if(op == 0) add(l, r, c);else printf("%d\n", query(l, r, c * c));}return 0;
}数列分块入门 3
用set简直太方便！！比vector方便多了！！set可以自动排序，增加删除都很方便。
#include<bits/stdc++.h>
#define L(i) (i - 1) * blo + 1
#define R(i) min(i * blo, n)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
const int MAXM = 350;
int a[MAXN], bl[MAXN], tag[MAXM];
int blo, n, m;
set<int> s[MAXM];inline void motify(int x, int q) //第x个元素加上q
{s[bl[x]].erase(a[x]);a[x] += q;s[bl[x]].insert(a[x]);
}inline void add(int l, int r, int k)
{if(bl[l] == bl[r]){_for(i, l, r) motify(i, k);return;}_for(i, l, R(bl[l])) motify(i, k);_for(i, L(bl[r]), r) motify(i, k);_for(i, bl[l] + 1, bl[r] - 1) tag[i] += k;
}inline void update(int now, int& res, int k)
{if(now < k && now > res) res = now;
}inline int query(int l, int r, int k)
{int res = -1;if(bl[l] == bl[r]){_for(i, l, r) update(a[i] + tag[bl[l]], res, k);return res;}_for(i, l, R(bl[l])) update(a[i] + tag[bl[l]], res, k);_for(i, L(bl[r]), r) update(a[i] + tag[bl[r]], res, k);_for(i, bl[l] + 1, bl[r] - 1){set<int>::iterator it = s[i].lower_bound(k - tag[i]);if(it == s[i].begin()) continue; it--;update(*it + tag[i], res, k);}return res;
}void init()
{blo = sqrt(n);for(int i = 1; i <= n; i++) {bl[i] = (i - 1) / blo + 1;s[bl[i]].insert(a[i]);}
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);init();REP(i, 0, n){int op, l, r, c; scanf("%d%d%d%d", &op, &l, &r, &c);if(op == 0) add(l, r, c);else printf("%d\n", query(l, r, c));}return 0;
}数列分块入门 4
多开一个sum数组。涉及到区间修改开tag数组，涉及到区间求和用sum数组
记得开long long
#include<bits/stdc++.h>
#define L(i) (i - 1) * blo + 1
#define R(i) min(i * blo, n)
#define cal(a, b) a = (a + b) % MOD
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 5e4 + 10;
const int MAXM = 250;
ll a[MAXN], sum[MAXM], tag[MAXN];
int bl[MAXN], blo, n, m;inline void add(int l, int r, int k)
{if(bl[l] == bl[r]){_for(i, l, r) a[i] += k, sum[bl[l]] += k; return;}_for(i, l, R(bl[l])) a[i] += k, sum[bl[l]] += k; _for(i, L(bl[r]), r) a[i] += k, sum[bl[r]] += k; _for(i, bl[l] + 1, bl[r] - 1) tag[i] += k;
}inline ll query(int l, int r, int MOD)
{ll res = 0;if(bl[l] == bl[r]){_for(i, l, r) cal(res, a[i] + tag[bl[l]]);return res;}_for(i, l, R(bl[l])) cal(res, a[i] + tag[bl[l]]);_for(i, L(bl[r]), r) cal(res, a[i] + tag[bl[r]]);_for(i, bl[l] + 1, bl[r] - 1) cal(res, sum[i] + blo * tag[i]);return res;
}void init()
{blo = sqrt(n);for(int i = 1; i <= n; i++) {bl[i] = (i - 1) / blo + 1;sum[bl[i]] += a[i];}
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);init();REP(i, 0, n){int op, l, r, c; scanf("%d%d%d%d", &op, &l, &r, &c);if(op == 0) add(l, r, c);else printf("%lld\n", query(l, r, c + 1));}return 0;
}数列分块入门5
正好前几天做过一模一样的题，是用线段树写的。核心就是很多数开方几次就变成1了，分块的时候可以看如果sum[i]==blo的话说明全部是1，就直接跳过就好了。其实应该有0的情况，所以应该写sum[i] > blo才执行，但是不知道为什么我这么写以后拿了80分。
#include<bits/stdc++.h>
#define L(i) (i - 1) * blo + 1
#define R(i) min(i * blo, n)
#define cal(a, b) a = (a + b) % MOD
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 5e4 + 10;
const int MAXM = 250;
ll a[MAXN], sum[MAXM];
int bl[MAXN], blo, n, m;inline void updata(int i)
{sum[bl[i]] -= a[i] - sqrt(a[i]);a[i] = sqrt(a[i]);
}inline void change(int l, int r)
{if(bl[l] == bl[r]){if(sum[bl[l]] == blo) return;_for(i, l, r) updata(i);return;}if(sum[bl[l]] != blo)_for(i, l, R(bl[l])) updata(i);if(sum[bl[r]] != blo)_for(i, L(bl[r]), r) updata(i);_for(i, bl[l] + 1, bl[r] - 1){if(sum[i] == blo) continue;_for(j, L(i), R(i))updata(j);}
}inline ll query(int l, int r)
{ll res = 0;if(bl[l] == bl[r]){_for(i, l, r) res += a[i];return res;}_for(i, l, R(bl[l])) res += a[i];_for(i, L(bl[r]), r) res += a[i];_for(i, bl[l] + 1, bl[r] - 1) res += sum[i];return res;
}void init()
{blo = sqrt(n);for(int i = 1; i <= n; i++) {bl[i] = (i - 1) / blo + 1;sum[bl[i]] += a[i];}
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);init();REP(i, 0, n){int op, l, r, c; scanf("%d%d%d%d", &op, &l, &r, &c);if(op == 0) change(l, r);else printf("%lld\n", query(l, r));}return 0;
}数列分块入门6
不得不说，这道题真的
非常暴力！！！！
这样也可以过？？？？？
看来我低估了数据强度（）
因为vector支持在中间插入，所以用vector来存每一块的内容
然后每加入一个数就找到时第几块第几个位置（注意这里vector下标从0开始，我因此WA一次）
然后加入就好了。
这里有个技巧是重构
就是当一个块很多的时候，复杂度会很大，这个时候可以重构，O（n）
复杂度分析：构建分块O（n），每次查询根号n，每次加入根号n
所以是n的1.5次方
复杂度貌似没有问题……我想到了这个方法但是感觉太暴力就没敢写
分块是一个优秀的暴力……
反思
（1）没有算复杂度的习惯，导致想到正解却不敢写
（2）随机数据代表不会有一些专门卡你的数据，数据比较弱
（3）vector加入操作
(4)分块的重构技巧
（5）写完后静态查错。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 2e5 + 10;
const int MAXM = 500;
vector<int> ve[MAXM];
int tmp[MAXN], num, n, blo, m;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void rebulid()
{num = 0;_for(i, 1, m){REP(j, 0, ve[i].size())tmp[++num] = ve[i][j]; ve[i].clear();}blo = sqrt(num);_for(i, 1, num){int t = (i - 1) / blo + 1;ve[t].push_back(tmp[i]);}m = (num - 1) / blo + 1;
}void add(int l, int c)
{int x = 1;while(l > ve[x].size()) //这个定位的方法很棒 l -= ve[x++].size();ve[x].insert(ve[x].begin() + l - 1, c);if(ve[x].size() > blo * 10) rebulid();
}int query(int l)
{int x = 1;while(l > ve[x].size()) l -= ve[x++].size();return ve[x][l-1];
}int main()
{read(n);blo = sqrt(n);_for(i, 1, n){int x; read(x);int t = (i - 1) / blo + 1;ve[t].push_back(x);}m = (n - 1) / blo + 1;_for(i, 1, n){int op, l, r, c;read(op); read(l); read(r); read(c); if(op == 0) add(l, r);else printf("%d\n", query(r));}return 0;
}数列分块入门 7
这道题之前做过，还想了好久……方法有些问题……
先乘后加，如果乘的话要把加法标记一起乘了。
然后如果暴力的话，那么就要把标记的值传下来然后再做，然后标记清零。
#include<bits/stdc++.h>
#define L(i) (i - 1) * blo + 1
#define R(i) min(n, i * blo)
#define a(x, y) x = (x + y) % MOD
#define m(x, y) x = (x * y) % MOD
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
const int MAXM = 500;
const int MOD = 10007;
int bl[MAXN], tag[MAXM], ftag[MAXM], a[MAXN];
int blo, n;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}inline int query(int r)
{return (a[r] * ftag[bl[r]] % MOD + tag[bl[r]]) % MOD;
}void reset(int x)
{_for(i, L(x), R(x))a[i] = query(i);tag[x] = 0; ftag[x] = 1;
}void add(int l, int r, int c)
{if(bl[l] == bl[r]){reset(bl[l]);_for(i, l, r) a(a[i], c);return;}reset(bl[l]); _for(i, l, R(bl[l])) a(a[i], c);reset(bl[r]); _for(i, L(bl[r]), r) a(a[i], c);_for(i, bl[l] + 1, bl[r] - 1) a(tag[i], c);
}void mul(int l, int r, int c)
{if(bl[l] == bl[r]){reset(bl[l]);_for(i, l, r) m(a[i], c);return;}reset(bl[l]); _for(i, l, R(bl[l])) m(a[i], c);reset(bl[r]); _for(i, L(bl[r]), r) m(a[i], c);_for(i, bl[l] + 1, bl[r] - 1) m(tag[i], c), m(ftag[i], c);
}int main()
{read(n);blo = sqrt(n);_for(i, 1, n) {read(a[i]);bl[i] = (i - 1) / blo + 1;}_for(i, 1, bl[n]) ftag[i] = 1;_for(i, 1, n){int op, l, r, c;read(op); read(l); read(r); read(c); if(op == 0) add(l, r, c);else if(op == 1) mul(l, r, c);else printf("%d\n", query(r));}return 0;
}数列分块入门8
足足写了两个半小时。
开始看到统计个数，想到二分，用lower_bound和upper_bound的差值。
所以用，multiset，也就是可以加入重复元素的set
然后就一直调，一直WA，各种各样的细节错误
后来发现懒标记改掉的时候我没有改变multiset里面的值
然后发现这样还不如直接用数组。
非常非常暴力的求值
加速就加在懒标记，统计的时候便利块的时候可以O（1）过去
真的好暴力，我想复杂了。
暴力出奇迹！！
#include<bits/stdc++.h>
#define L(i) ((i - 1) * blo + 1)
#define R(i) min(n, i * blo)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
int bl[MAXN], a[MAXN], tag[MAXN];
int blo, n;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void reset(int x, int c)
{_for(i, L(x), R(x))a[i] = c;tag[x] = -1;
}void deal(int i, int c, int& res)
{if(tag[bl[i]] != -1) reset(bl[i], tag[bl[i]]);if(a[i] == c) res++;a[i] = c;
}int query(int l, int r, int c)
{int res = 0;if(bl[l] == bl[r]){_for(i, l, r) deal(i, c, res);return res;}_for(i, l, R(bl[l])) deal(i, c, res);_for(i, L(bl[r]), r) deal(i, c, res);_for(i, bl[l] + 1, bl[r] - 1){if(tag[i] != -1) res += (tag[i] == c) ? blo : 0;else _for(j, L(i), R(i)) deal(j, c, res); tag[i] = c;}return res;
}int main()
{memset(tag, -1, sizeof(tag)); read(n); blo = sqrt(n);_for(i, 1, n) {read(a[i]);bl[i] = (i - 1) / blo + 1;}_for(k, 1, n){int l, r, c;read(l); read(r); read(c); printf("%d\n", query(l, r, c));}return 0;
}数列分块入门9（区间众数）
这道题真的秀！！
思考分块算法的时候分两个部分，一个是块内，一个是多余部分
对于这道题，设块大小为S
（1）块内可以暴力预处理出来，N * N / S
（2）多余部分可以用vector+二分的骚操作弄。
对于每个数值建一个vector，插入位置。
然后查询的时候用当前左端点和右端点二分的差值就是个数。
很秀！
复杂度NlogNS
所以总的复杂度是 O（N * N / S + NlogNS）
当N * N / S = NlogNS时最小
得S = 根号下N /logN
注意这里如果用根号N的话会TLE。
最后注意要离散化一下。
#include<bits/stdc++.h>
#define L(i) ((i - 1) * blo + 1)
#define R(i) min(n, i * blo)
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
const int MAXM = 2e3 + 10;int bl[MAXN], a[MAXN], b[MAXN];
int pos[MAXN], f[MAXM][MAXM];
int p[MAXN], buck[MAXN], blo, n;vector<int> ve[MAXN];void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void updata(int times, int& cnt, int& ans, int now)
{if(times > cnt) cnt = times, ans = now;else if(times == cnt && now < ans) ans = now;
}int time(int x, int l, int r)
{int a = lower_bound(ve[x].begin(), ve[x].end(), l) - ve[x].begin();int b = upper_bound(ve[x].begin(), ve[x].end(), r) - ve[x].begin();return b - a;
}int query(int l, int r)
{if(bl[l] == bl[r]){int ans = 0, cnt = 0;_for(i, l, r)updata(time(a[i], l, r), cnt, ans, a[i]);return ans;}int ans = f[bl[l] + 1][bl[r] - 1]; int cnt = time(ans, l, r); _for(i, l, R(bl[l])) updata(time(a[i], l, r), cnt, ans, a[i]);_for(i, L(bl[r]), r) updata(time(a[i], l, r), cnt, ans, a[i]);return ans;
}void Read()
{read(n); blo = sqrt(n / log2(n));_for(i, 1, n) {read(a[i]);bl[i] = (i - 1) / blo + 1;b[i] = a[i];}
}void Disperse()
{sort(b + 1, b + n + 1);int m = unique(b + 1, b + n + 1) - b - 1; _for(i, 1, n){int x = lower_bound(b + 1, b + m + 1, a[i]) - b;p[x] = a[i];a[i] = x;}
}void deal(int x)
{int ans = 0, cnt = 0;memset(buck, 0, sizeof(buck));_for(i, L(x), n){buck[a[i]]++;updata(buck[a[i]], cnt, ans, a[i]);f[x][bl[i]] = ans; }
}void work()
{_for(i, 1, bl[n]) deal(i);_for(i, 1, n) ve[a[i]].push_back(i);_for(q, 1, n){int l, r;read(l); read(r);printf("%d\n", p[query(l, r)]);}
}int main()
{Read();Disperse();work();return 0;
}bzoj 2038 (莫队算法)
这就是分块的另一种应用了，对询问进行分块，也就是莫队算法。
这个算法的精髓在于可以利用之前求出的结果离线查询，知道[L，R]
的每次可以答案O(1)的时间对端点拓展一个单位
要注意左端点右端点拓展的方式不同。
然后注意一些细节
（1）n和m的意义要非常清楚，不要搞混
（2） 注意有些地方会爆int， 尤其乘法的时候。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 5e4 + 10;
int color[MAXN], bl[MAXN], sum[MAXN];
int blo, n, m;
ll ans;
struct node
{int l, r, id;ll a, b;bool operator < (const node& rhs) const{if(bl[l] != bl[rhs.l]) return bl[l] < bl[rhs.l];return r < rhs.r;}
}a[MAXN];void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}bool cmp(node a, node b) { return a.id < b.id; }ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }inline void motify(int x, int t)
{ans += (sum[color[x]] << 1) * t + 1;sum[color[x]] += t;
}int main()
{read(n); read(m); blo = sqrt(n);_for(i, 1, n) {read(color[i]);bl[i] = (i - 1) / blo + 1;}_for(i, 1, m){a[i].id = i;read(a[i].l); read(a[i].r);}sort(a + 1, a + m + 1);int last_l = 1, last_r = 0;_for(i, 1, m){a[i].b = (ll)(a[i].r - a[i].l) * (a[i].r - a[i].l + 1);while(last_r < a[i].r) motify(++last_r, 1);while(last_r > a[i].r) motify(last_r--, -1);while(last_l < a[i].l) motify(last_l++, -1);while(last_l > a[i].l) motify(--last_l, 1);a[i].a = ans - (a[i].r - a[i].l + 1);}sort(a + 1, a + m + 1, cmp);_for(i, 1, m){ll t = gcd(a[i].a, a[i].b);printf("%lld/%lld\n", a[i].a / t, a[i].b / t);}return 0;
}