/*
	PKU 2777
	Algorithm: LineTree
*/

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

class LineTree
{
public:
	int color;
	int left, right, mid;
	LineTree *lChild, *rChild;
	LineTree(int, int);
	void SetColor(int, int, int);
	int CountColor(int, int);
};

LineTree::LineTree(int l, int r)
{
	left = l;
	right = r;
	mid = (l + r) >> 1;
	color = 1;
	if (left + 1 != right)
	{
		lChild = new LineTree(left, mid);
		rChild = new LineTree(mid, right);
	}
}

void LineTree::SetColor(int first, int last, int c)
{
	if (first == last)
	{
		color = 1;
		return ;
	}
	if (left == first && right == last)
	{
		color = 0;
		color |= 1 << c;
		return;
	}
	else
	{
		//color |= 1 << c;
		if (first >= mid)
		{
			rChild->SetColor(first, last, c);
		}
		else if (last <= mid)
		{
			lChild->SetColor(first, last, c);
		}
		else if (first <= mid && last >= mid)
		{
			lChild->SetColor(first, mid, c);
			rChild->SetColor(mid, last, c);
		}

		color = lChild->color | rChild->color;
	}
	return ;
}

int LineTree::CountColor(int first, int last)
{
	if (first == left && last == right)
	{
		return color;
	}
	else if (first >= mid)
	{
		return rChild->CountColor(first, last);
	}
	else if (last <= mid)
	{
		return lChild->CountColor(first, last);
	}
	else if (first <= mid && last >= mid)
	{ 
		return lChild->CountColor(first, mid) | rChild->CountColor(mid, last);
	}
	return color;
}

int main()
{
	int length, color, op;
	int i;
	int first, last, cnum;
	char cmd;
	int tmp, j;
	cin >> length >> cnum >> op;
	{
		LineTree *Tree = new LineTree(0, length);
		for (i = 0; i < op; i++)
		{
			cin >> cmd;
			if (cmd == 'C')
			{
				cin >> first >> last >> color;
				Tree->SetColor(first-1, last, color);
			}
			else if (cmd == 'P')
			{
				cin >> first >> last;
				int ans = 0;
				tmp = Tree->CountColor(first-1, last);
				for (j = 0; j <= cnum; j++)
				{
					if (tmp & 1)
						ans++;
					tmp = tmp >> 1;
				}
				printf("%d\n", ans);
			}
		}
		delete Tree;
	}
	return 0;
}

• Re:WA 请大大指点一下阿！谢谢 (2382) cuiweican 2007-04-17 19:35:17