数列分块入门1-9

分块1

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 50003;
int n, opt, a, b, c, cnt;
int w[maxn], in[maxn], addtag[maxn];
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
inline void add(int l, int r, int x) {
	for (int i = l; i <= min(r, in[l]*cnt); i++)
		w[i] += x;

	if (in[l] != in[r])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++)
			w[i] += x;

	for (int i = in[l] + 1; i < in[r]; i++)
		addtag[i] += x;
}
inline int query(int x) {
	return w[x] + addtag[in[x]];
}
int main() {
	n = read();
	cnt = sqrt(n);

	for (int i = 1; i <= n; i++)
		w[i] = read();

	for (int i = 1; i <= n; i++)
		in[i] = (i - 1) / cnt + 1;

	for (int i = 1; i <= n; i++) {
		opt = read();
		a = read();
		b = read();
		c = read();

		if (opt == 0)
			add(a, b, c);
		else
			printf("%d\n", query(b));
	}
}
//1.l和r在同一个块内，那么只需要暴力的修改l到r便可
//2.l和r不在同一个块，那么要分别对l和r所在的块进行修改
//3.这一种是第2种的一个分支情况，l和r之间还有很多个块，因为这些块都是被整体修改，所以直接打到标记

分块2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4 + 3;
vector<int> blo[505];
int w[maxn], in[maxn], addtag[maxn];
int n, opt, a, b, c, cnt;
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
inline void resort(int x) {
	blo[x].clear();

	for (int i = (x - 1) * cnt + 1; i <= x * cnt; i++)
		blo[x].push_back(w[i]);

	sort(blo[x].begin(), blo[x].end());
}
inline void add(int l, int r, int x) {
	for (int i = l; i <= min(in[l]*cnt, r); i++)
		w[i] += x;

	resort(in[l]);

	if (in[l] != in[r])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++)
			w[i] += x;

	resort(in[r]);

	for (int i = in[l] + 1; i < in[r]; i++)
		addtag[i] += x;
}
inline int query(int l, int r, int x) {
	int ans1 = 0;

	for (int i = l; i <= min(r, in[l]*cnt); i++)
		if (w[i] + addtag[in[i]] < x)
			ans1++;

	if (in[l] != in[r])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++)
			if (w[i] + addtag[in[i]] < x)
				ans1++;

	for (int i = in[l] + 1; i < in[r]; i++) {
		int s = x - addtag[i];
		ans1 += lower_bound(blo[i].begin(), blo[i].end(), s) - blo[i].begin();
	}

	return ans1;
}
int main() {
	n = read();
	cnt = sqrt(n);

	for (int i = 1; i <= n; i++)
		w[i] = read();

	for (int i = 1; i <= n; i++) {
		in[i] = (i - 1) / cnt + 1;
		blo[in[i]].push_back(w[i]);
	}

	for (int i = 1; i <= in[n]; i++)
		sort(blo[i].begin(), blo[i].end());

	for (int i = 1; i <= n; i++) {
		opt = read();
		a = read();
		b = read();
		c = read();

		if (opt == 0)
			add(a, b, c);
		else
			printf("%d\n", query(a, b, c * c));
	}

	return 0;
}
//添加过程同分块1
//二分查找来找到第一个大于给定数值的数的位置，然后就可以算出一个块内有多少数是小于给定值的

