分块入门

分块入门

鸽子给了个链接https://www.luogu.com.cn/paste/btx82uof

稍微总结下

数列分块入门 2（区间加，区间求和）

题目链接

题目描述

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

输入格式

第一行输入一个数字 。

第二行输入 个数字，第 个数字为 ，以空格隔开。

接下来输入 行询问，每行输入四个数字 op、l、r、c，以空格隔开。

若op==1 ，表示将位于[l,r] 的之间的数字都加c 。

若op==2 ，表示询问 [l,r]中，小于c 的数字的个数。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例输入

1
2
3
4
5
6
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

样例输出

1
2
3
3
0
2
1
1 2 3 2

样例输出

1
2
3
3
0
2

数据范围与提示

1<=n<=50000,-231<ans,ai<231

思路

对一些区间操作我们可以将线段先分块再暴力处理零散块+排序二分处理整块

算块长我们根据复杂度来做，设块长为b

对于操作1我们O(\(b+\frac{n}{b}\))可以解决

对于操作2我们O(\(b+\frac{n}{b}logb\))

很显然操作2的复杂度大于操作1，因此我们用操作2来计算块长

b可以看作是n的多项式（poly n），因此\(logb\)可以看作是\(logn\)加一个常数，也就是\(logn\)

所以我们利用均值不等式 \[ b+\frac{n}{b}logn\ge2\sqrt{nlogn} \\ 等号在b=\frac{n}{b}logn时取到，此时b=\sqrt{nlogn} \] 因此我们算出块长b=\(\sqrt{nlogn}\)，复杂度为O(\(m\sqrt{nlogn}\))

代码

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
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cn.tie(0);cout.tie(0);

#define bi(x) (((x)-1)/block)//块序号
#define sb(x) ((x)*block+1)//每块开始位置 strat of block
#define eb(x) min(((x)+1)*block,n)//每块结束位置 end of block
//基本是分块必备了
const int N=/*1e4*/5e4,block=888;
int a[N],id[N],tag[bi(N)+10];
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		id[i]=i;
	}
	for(int i=bi(1); i<=bi(n); i++)sort(id+sb(i),id+eb(i)+1,[&](int x,int y) {
		return a[x]<a[y];
	});
	int op,l,r,c;
	for(int k=1; k<=n; k++) {
		cin>>op>>l>>r>>c;
		int lb=bi(l),rb=bi(r);
		if(op==0) {
			if(lb==rb) {
				for(int i=l; i<=r; i++)a[i]+=c;
				sort(id+sb(lb),id+eb(lb)+1,[&](int x,int y) {
					return a[x]<a[y];
				});//排序，但是有些题会被卡常
				continue;
			}
			for(int i=lb+1; i<=rb-1; i++)tag[i]+=c;
			for(int i=l; i<=eb(lb); i++)a[i]+=c;
			for(int i=sb(rb); i<=r; i++)a[i]+=c;
			sort(id+sb(lb),id+eb(lb)+1,[&](int x,int y) {
				return a[x]<a[y];
			});
			sort(id+sb(rb),id+eb(rb)+1,[&](int x,int y) {
				return a[x]<a[y];
			});
		} else {
			int ans=0;
			if(lb==rb) {
				for(int i=l; i<=r; i++)ans+=a[i]+tag[lb]<c*c;
			} else {
				for(int i=lb+1; i<=rb-1; i++) {
					int l=sb(i),r=eb(i);
					if(a[id[l]]+tag[i]>=c*c)continue;
					while(l<r) {//二分查找每块里小于c的个数
						int mid=(l+r+1)>>1;
						if(a[id[mid]]+tag[i]<c*c)l=mid;
						else r=mid-1;
					}
					ans+=l-sb(i)+1;
				}
				for(int i=l; i<=eb(lb); i++)ans+=a[i]+tag[lb]<c*c;
				for(int i=sb(rb); i<=r; i++)ans+=a[i]+tag[rb]<c*c;
			}
			cout<<ans<<'\n';
		}

	}
	return 0;
}

