分块专题2

自用笔记算法

分块专题2

cf 455D

题目要求

题意：给出一个序列，两种操作
1.将区间[l,r]滚动一次 a[l] a[l+1]···a[r]->a[r] a[l]···a[r-1]
2.询问区间[l,r]中值等于k的数有多少个
根据所给公式强制在线

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
deque<int>que[350];
int b[350][maxn];
int n,q;
int val[maxn];
int block,num,belong[maxn],l[maxn],r[maxn];
void build(){
	block=sqrt(n);
    num=n/block;
	if(n%block) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++){
    	for(int j=l[i];j<=r[i];j++){
    		b[i][val[j]]++;
    		que[i].push_back(val[j]);
		}
	}
}
void update(int x,int y){
	if(belong[x]==belong[y]){
		int index=belong[x];
		x-=l[index];
		y-=l[index];
		int temp=que[index][y];
		for(int i=y;i>x;i--) que[index][i]=que[index][i-1];
		que[index][x]=temp;
		return;
	}
	int temp=que[belong[y]][y-l[belong[y]]];
	int temp2=que[belong[x]][r[belong[x]]-l[belong[x]]];
	b[belong[y]][temp]--;
	b[belong[x]][temp2]--;
	for(int i=r[belong[x]];i>x;i--) que[belong[x]][i-l[belong[x]]]=que[belong[x]][i-l[belong[x]]-1];
	que[belong[x]][x-l[belong[x]]]=temp;
	b[belong[x]][temp]++;
	for(int i=belong[x]+1;i<belong[y];i++){
		int tp=temp2;
		b[i][temp2]++;
		temp2=que[i][r[i]-l[i]];
		b[i][temp2]--;
		que[i].pop_back();
		que[i].push_front(tp);
	}
	for(int i=y;i>l[belong[y]];i--) que[belong[y]][i-l[belong[y]]]=que[belong[y]][i-l[belong[y]]-1];
	que[belong[y]][0]=temp2;
	b[belong[y]][temp2]++;
}
int query(int x,int y,int k){
	int ans=0;
	if(belong[x]==belong[y]){
		for(int i=x;i<=y;i++){
			if(que[belong[x]][i-l[belong[x]]]==k) ans++;
		}
		return ans;
	}
	for(int i=x;i<=r[belong[x]];i++){
		if(que[belong[x]][i-l[belong[x]]]==k) ans++;
	}
	for(int i=belong[x]+1;i<belong[y];i++) ans+=b[i][k];
	for(int i=l[belong[y]];i<=y;i++){
		if(que[belong[y]][i-l[belong[y]]]==k) ans++;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&val[i]);
	build();
	int ans=0;
	scanf("%d",&q);
	while(q--){
		int op;
		scanf("%d",&op);
		int x,y;
		scanf("%d%d",&x,&y);
		x=(x+ans-1)%n+1;
		y=(y+ans-1)%n+1;
		if(x>y) swap(x,y);
		if(op==1) update(x,y);
		else{
			int k;
			scanf("%d",&k);
			k=(k+ans-1)%n+1;
			printf("%d\n",ans=query(x,y,k));
		}
	}
	return 0;
}

思路

分块+双段队列模拟
b代表每个块的hash表 que模拟每个块
模拟时注意细节即可 每个块que的下标需要减去左端点l

codeforces 13E

题目要求

有n个弹簧，每次扔个球，这个球可以弹到i+power[i]的位置
然后有两种操作
将第i个位置的弹簧的弹力改为b
将球扔到第i个位置，问这个球最后弹到了哪儿，这个球弹了几次？

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,q,block,num;
int a[maxn],belong[maxn];
int cnt[maxn],End[maxn];
int l[1100],r[1100];
inline LL 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*10+ch-'0';ch=getchar();}
    return x*f;
}
void build(){
	block = sqrt(n);
    num = n/block;
    if(n%block) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
	for(int i=n;i>=1;i--){
		if(a[i]+i>n) cnt[i]=1,End[i]=-1;
		else if(belong[i]==belong[a[i]+i]) cnt[i]=cnt[i+a[i]]+1,End[i]=End[i+a[i]];
		else cnt[i]=1,End[i]=i+a[i];
	}
}
void update(int x,int y){
	a[x]=y;
	for(int i=x;i>=l[belong[x]];i--){
		if(a[i]+i>n) cnt[i]=1,End[i]=-1;
		else if(belong[i]==belong[a[i]+i]) cnt[i]=cnt[i+a[i]]+1,End[i]=End[i+a[i]];
		else cnt[i]=1,End[i]=i+a[i];
	}
}
void solve(int x){
	int ans=0;
	while(1){
		ans+=cnt[x];
		if(End[x]<0) break;
		x=End[x];
	}
	while(1){
		if(x+a[x]>n) break;
		x=x+a[x];
	}
	printf("%d %d\n",x,ans);
}
int main(){
//	freopen("input.txt","r",stdin);
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build();
	while(q--){
		int op; op=read();
		if(op==1){
			int x; x=read();
			solve(x);
		}
		else{
			int x,y;
			x=read(),y=read();
			update(x,y);
		}
	}
	return 0;
}