分块3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 3;
set<int> blo[1005];
int n, opt, a, b, c, cnt;
int w[maxn], addtag[1005], in[maxn];
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
inline void add(int l, int r, int x) {
	for (int i = l; i <= min(r, in[l]*cnt); i++) {
		blo[in[l]].erase(w[i]);
		w[i] += x;
		blo[in[l]].insert(w[i]);
	}

	if (in[l] != in[r])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++) {
			blo[in[r]].erase(w[i]);
			w[i] += x;
			blo[in[r]].insert(w[i]);
		}

	for (int i = in[l] + 1; i < in[r]; i++)
		addtag[i] += x;
}
inline int query(int l, int r, int x) {
	int ans = -1;

	for (int i = l; i <= min(in[l]*cnt, r); i++)
		if (w[i] + addtag[in[i]] < x)
			ans = max(ans, w[i] + addtag[in[i]]);

	if (in[l] != in[r])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++)
			if (w[i] + addtag[in[i]] < x)
				ans = max(ans, w[i] + addtag[in[i]]);

	for (int i = in[l] + 1; i < in[r]; i++) {
		int s = x - addtag[i];
		set<int>::iterator it = blo[i].lower_bound(s);

		if (it == blo[i].begin())
			continue;

		--it;
		ans = max(ans, *it + addtag[i]);
	}

	return ans;
}
int main() {
	n = read();
	cnt = 1000;

	for (int i = 1; i <= n; i++)
		w[i] = read();

	for (int i = 1; i <= n; i++) {
		in[i] = (i - 1) / cnt + 1;
		blo[in[i]].insert(w[i]);
	}

	for (int i = 1; i <= n; i++) {
		opt = read();
		a = read();
		b = read();
		c = read();

		if (opt == 0)
			add(a, b, c);
		else
			printf("%d\n", query(a, b, c));
	}

	return 0;
}
//添加过程相同
//维护一个有序集合set，前驱查找用迭代器， 二分查找x（因为set是有序的），如果x=l输出-1

分块4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4 + 3;
int n, cnt, opt, l, r, k;
int in[maxn], arr[maxn], addtag[500], sum[500];
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
inline void add(int l, int r, int k) {
	for (int i = l; i <= min(r, in[l]*cnt); i++) {
		arr[i] += k;
		sum[in[i]] += k;
	}

	if (in[l] != in[r]) {
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++) {
			arr[i] += k;
			sum[in[i]] += k;
		}
	}

	for (int i = in[l] + 1; i < in[r]; i++)
		addtag[i] += k;
}
inline int query(int l, int r, int modd) {
	int ans = 0;

	for (int i = l; i <= min(r, in[l]*cnt); i++)
		ans = arr[i] % modd + addtag[in[i]] % modd + ans % modd;

	if (in[l] != in[r])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++)
			ans = arr[i] % modd + addtag[in[i]] % modd + ans % modd;

	for (int i = in[l] + 1; i < in[r]; i++)
		ans = addtag[i] % modd * cnt % modd + sum[i] % modd + ans % modd;

	return ans % modd;
}
int main() {
	n = read();
	cnt = sqrt(n);

	for (int i = 1; i <= n; i++) {
		arr[i] = read();
		in[i] = (i - 1) / cnt + 1;
		sum[in[i]] += arr[i];
	}

	for (int i = 1; i <= n; i++) {
		opt = read();
		l = read();
		r = read();
		k = read();

		if (opt == 0)
			add(l, r, k);
		else
			printf("%d\n", query(l, r, k + 1));
	}
}
//添加同上
//每一个块内都维护一个sum，表示这个块内所有元素的和
//在进行修改区间两端的两个特殊的块的时候修改一个加一个
//到最后查询的时候sum+addtag*cnt，cnt表示块的大小

