POJ2777 (C++)

poj2777.cpp

#include <stdio.h>
#include <string.h>
#include <algorithm>

struct segment {
  int left,right,color;
} a[275000];
bool f[50];

void segtree_create(int p, int l, int r);
void segtree_insert(int p, int l, int r, int c);
void segtree_query(int p, int l, int r);
inline void pushdown(int p) {
	if (a[p].color!=-1) {
		a[p*2].color=a[p*2+1].color=a[p].color;
		a[p].color=-1;
	}
}

int main() {
	int len,l,r,c,t,o;
	scanf("%d%d%d",&len,&t,&o);
	char ch;
	segtree_create(1,1,len);
	while (o--) {
		getchar();
		scanf("%c",&ch);
		if (ch=='C') {
			scanf("%d%d%d",&l,&r,&c);
			if (l>r) std::swap(l,r);
			segtree_insert(1,l,r,c);
		}
		else if (ch=='P') {
			scanf("%d%d",&l,&r);
			if (l>r) std::swap(l,r);
			memset(f,false,sizeof(f));
			segtree_query(1,l,r);
			int ans=0;
			for (int j=1; j<=t; j++) ans+=f[j];
			printf("%d\n",ans);
		}
	}
	return 0;
}

void segtree_create(int p, int l, int r) {
	a[p].left=l;
	a[p].right=r;
	a[p].color=1;
	if (l==r) return;
	int m=(l+r)>>1;
	segtree_create(p*2,l,m);
	segtree_create(p*2+1,m+1,r);
}

void segtree_insert(int p, int l, int r, int c) {
	if (a[p].left>=l && a[p].right<=r) a[p].color=c; else {
		pushdown(p);
		if (l<=a[p*2].right) segtree_insert(p*2,l,r,c);
		if (r>=a[p*2+1].left)  segtree_insert(p*2+1,l,r,c);
	}
}

void segtree_query(int p, int l, int r) {
	if (a[p].color!=-1) f[a[p].color]=true; else {
		pushdown(p);
		if (l<=a[p*2].right) segtree_query(p*2,l,r);
		if (r>=a[p*2+1].left)  segtree_query(p*2+1,l,r);
	}
}