思路

跟bzoj弹飞绵羊一样 多了一个输出终止位置
这个在solve里暴力一下就好了

codeforces 551E

题目要求

对于给定数列，操作一是把[l,r]区间内的数加x，操作二是求出一个值，该值为数x出现的最右位置减最左位置，若不存在x输出为-1

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 500050
#define LL long long 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	LL v;
	int id;
	bool operator < (const node& x) const{
		if(v==x.v) return id<x.id;
		return v<x.v;
	}
}a[maxn],d[maxn];
int n,q,num,belong[maxn],block,l[maxn],r[maxn];
LL p[maxn];
void build(){
    block=sqrt(n);
    num=n/block;
	if(n%block) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    for(int i=1;i<=n;i++) d[i]=a[i];
    for(int i=1;i<=num;i++) sort(d+l[i],d+r[i]+1);
}
void update(int x,int y,int k){
	if(belong[x]==belong[y]){
		for(int i=x;i<=y;i++) a[i].v+=k;
		for(int i=l[belong[x]];i<=r[belong[x]];i++) d[i]=a[i];
		sort(d+l[belong[x]],d+r[belong[x]]+1);
		return;
	}
	for(int i=x;i<=r[belong[x]];i++) a[i].v+=k;
	for(int i=l[belong[x]];i<=r[belong[x]];i++) d[i]=a[i];
	sort(d+l[belong[x]],d+r[belong[x]]+1);
	for(int i=belong[x]+1;i<belong[y];i++) p[i]+=k;
	for(int i=l[belong[y]];i<=y;i++) a[i].v+=k;
	for(int i=l[belong[y]];i<=r[belong[y]];i++) d[i]=a[i];
	sort(d+l[belong[y]],d+r[belong[y]]+1);
}
int binsearch1(int L,int R,LL x){
    int l=L,r=R;  
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;  
        if(d[mid].v>=x) ans=mid,r=mid-1;
        else l=mid+1;  
    }  
    return d[ans].v==x?d[ans].id:-1;  
}  
int binsearch2(int L,int R,LL x){
    int l=L,r=R;  
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;  
        if(d[mid].v<=x) ans=mid,l=mid+1;  
        else r=mid-1;  
    }  
    return d[ans].v==x?d[ans].id:-1;  
}  
int query(int x){
	int lpos=-1,rpos=-1;
	for(int i=1;i<=num;i++){
		if(lpos==-1) lpos=binsearch1(l[i],r[i],x-p[i]); 
		rpos=max(rpos,binsearch2(l[i],r[i],x-p[i]));
	}	
	if(lpos==-1 || rpos==-1) return -1;
	return rpos-lpos;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].v);
		a[i].id=i;
	}
	build();
	while(q--){
		int op;
		scanf("%d",&op);
		if(op==1){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			update(x,y,z);
		}
		else{
			int x;
			scanf("%d",&x);
			printf("%d\n",query(x));
		}
	}
	return 0;
}

思路

对于这种迷之询问，用分块。将n个数分成sqrt(n)块，初始化将a数组赋值给d数组，将d数组分块从小到大排序，新建一个数组p储存每一块所加的和，
注意寻找最左侧和最右侧的二分写法

cf 103D

题目要求

给你N个数，然后每次询问给你(x,y)，求a[x]+a[x+y]+a[x+2y]+a[x+3y]的和是多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 300050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int a,b;
}q[maxn];
int n,m;
int limit=600;
LL a[maxn],ans[maxn],dp[maxn];
vector<int>e[600];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].a,&q[i].b);
		if(q[i].b>limit){
			LL re=0;
			for(int j=q[i].a;j<=n;j+=q[i].b) re+=a[j];
			ans[i]=re;
		}
		else e[q[i].b].push_back(i);
	}	
	for(int i=1;i<=limit;i++){
		if(e[i].size()){
			for(int j=n;j>=1;j--){
				if(i+j>n) dp[j]=a[j];
				else dp[j]=dp[i+j]+a[j];
			}
			int len=e[i].size();
			for(int j=0;j<len;j++){
				int temp=e[i][j];
				ans[temp]=dp[q[temp].a];
			}
		}
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}