分块5

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4 + 3;
int n, cnt, opt, l, r, k;
int in[maxn], arr[maxn], sum[500];
bool flag[500];
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
inline void solve_sqrt(int x) {
	if (flag[x])
		return ;

	flag[x] = 1;
	sum[x] = 0;

	for (int i = (x - 1) * cnt + 1; i <= x * cnt; i++) {
		arr[i] = sqrt(arr[i]);
		sum[x] += arr[i];

		if (arr[i] > 1)
			flag[x] = 0;
	}
}
inline void update(int l, int r) {
	for (int i = l; i <= min(r, in[l]*cnt); i++) {
		sum[in[i]] -= arr[i];
		arr[i] = sqrt(arr[i]);
		sum[in[i]] += arr[i];
	}

	if (in[l] != in[r]) {
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++) {
			sum[in[i]] -= arr[i];
			arr[i] = sqrt(arr[i]);
			sum[in[i]] += arr[i];
		}
	}

	for (int i = in[l] + 1; i < in[r]; i++)
		solve_sqrt(i);
}
inline int query(int l, int r) {
	int ans = 0;

	for (int i = l; i <= min(in[l]*cnt, r); i++)
		ans += arr[i];

	if (in[r] != in[l])
		for (int i = (in[r] - 1) * cnt + 1; i <= r; i++)
			ans += arr[i];

	for (int i = in[l] + 1; i < in[r]; i++)
		ans += sum[i];

	return ans;
}
int main() {
	n = read();
	cnt = sqrt(n);

	for (int i = 1; i <= n; i++) {
		arr[i] = read();
		in[i] = (i - 1) / cnt + 1;
	}

	for (int i = 1; i <= n; i++)
		sum[in[i]] += arr[i];

	for (int i = 1; i <= n; i++) {
		opt = read();
		l = read();
		r = read();
		k = read();

		if (opt == 0)
			update(l, r);
		else
			printf("%d\n", query(l, r));
	}
}
//一段区间进行至多5次区间开方就会变成1或者0（上网是个好东西）
//只需要暴力的对区间进行修改
//原因：1和0开方后还是本身，所以对于已经全部变为1或者0的区间就不必再开方了

分块6

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
int n, d, nn, opt, l, r, c;
int a[MAXN << 1];
vector<int> v[1005];
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
inline void mer() {                                     //把所有元素还原到a数组中
	n = 0;

	for (int i = 1; i <= d + 1; i++) {
		if (v[i].empty())
			break;

		for (int j = 0; j < v[i].size(); j++)
			a[++n] = v[i][j];

		v[i].clear();
	}
}
inline void div() {                                     //把a数组元素分配到各个块中
	d = sqrt(n);

	for (int i = 1; i <= n; i++)
		v[(i - 1) / d + 1].push_back(a[i]);
}
inline int Get(int wh) {
	for (int i = 1; i <= d + 1; i++) {
		if (wh > v[i].size())
			wh -= v[i].size();
		else
			return v[i][wh - 1];
	}
}
inline void Ins(int wh, int x) {
	for (int i = 1; i <= d + 1; i++) {
		if (wh > v[i].size())
			wh -= v[i].size();
		else {
			v[i].insert(v[i].begin() + wh - 1, x);       //插入

			if (v[i].size() > 10 * d)
				mer(), div();                               //重排

			return ;
		}
	}
}
int main() {
	n = read();

	for (int i = 1; i <= n; i++)
		a[i] = read();

	div();
	nn = n;

	for (int i = 1; i <= nn; i++) {
		opt = read();
		l = read();
		r = read();
		c = read();

		if (!opt)
			Ins(l, r);
		else
			cout << Get(r) << endl;
	}

	return 0;
}
//经典快读~~~
//单点插入使用vector(insert)非常方便，但要注意插入后每个块的长度
//如果多次插入同一块，会导致块过长，时间复杂度过高，失去分块的意义
//所以当一个块的元素量是原来的10倍时，就要重新分块