[Ynoi2017] 由乃打扑克（区间加，区间查询）

题目链接

题目描述

给你一个长为 n 的序列 a，需要支持 m 次操作，操作有两种：

  1. 查询区间 [l,r]的第 k 小值。
  2. 区间 [l,r] 加上 k。

输入格式

一行两个整数 n，m。

接下来一行 n 个整数， 第 i 个整数表示 ai。

接下来 mm 行，每行四个数 opt,l,r,k，其中 opt 代表是哪种操作。

输出格式

对于每个询问输出一个数表示答案，如果无解输出 −1。

输入输出样例

输入 #1

1
2
3
1 1
1
1 1 1 1

输出 #1

1
1

思路

区间加和上题一样，区间查询我们运用二分答案+上面的区间求和来做，二分答案，求区间和，如果有k-1个比答案小的数就是最终答案，我们通过二分来逼近这个答案。这样做之后我们就把区间查询问题转化成了区间求和。

同样的，我们来算一下块长b

查询零散块为O(\(blogn\))，先归并零散块再排序可以优化为O(\(b+log^2n\))

查询整块为O(\(logn\frac{n}{b}logb\))=O(\(\frac{n}{b}log^2n\)) \[ b+log^2n+\frac{n}{b}log^2n\ge2\sqrt{n}logn+log^2n\\ 在b=\frac{n}{b}log^2n时取等，此时b=\sqrt{n}logn \]

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;
#define bi(x) (((x)-1)/block)
#define sb(x) ((x)*block+1)
#define eb(x) min(((x)+1)*block,n)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
const int N=/*1e4*/1e5+10,block=1000;
inline long long read() {
	long long s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
//快写
inline void out(long long a) {
	if(a>=10)out(a/10);
	putchar(a%10+'0');
}
int a[N],id[N],tmp[N],e,tag[bi(N)+10],n,m,buf1[N],buf2[N];
void add(int l,int r,int c) {
	int lb=bi(l),rb=bi(r);
	if(lb==rb) {
		for(int i=l; i<=r; i++)a[i]+=c;
		/*sort(id+sb(lb),id+eb(lb)+1,[&](int x,int y) {
			return a[x]<a[y];
		});*/
		int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
		for(int i=sb(lb); i<=eb(lb); i++)
			if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
			else buf2[++ e2] = id[i];
		for(int i=sb(lb); i<=eb(lb); i++)
			if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) id[i] = buf1[p1 ++];
			else id[i] = buf2[p2 ++];
		return;
	}
	for(int i=lb+1; i<=rb-1; i++)tag[i]+=c;
	for(int i=l; i<=eb(lb); i++)a[i]+=c;
	for(int i=sb(rb); i<=r; i++)a[i]+=c;
	
	int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
	for(int i=sb(lb); i<=eb(lb); i++)
		if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
		else buf2[++ e2] = id[i];
	for(int i=sb(lb); i<=eb(lb); i++)
		if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) id[i] = buf1[p1 ++];
		else id[i] = buf2[p2 ++];
	
	e1 = -1, e2 = -1, p1 = 0, p2 = 0;
	for(int i=sb(rb); i<=eb(rb); i++)
		if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
		else buf2[++ e2] = id[i];
	for(int i=sb(rb); i<=eb(rb); i++)
		if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) id[i] = buf1[p1 ++];
		else id[i] = buf2[p2 ++];
	/*sort(id+sb(lb),id+eb(lb)+1,[&](int x,int y) {
		return a[x]<a[y];
	});
	sort(id+sb(rb),id+eb(rb)+1,[&](int x,int y) {
		return a[x]<a[y];
	});*/
}
void init(int l,int r) {
	int lb=bi(l),rb=bi(r);
	e=-1;
	if(lb==rb) {
		for(int i=sb(lb);i<=eb(lb);i++) if(id[i] >= l && id[i] <= r) tmp[++ e] = id[i];
	} else {
		/*for(int i=sb(lb); i<=eb(lb); i++)if(id[i]>=l&&id[i]<=r)tmp[++e]=id[i];
		for(int i=sb(rb); i<=eb(rb); i++)if(id[i]>=l&&id[i]<=r)tmp[++e]=id[i];
		sort(tmp,tmp+e+1,[&](int x,int y) {
			return a[x]<a[y];
		});*/
		int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
		for(int i=sb(lb);i<=eb(lb);i++) if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
		for(int i=sb(rb);i<=eb(rb);i++) if(id[i] >= l && id[i] <= r) buf2[++ e2] = id[i];

		while(p1 <= e1 || p2 <= e2) {
			if(p2 > e2 || p1 <= e1 && a[buf1[p1]] + tag[lb] < a[buf2[p2]] + tag[rb]) tmp[++ e] = buf1[p1 ++];
			else tmp[++ e] = buf2[p2 ++];
		}
	}
}
int cal(int l,int r,int c) {
	int lb = bi(l), rb = bi(r);
	int ans = 0;
	for(int i= lb + 1;i<= rb - 1;i++) {
		int l = sb(i), r = eb(i);
		if(a[id[l]] + tag[i] >= c) continue;
		while(l < r) {
			int mid = (l + r + 1) >> 1;
			if(a[id[mid]] + tag[i] < c) l = mid;
			else r = mid - 1;
		}
		ans += l - sb(i) + 1;
	}
	if(~e && a[tmp[0]] + tag[bi(tmp[0])] < c) {
		int l = 0, r = e;
		while(l < r) {
			int mid = (l + r + 1) >> 1;
			if(a[tmp[mid]] + tag[bi(tmp[mid])] < c) l = mid;
			else r = mid - 1;
		}
		ans += l + 1;
	}
	return ans;
}
signed main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++) {
		//scanf("%d",&a[i]);
		a[i]=read();
		id[i]=i;
	}
	for(int i=bi(1); i<=bi(n); i++)sort(id+sb(i),id+eb(i)+1,[&](int x,int y) {
		return a[x]<a[y];
	});
	for(int k=1; k<=m; k++) {
		int op,l,r,c;
		op=read(),l=read(),r=read(),c=read();
		if(op==2)add(l,r,c);
		else {
			if(c>r-l+1)printf("-1\n");
			else {
				int ll=-2e9,rr=2e9;
				init(l,r);
				while(ll<rr) {
					int mid=(ll+rr+1)>>1;
					if(cal(l,r,mid)<c)ll=mid;
					else rr=mid-1;
				}
				printf("%lld\n", ll);
			}
		}
	}
	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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#define int long long