思路

分块+离线
按照间隔y大小的sqrt分块 本题limit为：600
大于600直接暴力 小于600按照limit把询问的编号记录下来
对于每个limit按照dp预处理出每个位置 再更新ans

bzoj 2957

题目要求

小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，
数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，
其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi
(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，
他能看到多少栋楼房？

第一行两个正整数N,M
接下来M行，每行两个正整数Xi,Yi
输出M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
template<typename T> inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}
struct T{
	double val;
	int ans;
}tree[maxn<<2];
int n,m;
int query(int rt,int l,int r,double val){
	if(l==r) return tree[rt].val>val;
	int mid=(l+r)>>1;
	if(tree[rt<<1].val<=val) return query(rson,val);
	return tree[rt].ans-tree[rt<<1].ans+query(lson,val);
}
void update(int rt,int l,int r,int pos,double val){
	if(l==r){
		tree[rt].ans=1;
		tree[rt].val=val;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=pos) update(lson,pos,val);
	else update(rson,pos,val);
	tree[rt].val=max(tree[rt<<1].val,tree[rt<<1|1].val);
	tree[rt].ans=tree[rt<<1].ans+query(rson,tree[rt<<1].val);
}
int main(){
//	freopen("input.txt","r",stdin);
	read(n),read(m);
	while(m--){
		int x,y;
		read(x),read(y);
		update(1,1,n,x,double(y)/x);
		printf("%d\n",tree[1].ans);
	}
	return 0;
}

思路

能使用线段树的条件是：两个子问题可以合并
本题中，记ans[o]为：仅考虑o所代表的区间，有多少满足条件的数
那么首先，ans[o]一定包含ans[o×2]; 其次，属于ans[o×2]的建筑有可能挡住属于ans[o×2+1]的建筑，难点在于需求出这个数目
记 o×2 代表的区间中最大数为M，并将 o×2+1 所代表的区间分左右两段，记左段代表的区间中最大数为M2，继续讨论：

  1. 若M大于等于M2，则左段全部不符合要求，递归判断右段有多少个大于M的数
  2. 若M小于M2，则右段的答案不变，为ans[o×2+1]-ans[左段]，递归判断左段有多少个大于M的数

hihocoder 1236

题目要求

q次询问 每次寻找五维偏序
要求每次ans[i]的值异或flag

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 50050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
bitset<maxn>b[6][250],res[6];
int n,m,q,num,belong[maxn],block,l[maxn],r[maxn];
int ans[6];
struct node{
	int val,index;
	bool operator < (const node& x) const{
		return val<x.val;
	}
}a[6][maxn];
void build(){
    block=sqrt(n);
    num=n/block;
	if(n%block) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
	for(int i=1;i<=5;i++){
		for(int j=1;j<=num;j++) b[i][j].reset();
	}
	for(int i=1;i<=5;i++){
		for(int j=1;j<=num;j++){
			b[i][j]|=b[i][j-1];
			for(int k=l[j];k<=r[j];k++) b[i][j].set(a[i][k].index);
		}
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=5;j++){
				scanf("%d",&a[j][i].val);
				a[j][i].index=i;
			}
		}
		for(int i=1;i<=5;i++) sort(a[i]+1,a[i]+1+n);
		build();
		scanf("%d",&q);
		int flag=0;
		while(q--){
			for(int i=1;i<=5;i++){
				scanf("%d",&ans[i]);
				ans[i]^=flag;
				res[i].reset();
			}
			for(int i=1;i<=5;i++){
				int L=1,R=n,re=0;
				while(L<=R){
					int mid=L+R>>1;
					if(a[i][mid].val<=ans[i]) re=mid,L=mid+1;
					else R=mid-1;
				}
				for(int j=l[belong[re]];j<=re;j++) res[i].set(a[i][j].index);
				res[i]|=b[i][belong[re]-1];
			}
			res[0]=res[1]&res[2]&res[3]&res[4]&res[5];
			printf("%d\n",flag=res[0].count());
		}
	}
	return 0;
}

思路

在hihocoder147周的基础上分块
对于每次询问ans[i]二分查找到小于等于key的第一个位置 再进行块的处理
由于本题的q是在线的 所以需要排序分块二分
具体题解参考链接转跳链接

本文标题:分块专题2

文章作者:Hippopmonkey

发布时间:2017-08-30, 18:09:23

最后更新:2017-09-07, 20:04:57

原始链接:http://xuboming8.github.io/2017/08/30/分块专题2/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 分块专题2
    1. 1.1. cf 455D
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. codeforces 13E
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. codeforces 551E
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cf 103D
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. bzoj 2957
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. hihocoder 1236
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
|