程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ2777 Count Color 線段樹區間更新

POJ2777 Count Color 線段樹區間更新

編輯：C++入門知識

題目描述：
長度為L個單位的畫板，有T種不同的顏料，現要求按序做O個操作，操作分兩種：
1.“C A B C”,即將A到B之間的區域塗上顏色C
2.“P A B”，查詢[A，B]區域內出現的顏色種類

出現操作2時，請輸出答案

PS:初始狀態下畫板顏色為1

一開始沒有想那麼好，用int整型位移來代替顏色，還是使用了最傳統的bool color[來記錄，可是不知道錯在了哪裡，

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;


const int N = 100000 + 5;

typedef struct Node {
	int color;
	int l,r;
};

Node tree[N * 4];
bool vis[50];

void init() {
	memset(vis,false,sizeof(vis));
}

void build(int l,int r,int id) {
	tree[id].color = 1;
	tree[id].l = l;
	tree[id].r = r;
	if(tree[id].l == tree[id].r)return;
	int mid = (l + r)/2;
	build(l,mid,id<<1);
	build(mid + 1,r,id<<1|1);
}

void update(int l,int r,int id,int color) {
	if(tree[id].l >= l && tree[id].r <= r) {
		tree[id].color = color;return;
	}
	int mid = (tree[id].l + tree[id].r)/2;
	tree[id].color = -1;
	if(r <= mid) update(l,r,id<<1,color);
	else  {
		if(l > mid)update(l,r,id<<1|1,color);
		else {
			update(l,mid,id<<1,color);
			update(mid+1,r,id<<1|1,color);
		}
	}
}

void update2(int l,int r,int id) {
	if(tree[id].color > 0) {
		vis[tree[id].color] = true;return;
	}
	if(tree[id].l == tree[id].r)return;
	int mid = (tree[id].l + tree[id].r)/2;
	if(r <= mid) update2(l,r,id<<1);
	else {
		if(l > mid)update2(l,r,id<<1|1);
		else {
			update2(l,mid,id<<1);
			update2(mid+1,r,id<<1|1);
		}
	}
}

int find(int x) {
	int ans = 0;
	for(int i=1;i<=x;i++)
		if(vis[i])
			ans++;
	return ans;
}

int main() {
	int n,m,q;
	while(scanf("%d %d %d",&n,&m,&q) == 3 ){
		memset(tree,0,sizeof(tree));
		init();
		build(1,n,1);
		while(q--) {
			char s[2];
			scanf("%s",s);
			if(s[0] == 'C') {
				int x,y,c;
				scanf("%d %d %d",&x,&y,&c);
				if(x > y)swap(x,y);
				update(x,y,1,c);
			}
			else {
				int x,y;
				scanf("%d %d",&x,&y);
				init();
				if(x > y)swap(x,y);
				update2(x,y,1);
				printf("%d\n",find(m));
			}

		}
	}
	return 0;
}

後來看了別人的一下，看到方法不一樣，跑了案例也沒發現自己的錯誤，繼續檢查還是不行，難道真的是方法不行？換了個方法過了，但是上面的代碼錯誤原因還是沒有查出來，WA哭

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

const int N = 100000 + 5;

typedef struct Node {
	int l,r;
	int color;
	int flag;
};

Node tree[N * 4];

void init() {
	memset(tree,0,sizeof(tree));
}

void cal(int id) {
	tree[id].color = tree[id<<1].color | tree[id<<1|1].color;
}

void build(int l,int r,int id) {
	tree[id].l = l;
	tree[id].r = r;
	tree[id].color = 1;
	tree[id].flag = 1;
	if(tree[id].l == tree[id].r) return;
	int mid = (l + r)/2;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
}

void cover(int id) {
	tree[id<<1].color = tree[id].color;
	tree[id<<1].flag = 1;
	tree[id<<1|1].color = tree[id].color;
	tree[id<<1|1].flag = 1;
	tree[id].flag = 0;
}

void updata(int l,int r,int id,int col) {
	if(l <= tree[id].l && r >= tree[id].r) {
		tree[id].color = col;
		tree[id].flag = 1;
		return;
	}
	if(tree[id].color == col)return;
	if(tree[id].flag)cover(id);
	int mid = (tree[id].l + tree[id].r)/2;
	if(r <= mid) updata(l,r,id<<1,col);
	else if(l > mid)updata(l,r,id<<1|1,col);
	else {
		updata(l,mid,id<<1,col);
		updata(mid+1,r,id<<1|1,col);
	}
	cal(id);
}

int ans;

void query(int l,int r,int id) {
	if(l <= tree[id].l && r >= tree[id].r) {
		ans |= tree[id].color;return;
	}
	if(tree[id].flag) {
		ans |= tree[id].color;return;
	}
	int mid = (tree[id].l + tree[id].r)/2;
	if(r <= mid) query(l,r,id<<1);
	else if(l > mid) query(l,r,id<<1|1);
	else {
		query(l,mid,id<<1);
		query(mid+1,r,id<<1|1);
	}
}

int main() {
	int n,m,q;
	while(scanf("%d %d %d",&n,&m,&q) == 3) {
		init();
		build(1,n,1);
		char s[2];
		while(q--) {
			scanf("%s",s);
			if(s[0] == 'C') {
				int x,y,c;
				scanf("%d %d %d",&x,&y,&c);
				if(x > y)swap(x,y);
				updata(x,y,1,1<<(c-1));//把顏色改成用正向委員算表示
			}
			else {
				int x,y;
				scanf("%d %d",&x,&y);
				if(x > y)swap(x,y);
				ans = 0;
				query(x,y,1);
				int cnt = 0;
				while(ans) {
					if(ans%2)cnt++;
					ans /= 2;
				}
				printf("%d\n",cnt);
			}
		}
	}
	return 0;
}