#define bi(x) (((x)-1)/block)//块序号
#define sb(x) ((x)*block+1)//每块开始位置 strat of block
#define eb(x) min(((x)+1)*block,n) //每块结束位置 end of block
const int N=/*1e4*/1e5+10,block=1000;
struct Block {
	//基本是分块必备了

	int id[N],tmp[N],e,tag[bi(N)+10],buf1[N],buf2[N],a[N],n,m;
	Block() {
		e=-1;
		memset(id,0,sizeof(id));
		memset(tag,0,sizeof(tag));
		memset(a,0,sizeof(a));
		memset(tmp,0,sizeof(tmp));
		memset(buf1,0,sizeof(buf1));
		memset(buf2,0,sizeof(buf2));
	}
	void add(int l,int r,int c) {
		int lb=bi(l),rb=bi(r);
		if(lb==rb) {
			for(int i=l; i<=r; i++)a[i]+=c;
			/*sort(id+sb(lb),id+eb(lb)+1,[&](int x,int y) {
				return a[x]<a[y];
			});*/
			int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
			for(int i=sb(lb); i<=eb(lb); i++)
				if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
				else buf2[++ e2] = id[i];
			for(int i=sb(lb); i<=eb(lb); i++)
				if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) id[i] = buf1[p1 ++];
				else id[i] = buf2[p2 ++];
			return;
		}
		for(int i=lb+1; i<=rb-1; i++)tag[i]+=c;
		for(int i=l; i<=eb(lb); i++)a[i]+=c;
		for(int i=sb(rb); i<=r; i++)a[i]+=c;

