pku2777.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 120 行

#include <stdio.h>
#include <memory.h>
#define size 100010

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

Node STree[size * 4];
int L, T, O;
int Count;

void CreateTree(int s, int e, int p)
{
	int m;
	STree[p].l = s;
	STree[p].r = e;
	STree[p].color = 1;
	if (e - s == 1)
		return;
	m = (e + s + 1) / 2;
	CreateTree(s, m, p * 2);
	CreateTree(m, e, p * 2 + 1);
}

void Insert(int l, int r, int c, int p)
{
	int m;
	if (l <= STree[p].l && r >= STree[p].r)
	{
		STree[p].color = c;
		return;
	}
	if (STree[p].l + 1 == STree[p].r)
		return;
	if (STree[p].color)
	{
		STree[p * 2].color = STree[p].color;
		STree[p * 2 + 1].color = STree[p].color;
	}
	m = (STree[p].l + STree[p].r + 1) / 2;
	if (l < m && r > STree[p].l)
		Insert(l, r, c, p * 2);
	if (r > m && l < STree[p].r)
		Insert(l, r, c, p * 2 + 1);
	if (STree[p * 2].color == STree[p * 2 + 1].color)
		STree[p].color = STree[p * 2].color;
	else
		STree[p].color = 0;
}

void Find(int l, int r, int p)
{
	int m;
	if (STree[p].color)
	{
		Count = Count | (1 << (STree[p].color - 1));
		return;
	}
	m = (STree[p].l + STree[p].r + 1) / 2;
	if (l < m && r > STree[p].l)
		Find(l, r, p * 2);
	if (r > m && l < STree[p].r)
		Find(l, r, p * 2 + 1);
}

void Calc(int val)
{
	int i, p;
	p = 0;
	for (i = 0; i < T; i++)
	{
		if ((val >> i) & 1)
			p++;
	}
	printf("%d\n", p);
}

void Solve()
{
	char s[3];
	int l, r, c;
	while (O--)
	{
		scanf("%s", s);
		if (s[0] == 'C')
		{
			scanf("%d %d %d", &l, &r, &c);
			Insert(l - 1, r, c, 1);
		}
		else
		{
			scanf("%d %d", &l, &r);
			if (l > r)
			{
				c = l;
				l = r;
				r = c;
			}
			Count = 0;
			Find(l - 1, r, 1);
			Calc(Count);
		}
	}
}

int main()
{
	while (EOF != scanf("%d %d %d", &L, &T, &O))
	{
		CreateTree(0, L, 1);
		Solve();
	}
	return 0;
}