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;
}