POJ 2777 Count Colorセグメントツリー

2195 ワード

題意:長い板を塗装し、2つの操作があり、1つは挿入し、1つは統計し、一定範囲の色種数を出力する.
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define L(u) (u<<1)
#define R(u) (u<<1|1)
#define N 150000
struct TreeNode { int l,r,c;};
TreeNode node[N*3];
int kind, mark[31];

void build ( int u, int l, int r )
{
    node[u].l = l;
    node[u].r = r;
    node[u].c = 1;
	if ( l == r ) return;
	int mid = ( l + r ) >> 1;
	build ( L(u), l, mid );
	build ( R(u), mid + 1, r );
}

void update ( int u, int l, int r, int c )
{
    if ( node[u].c == c ) return;
	if ( node[u].l == l && node[u].r == r )
	{
		node[u].c = c; return;
	}

	if ( node[u].c != -1 )
	{
	    node[L(u)].c = node[R(u)].c = node[u].c;
		node[u].c = -1;
    }
	int mid = (node[u].l + node[u].r) >> 1;
	if ( r <= mid ) update (L(u),l,r,c);
	else if ( l > mid ) update (R(u),l,r,c);
	else update (L(u),l,mid,c), update(R(u),mid+1,r,c);
}

void query ( int u, int l, int r )
{
	if ( node[u].c != -1 )
    {
		if( !mark[node[u].c] )
        {
            mark[node[u].c] = 1;
            kind++;
        }
		return;
	}
	int mid = (node[u].l + node[u].r) >> 1;
	if ( r <= mid ) query (L(u),l,r);
	else if ( l > mid ) query (R(u),l,r);
	else query(L(u),l,mid), query(R(u),mid+1,r);
}

int main()
{
	int L, T, O, a, b, c;
	char oper[10];
	scanf("%d%d%d", &L, &T, &O);
	build ( 1, 1, L );
	while ( O-- )
	{
		scanf("%s %d %d",oper, &a, &b);
		if ( a > b ) swap(a,b);
		if ( oper[0] == 'P' )
		{
			kind = 0;
			memset(mark,0,sizeof(mark));
			query ( 1, a, b );
			printf("%d
", kind ); } else { scanf("%d",&c); update ( 1, a, b, c ); } } return 0; }