分块7

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 10007;
ll n, a[maxn], pos[maxn], m[maxn], sum[maxn], block;
inline ll read() {                                          //经典快读
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
void reset(int x) {                                         //更新不完整块中的每个值
	ll p = pos[x];

	for (int i = (p - 1) * block + 1; i <= min(p * block, n); i++)
		a[i] = (m[p] * a[i] + sum[p]) % mod;

	m[p] = 1;
	sum[p] = 0;                                             //更新该块的sum,m
}
void update(int l, int r, int c, int opt) {                 //加和乘
	reset(l);                                               //更新左边不完整块

	for (int i = l; i <= min(pos[l]*block, (ll)r); i++) {   //暴力加或乘
		if (opt == 0)
			a[i] = (a[i] + c) % mod;
		else
			a[i] = (a[i] * c) % mod;
	}

	if (pos[l] != pos[r]) {
		reset(r);                                           //更新右边不完整块

		for (int i = (pos[r] - 1) * block + 1; i <= r; i++) //暴力加或乘
			if (opt == 0)
				a[i] = (a[i] + c) % mod;
			else
				a[i] = (a[i] * c) % mod;
	}

	for (int i = pos[l] + 1; i <= pos[r] - 1; i++)          //完整块处理
		if (opt == 0)
			sum[i] = (sum[i] + c) % mod;                    //加
		else {                                              //乘
			sum[i] = (sum[i] * c) % mod;                    //sum要乘  关键
			m[i] = (m[i] * c) % mod;                        //系数要乘
		}
}
int main() {
	n = read();
	block = sqrt(n);

	for (int i = 1; i <= n; i++) {
		a[i] = read();
		a[i] %= mod;
		pos[i] = (i - 1) / block + 1;
		m[pos[i]] = 1;                                      //系数初始化为1
	}

	int opt, l, r, c;
	memset(sum, 0, sizeof(sum));

	for (int i = 1; i <= n; i++) {
		opt = read();
		l = read();
		r = read();
		c = read();

		if (opt == 0 || opt == 1)
			update(l, r, c, opt);
		else
			printf("%lld\n", (a[r]*m[pos[r]] + sum[pos[r]]) % mod);
	}

	return 0;
}
//加法操作会影响乘法操作的值
//用sum[]存整块的加数，m[]存整块的乘的系数。容易知道，乘的时候sum也要乘
//数值x第一个操作加c1,数值变成了x+c1。用sum[]存c1
//第二个操作乘以c2，数值变成(x+c1)*c2,可以理解为c2*x+c1*c2，用sum[]存c1*c2,m[]存c2
//注意不完整块的处理，每次不完整的块要更新a[]的值，因为可能前面的操作把它当成完整块处理
//不完整块要暴力加，所以要变成最新的值才可以暴力加，只有始终为完整块的数可以不用更新

分块8

#include <bits/stdc++.h>
#define MAXN 100005
#define ll long long
using namespace std;
int n, d;
int a[MAXN], b[MAXN], f[500];
bool v[500];
inline ll read() {                                          //经典快读
	ll x = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;

		ch = getchar();
	}

	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return x * f;
}
int FF(int x) {   //取出x位置的值
	return v[b[x]] ? f[b[x]] : a[x];
}
int fun(int l, int r, int c) {   //计数&修改
	int ans(0);

	for (int i = l; i <= r && i <= n; ++i)
		ans += FF(i) == c, a[i] = c;

	return ans;
}
int Get(int l, int r, int c) {
	int ans(0);

	if (b[l] == b[r]) {
		if (v[b[l]] && f[b[l]] == c)
			return r - l + 1;

		if (v[b[l]]) {
			fun((b[l] - 1) * d + 1, l - 1, f[b[l]]);
			fun(r + 1, b[l] * d, f[b[l]]);
		}

		ans = fun(l, r, c);
		v[b[l]] = 0;
		return ans;
	}

	if (v[b[l]])
		fun((b[l] - 1) * d + 1, l - 1, f[b[l]]);

	ans += fun(l, b[l] * d, c);
	v[b[l]] = 0;

	if (v[b[r]])
		fun(r + 1, min(b[r] * d, n), f[b[r]]);

	ans += fun((b[r] - 1) * d + 1, r, c);
	v[b[r]] = 0;

	for (int i = b[l] + 1; i <= b[r] - 1; ++i) {
		if (!v[i]) {
			for (int j = (i - 1) * d + 1; b[j] == i; ++j) {
				ans += a[j] == c;
				a[j] = c;
			}

			v[i] = 1;
			f[i] = c;
		} else {
			if (f[i] == c)
				ans += d;
			else
				f[i] = c;
		}
	}
	return ans;
}
int main() {
	n = read();
	d = (int)sqrt(n);

	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		b[i] = (i - 1) / d + 1;
	}

	for (int i = 1; i <= n; ++i) {
		int l, r, c;
		l = read();
		r = read();
		c = read();
		printf("%d\n", Get(l, r, c));
	}

	return 0;
}
//查询+修改不过多赘述

