//by David
#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;

typedef __int64 LL;		//scanf("%I64d", &x);
typedef vector<int> VI;
typedef pair<int,int> PII;
#define MP				make_pair
#define FOR(i,a)			for( int i = 0 ; i < a ; i ++ )
#define LL(a)				a<<1		//a=a*2   LL和RR主要用于线段树
#define RR(a)				a<<1|1		//a=a*2+1
const double Pi = acos(-1.0);
template<class T> inline void checkmin(T &a,T b)	{if(a < 0 || a > b)a = b;}
template<class T> inline void checkmax(T &a,T b)	{if(a < b)	a = b;}
int dx[] = {-1,0,1,0,1,1,-1,-1};//up Right down Left
int dy[] = {0,1,0,-1,1,-1,1,-1};
//-----------------------------------------------------------------
int countbit(int n){int c;for(c=0;n;n>>=1)c+=n&1;return c;}

#define N 300000

struct Seg_Tree
{
	int left,right;
	int col;
	bool cover;
	int calmid() {		return (left+right)/2;		}
}tt[N];
 
void build(int left,int right,int idx) 
{
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].col = 1;
	tt[idx].cover = true;
	if(left == right)
		return ;
	int mid = tt[idx].calmid();
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
}
 
void update(int left,int right,int c,int idx) 
{
	if(left <= tt[idx].left && right >= tt[idx].right) 
	{
		tt[idx].cover = true;
		tt[idx].col = 1<<(c-1);
		return ;
	}
	if(tt[idx].cover) 
	{
		tt[RR(idx)].col = tt[LL(idx)].col = tt[idx].col;
		tt[RR(idx)].cover = tt[LL(idx)].cover = true;
		tt[idx].cover = false;
	}
	int mid = tt[idx].calmid();
	if(left <= mid) update(left,right,c,LL(idx));
	if(mid < right) update(left,right,c,RR(idx));
	tt[idx].col = tt[LL(idx)].col | tt[RR(idx)].col;
}

int query(int left,int right,int idx) 
{
	if(left == tt[idx].left && right == tt[idx].right)
		return tt[idx].col;
	if(tt[idx].cover) 
	{
		tt[RR(idx)].col = tt[LL(idx)].col = tt[idx].col;
		tt[RR(idx)].cover = tt[LL(idx)].cover = true;
		tt[idx].cover = false;
	}
	int mid = tt[idx].calmid();
	if(right <= mid)
		return query(left,right,LL(idx));
	else if(mid < left)
		return query(left,right,RR(idx));
	else
		return query(left,mid,LL(idx)) | query(mid+1,right,RR(idx));
}

int main()
{
	int l,t,o;
	scanf("%d %d %d\n",&l,&t,&o);
	build(1,l,1);
	FOR(i,o)
	{
		char p[2];
		scanf("%s",&p);
		if( p[0]=='C')
		{
			int x,y,z;
			scanf("%d %d %d",&x,&y,&z);
			if(x>y)	{	int m=x;x=y;y=m;	}
			update(x,y,z,1);
		}
		else
		{
			int x,y;
			scanf("%d %d",&x,&y);
			if(x>y)	{	int m=x;x=y;y=m;	}
			printf("%lld\n",countbit(query(x,y,1)));
		}
	}
	return 0;
}

• Re:打广告,此题解答以及大量线段树题目http://www.notonlysuccess.com/?p=59 (8) comzyh 2010-10-13 06:10:02