poj 2777

题意：1给区间染色

        2问区间有多少颜色

#include<iostream>
using namespace std;
struct Node
{int x;//区间覆盖颜色int end;int L,R;Node *Right,*Left;
};
Node Tree[1200100];
int nCount;
void Build(Node *root,int l,int r)
{root->x=1;//初始颜色root->L=l;root->R=r;root->end=1;if(l==r)return ;nCount++;root->Left=Tree+nCount;Build(root->Left,l,(l+r)/2);nCount++;root->Right=Tree+nCount;Build(root->Right,(l+r)/2+1,r);
}
void Updata(Node *root,int l,int r,int nColor)
{if(root->L==l&&root->R==r) //若到空间直接
    {root->x=nColor;root->end=1;return ;}if(root->end)               //此区间的颜色要更新  区间覆盖要pushdown，因为不push就是错的，这个区间的子区间已经不是这个状态，与区间增加减少多少个值不同；而区间增加减少c则不需要pushdown 区间lr所经过的节点肯定是父节点 可以从上向下更新；这里与与区间增加恰恰相反。
    {root->Right->end=1;root->Right->x=root->x;root->Left->x=root->x;root->Left->end=1;root->end=0;}if(l>(root->R+root->L)/2) Updata(root->Right,l,r,nColor);else if(r<=(root->R+root->L)/2)Updata(root->Left,l,r,nColor);else{Updata(root->Left,l,(root->R+root->L)/2,nColor);Updata(root->Right,(root->R+root->L)/2+1,r,nColor);}root->x=root->Right->x|root->Left->x;//执行完左右孩子节点后的总结
}
int Query(Node *root,int l,int r)
{if(root->end)//这里不需要pushdown 与区间增加某只恰恰相反；因为父节点的覆盖代表了各个子节点的状态return root->x;if(root->R==r&&root->L==l)return root->x;if(l>(root->L+root->R)/2)return Query(root->Right,l,r);else if(r<=(root->L+root->R)/2) return Query(root->Left,l,r);elsereturn Query(root->Left,l,(root->L+root->R)/2)|Query(root->Right,(root->L+root->R)/2+1,r);}
int Countbit(int sum)
{int x=1;int ans=0;int i;for(i=0;i<32;i++,x<<=1)if(x&sum)ans++;return ans;
}int main()
{int n,t,i,q,l,r,nColor;char c;scanf("%d%d%d",&n,&t,&q);nCount=0;Build(Tree,0,n-1);while(q--){cin>>c;if(c=='C'){scanf("%d%d%d",&l,&r,&nColor);if(l>r){int t=l;l=r;r=t;}Updata(Tree,l-1,r-1,1<<(nColor-1));}else {scanf("%d%d",&l,&r);if(l>r){int t=l;l=r;r=t;}        printf("%d\n",Countbit(Query(Tree,l-1,r-1)));}}    return 0;
}