分块 学习笔记

众所周知，分块是一种优雅的暴力，一般来说复杂度带根号。由于本人对分块理解的还不是很深，如何算块取多长是最优的暂且不会，这篇文章中的块长都设为 $\sqrt{n}$。

具体操作也很简单，先将原序列分成 $\sqrt{n}$ 个块，大块$($即整块$)$打标记$($类似于线段树$)$，小块暴力修改。由于给出的一段区间，最多会包含 $2$ 个边上的小块，最多会包含 $\sqrt{n}$ 个大块。小块的操作是 $O(\sqrt{n})$，大块打标记是 $O(1)$，这么算下来大块和小块的复杂度都是 $O(\sqrt{n})$，所以可以说复杂度就是 $O(\sqrt{n})$。当然在块中，也可以加入数据结构。

数列分块入门 $1$

给出一个长度为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，单点查值。

这就是最基础的分块，区间加法像上文所说，大块打标记，小块暴力修改。最后查答案的时候别忘了把标记给加上。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int M = 5e4+10;
int n,B;
int a[M],tag[M];
inline void modify(int l,int r,int w){
   
	int idl = l/B,idr = r/B;
	if(idl == idr) rep(i,l,r) a[i] += w;
	else{
   
		rep(i,l,(idl+1)*B-1) a[i] += w;
		rep(id,idl+1,idr-1) tag[id] += w;
		rep(i,idr*B,r) a[i] += w;
	}
}
signed main(){
   
	n = read();
	B = sqrt(n);
	rep(i,1,n) a[i] = read();
	while(n--){
   
		int op = read(),l = read(),r = read(),c = read();
		if(op == 0)	modify(l,r,c);
		else printf("%d\n",a[r]+tag[r/B]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

数列分块入门 $2$

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，询问区间内小于某个值 $x$ 的元素个数。

看到询问区间内小于某个元素的个数，可以想到二分。具体的操作就是，每一个块维护一个有序的 $vector$，每次查询直接 $lower$_$bound$ 查答案即可。这里对于大块，同时加上一个数，整体的大小关系不会变，所以直接打上加法标记即可。
对于小块，修改会改变块内相对的大小关系。这是我们暴力将数组加上一个数，然后将这个块维护的 $vector$ 重新排序。这样就能保证每次操作的 $vector$ 都是有序的。每次最多只会这么重构两个小块，所以复杂度是正确的。

#include 
#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
   
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int M = 1e5+10;
int n,B;
int a[M],base[M];
vector<int> v[M];
inline void modify(int l,int r,int w){
   
	int idl = l/B,idr = r/B;
	if(idl == idr){
   
		rep(i,l,r) a[i] += w;
		v[idl].clear();
		rep(i,max(1ll,idl*B),min((idl+1)*B-1,n)) v[idl].push_back(a[i]);
		sort(v[idl].begin(),v[idl].end());
	}
	else{
   
		rep(i,l,(idl+1)*B-1) a[i] += w;
		v[idl].clear();
		rep(i,max(1ll,idl*B),(idl+1)*B-1) v[idl].push_back(a[i]);
		sort(v[idl].begin(),v[idl].end());
		
		rep(id,idl+1,idr-1) base[id] += w;
		
		rep(i,idr*B,r) a[i] += w;
		v[idr].clear();
		rep(i,idr*B,min(n,(idr+1)*B-1)) v[idr].push_back(a[i]);
		sort(v[idr].begin(),v[idr].end());
	}
}
inline int query(int l,int r,int x){
   
	int idl = l/B,idr = r/B;
	int ans = 0;
	if(idl == idr) rep(i,l,r) ans += (a[i] + base[idl] < x);
	else{
   
		rep(i,l,(idl+1)*B-1) ans += (a[i] + base[idl] < x);
		rep(id,idl+1,idr-1) ans += lower_bound(v[id
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63