#include "iostream"
struct Node
{
    int value,min,max;
    Node* left,*right;
    Node(){left=0;right=0;value=1;}
};
Node TreeNode[200000];
Node root;
int NodeNum;
int N,T,O;
void Init(int L)
{
    NodeNum=0;
    root=Node();
    root.left=0;
    root.right=0;
    root.min=1;
    root.max=L;
}
int cal(int color)
{
    int count=0;
    for(int i=0;i<T;i++)
        if((color>>i&1)==1)
            count++;
    return count;
}
void change(Node* root,int min,int max,int color)
{
    int mid=(root->min+root->max)/2;
    if(root->min==min&&root->max==max)
    {
        root->value=1<<color;
        if(root->left)change(root->left,root->left->min,root->left->max,color);
        if(root->right)change(root->right,root->right->min,root->right->max,color);
        return;
    }
    if(root->left==0)
    {
        root->left=&TreeNode[NodeNum++];
        root->right=&TreeNode[NodeNum++];
        root->left->min=root->min;
        root->left->max=mid;
        root->right->min=mid+1;
        root->right->max=root->max;
        root->left->value=1;
        root->right->value=1;
    }
    if(min>mid)
    {
        change(root->right,min,max,color);
    }
    if(max<=mid)
    {
        change(root->left,min,max,color);
    }
    if(min<=mid&&max>mid)
    {
        change(root->left,min,mid,color);
        change(root->right,mid+1,max,color);
    }
    root->value=root->left->value|root->right->value;
}
int find(Node* root,int min,int max)
{
    if(root->min==min&&root->max==max)
    {     
        return root->value;
    }
    int color=0;
    int mid=(root->min+root->max)/2;
    if(root->left==0)
    {
        root->left=&TreeNode[NodeNum++];
        root->right=&TreeNode[NodeNum++];
        root->left->min=root->min;
        root->left->max=mid;
        root->right->min=mid+1;
        root->right->max=root->max;
        root->left->value=root->value;
        root->right->value=root->value;
    }
    if(max<=mid)
    {
        return find(root->left,min,max);
    }
    if(min>mid)
    {
        return find(root->right,min,max);
    }
    if(min<=mid&&max>mid)
    {
        return find(root->left,min,mid)|find(root->right,mid+1,max);
    }
}
main()
{
    scanf("%d %d %d",&N,&T,&O);
    Init(N);
    for(int i=0;i<O;i++)
    {
        char s[10];
        scanf("%s",s);
        if(s[0]=='C')
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if(a<=b)
            {
                change(&root,a,b,c-1);
            }
            else
            {
                change(&root,b,a,c-1);
            }
        }
        if(s[0]=='P')
        {
            int a,b;
            scanf("%d %d",&a,&b);
            int color;
            if(a<=b)
            {
                color=find(&root,a,b); 
            }
            else
            {
                color=find(&root,b,a);
            }
            printf("%d\n",cal(color));
        }
    }
}

• Re:所有能想到的数据都过了,WA到吐 (14) 200730690331 2008-12-07 21:47:14