		int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
		for(int i=sb(lb); i<=eb(lb); i++)
			if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
			else buf2[++ e2] = id[i];
		for(int i=sb(lb); i<=eb(lb); i++)
			if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) id[i] = buf1[p1 ++];
			else id[i] = buf2[p2 ++];

		e1 = -1, e2 = -1, p1 = 0, p2 = 0;
		for(int i=sb(rb); i<=eb(rb); i++)
			if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
			else buf2[++ e2] = id[i];
		for(int i=sb(rb); i<=eb(rb); i++)
			if(p2 > e2 || p1 <= e1 && a[buf1[p1]] < a[buf2[p2]]) id[i] = buf1[p1 ++];
			else id[i] = buf2[p2 ++];
		/*sort(id+sb(lb),id+eb(lb)+1,[&](int x,int y) {
			return a[x]<a[y];
		});
		sort(id+sb(rb),id+eb(rb)+1,[&](int x,int y) {
			return a[x]<a[y];
		});*/
	}
	void init(int l,int r) {
		int lb=bi(l),rb=bi(r);
		e=-1;
		if(lb==rb) {
			for(int i=sb(lb); i<=eb(lb); i++) if(id[i] >= l && id[i] <= r) tmp[++ e] = id[i];
		} else {
			int e1 = -1, e2 = -1, p1 = 0, p2 = 0;
			for(int i=sb(lb); i<=eb(lb); i++) if(id[i] >= l && id[i] <= r) buf1[++ e1] = id[i];
			for(int i=sb(rb); i<=eb(rb); i++) if(id[i] >= l && id[i] <= r) buf2[++ e2] = id[i];

			while(p1 <= e1 || p2 <= e2) {
				if(p2 > e2 || p1 <= e1 && a[buf1[p1]] + tag[lb] < a[buf2[p2]] + tag[rb]) tmp[++ e] = buf1[p1 ++];
				else tmp[++ e] = buf2[p2 ++];
			}
		}
	}
	int cal(int l,int r,int c) {
		int lb = bi(l), rb = bi(r);
		int ans = 0;
		for(int i= lb + 1; i<= rb - 1; i++) {
			int l = sb(i), r = eb(i);
			if(a[id[l]] + tag[i] >= c) continue;
			while(l < r) {
				int mid = (l + r + 1) >> 1;
				if(a[id[mid]] + tag[i] < c) l = mid;
				else r = mid - 1;
			}
			ans += l - sb(i) + 1;
		}
		if(~e && a[tmp[0]] + tag[bi(tmp[0])] < c) {
			int l = 0, r = e;
			while(l < r) {
				int mid = (l + r + 1) >> 1;
				if(a[tmp[mid]] + tag[bi(tmp[mid])] < c) l = mid;
				else r = mid - 1;
			}
			ans += l + 1;
		}
		return ans;
	}
	long long find_kth(int l,int r,int c) {
		if(c>r-l+1)return -1;
		else {
			int ll=-2e9,rr=2e9;
			init(l,r);
			while(ll<rr) {
				int mid=(ll+rr+1)>>1;
				if(cal(l,r,mid)<c)ll=mid;
				else rr=mid-1;
			}
			return ll;
		}
	}
	void id_sort() {
		for(int i=bi(1); i<=bi(n); i++)sort(id+sb(i),id+eb(i)+1,[&](int x,int y) {
			return a[x]<a[y];
		});
	}
}
算法 笔记
分块 数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！