数列分块入门 2

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目

题目

思路

此题用分块。

要求区间内小于$c * c$的数的个数，区间加减。

看到n的范围都不超过50000，可以直接将每个块都快速排序，查询时用二分就好了。

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+7,maxm=500;
int n,m,num,a[maxn],b[maxn],l[maxm],r[maxm],pos[maxn],add[maxm];
void build(){
	num=n/m;if(n%m) num++;
	for(int i=1;i<=num;i++)
	l[i]=(i-1)*m+1,r[i]=i*m; r[num]=n;
	for(int i=1;i<=num;i++) sort(b+l[i],b+r[i]+1);
}
void change(int L,int R,int K){
	int p=pos[L],q=pos[R];
	if(p==q) {
		for(int i=L;i<=R;i++) a[i]+=K;
		for(int i=l[p];i<=r[p];i++) b[i]=a[i];
		sort(b+l[p],b+r[p]+1);
	}
	else {
		for(int i=L;i<=r[p];i++) a[i]+=K;
		for(int i=l[p];i<=r[p];i++) b[i]=a[i];
		sort(b+l[p],b+r[p]+1);
		for(int i=p+1;i<=q-1;i++) add[i]+=K;
		for(int i=l[q];i<=R;i++) a[i]+=K;
		for(int i=l[q];i<=r[q];i++) b[i]=a[i];
		sort(b+l[q],b+r[q]+1);
	}
}
int ask(int L,int R,int C){
	int ans=0,p=pos[L],q=pos[R],k;
	if(p==q){
		for(int i=L;i<=R;i++)
		if(a[i]+add[p]<C) ans++;
	}
	else {
		for(int i=L;i<=r[p];i++)
			if(a[i]+add[p]<C) ans++;
		for(int i=l[q];i<=R;i++)
			if(a[i]+add[q]<C) ans++;
		for(int i=p+1;i<=q-1;i++){
			k=lower_bound(b+l[i],b+r[i]+1,C-add[i])-b;
			ans+=k-l[i];
		}
	}
	return ans;
}
signed main(){
	int x,y,z,t;
//	freopen("a1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%lld",&n);m=sqrt(n);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]),b[i]=a[i],pos[i]=(i-1)/m+1;
	build();
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&t,&x,&y,&z);
		if(t) printf("%lld\n",ask(x,y,z*z));
		else change(x,y,z);
	}
	return 0;
}

总结

分块系列第2题我就不会了，真菜。

好吧，这题暴力的没边（可是蒟蒻还是不会）

就真的是怎么暴力怎么来，分块还加个快排。

注意点就是要分清a[]与b[]。

结束，撒花！