分块9

#include <bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
#define D(i,a,b) for(int i=a;i>=b;i--)
#define ms(i,a)  memset(a,i,sizeof(a))
#define st(x)   ( (x-1)*B+1)
#define ed(x)   ( min(n, x*B))
#define bl(x)   ( (x-1)/B+1)
#define sum(x)  ( (n-1)/B+1)
using namespace std;
int inline read() {
	int x = 0 ;
	char c = getchar();

	while (c < '0' || c > '9')
		c = getchar();

	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();

	return x;
}
int const maxn = 100003;
int n, m, B, cnt[maxn][401], v[401][401], num[401][401];
int a[maxn], b[maxn], c[maxn], tmp[maxn];
int query(int l, int r) {
	int x = bl(l);
	int y = bl(r);
	int V, NUM = 0;
	if (x + 1 <= y - 1) {
		V = v[x + 1][y - 1];
		NUM = num[x + 1][y - 1];
	}
	int s, e;
	tmp[0] = 0;
	if (x == y) {
		F(i, l, r) {
			tmp[++tmp[0]] = a[i];
			c[a[i]]++;
		}
	} else {
		s = l;
		e = ed(x);
		F(i, s, e) {
			tmp[++tmp[0]] = a[i];
			c[a[i]]++;
		}
		s = st(y);
		e = r;
		F(i, s, e) {
			tmp[++tmp[0]] = a[i];
			c[a[i]]++;
		}
	}
	F(i, 1, tmp[0]) {
		int t = x + 1 <= y - 1 ?  cnt[tmp[i]][y - 1] - cnt[tmp[i]][x] : 0;

		if (c[tmp[i]] + t > NUM || (c[tmp[i]] + t == NUM  && V > tmp[i])) {
			V = tmp[i];
			NUM = c[tmp[i]] + t;
		}
	}
	F(i, 1, tmp[0])
	c[tmp[i]] = 0;
	return V;
}
int main() {
	n = read();
	m = n;
	F(i, 1, n)
	a[i] = b[i] = read();
	sort(b + 1, b + n + 1);
	int k = unique(b + 1, b + n + 1) - b - 1;
	F(i, 1, n)
	a[i] = lower_bound(b + 1, b + k + 1, a[i]) - b;
	B = (int)sqrt(n);
	int t = sum(n);
	F(i, 1, t) {
		ms(0, c);
		int s = st(i);
		int e = ed(i);
		F(j, s, e)
		c[a[j]]++;
		F(j, 1, k)
		cnt[j][i] = cnt[j][i - 1] + c[j];
	}
	F(i, 1, t) {
		ms(0, c);
		F(j, i, t) {
			int V = v[i][j - 1];
			int NUM = num[i][j - 1];
			int s = st(j);
			int e = ed(j);
			F(p, s, e) {
				c[a[p]]++ ;
				if (c[a[p]] > NUM || (NUM == c[a[p]] && a[p] < V)) {
					V = a[p];
					NUM = c[a[p]];
				}
			}
			v[i][j] = V;
			num[i][j] = NUM;
		}
	}
	int x = 0;
	ms(0, c);
	while (m--) {
		int l = read();
		int r = read();
		x = 1;
		if (l > r)
			swap(l, r);
		printf("%d\n", x = b[query(l, r)]);
	}
	return 0;
}
//纯查询众数，也就花了1天

本栏目推荐文章
• P5161 WD与数列
• 数列选讲
• 平方数列求和的一种非正常求法
• loj 数列分块
• P3228 [HNOI2013] 数列
• 数列分块入门1-9
• [蓝桥杯 2023 国 B] 合并数列
• 数列操作
• 等比数列的判定
• 数列操作（加强版）

数列数列iii 数列01 数列offer 数列的极限 数列p4000 数列p1851 数列section 数列p1438 数列 极限 等差 数列