Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

代码注释+坑点

Posted by 0x404 at 2018-08-20 14:47:16 on Problem 2777
//题意:有T种颜色,T<=30,一段区间
//每次可以进行区间覆盖颜色或者询问某段区间不同的颜色个数
//因为T<=30,可以考虑状态压缩,在二进制中1代表有第i种颜色,0代表没有
//每次更新就相当于把该段状态 = 1<<i
//每次询问只要把该段的左右区间或运算一下即可
#include <cstdio>
#include <iostream>
#include <cstring>
#define MAXN 100050
using namespace std;
int col[MAXN*4],tag[MAXN*4],n,t,m;//col[i]表示第i段的颜色状态
 
inline void push_up(int rt){col[rt] = col[rt<<1] | col[rt<<1|1];} //维护上一段的col 
inline void push_down(int rt){
	if(tag[rt]){
		int i = tag[rt];
		col[rt<<1] = 1<<(i - 1);
		col[rt<<1|1] = 1<<(i - 1);
		tag[rt<<1] = tag[rt<<1|1] = i;
		tag[rt] = 0;
	}
}
inline void build(int rt, int l, int r){
	if(l == r){
		col[rt] = 1;//把颜色i看做是在二进制下1左移i-1位的结果,一开始是颜色1,所以col=1 
		return;
	}
	int mid = (l + r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);//记得更新 
}
inline void add(int rt,int L,int R,int i,int l, int r){
	if(l >= L && r <= R){
		col[rt] = 1<<(i-1);
		tag[rt] = i;
		return;
	}//遇到整段更新打标记 
	push_down(rt);//这边一定要pushdown,比如在区间X[1,4]有了一个tag,现在来到X,打算更新[3,4],如果不pushdown,等[3,4]更新完成,[1,4]的tag仍然存在
				 //下次询问来到X时,就会遇到X本不该存在的tag,push掉tag后,之前更新的[3,4]就会被tag覆盖,这样就会出现错误 
	int mid = (l + r)>>1;
	if(L <= mid) add(rt<<1,L,R,i,l,mid);
	if(R > mid) add(rt<<1|1,L,R,i,mid+1,r);
	push_up(rt);
}
inline int query(int rt, int L, int R, int l, int r){
	if(l >= L && r <= R) return col[rt];
	push_down(rt);//这边也一定要pushdown,理由如上 
	int mid = (l + r)>>1;
	int ans = 0;
	if(L <= mid) ans |= query(rt<<1,L,R,l,mid);
	if(R > mid) ans |= query(rt<<1|1,L,R,mid+1,r);
	return ans;//把状态并起来 
}
int main(){
	cin>>n>>t>>m;
	build(1,1,n);
	for (int i = 1; i <= m; i++){
		char opt;
		int l,r,x;
		cin>>opt;
		if(opt == 'C'){
			cin>>l>>r>>x;
			if(l>r) swap(l,r);//这题坑的地方,L可能大于R 
			add(1,l,r,x,1,n);
		}
		if(opt == 'P'){
			cin>>l>>r;
			if(l>r) swap(l,r);
			int s = query(1,l,r,1,n);
			int ans = 0;
			for (int j = 0; j <= 30; j++)
				if((1<<j)&s) ++ans;//统计答案 
			cout<<ans<<endl;
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator