poj 2777 Count Color(セグメント更新＋区間加算)

Count Color
Time Limit: 1000 MS
 
メモリLimit: 65536 K
Total Submissions: 36646
 
Acceepted: 11053
Description
Chosen Proble m Solving and Program design as,you are required to solive all kids of probles.Here,we get a new problem. 
The e e is a very long board with length L centimeter、L is a positive integer、so we can evernly divide the board into L segments、and the y are labeled by 1、2、…L from left to Right、each is 1 centimewers.Nollaton. 
1.「C A B C」Color the board from segment A to segment B withカラーカラーC. 
2.「P A B」Output the number of different colors painted between segment A and segment B(including) 
In our daily life、we have very few wods to describe a色(red、green、blue、yelloww...)、so you may asume that the total number of different colors T colorsT isssmake.Tomakeitsimple、we express thethethethethethethe aapapapapapapapapapapapapapapapapars the the thethethe thethethethe affs s s s s thethethethethethethethethethethersrsrs aaaaaffs s thethethethethethethethethethethethe aaafffs s s s thethethethethetheof problem is left to your. 
Input
First line of input contains L(1<=L==100000)、T(1==T<=30)and O(1==O==100000).Here O denotes the number of operations.Follwing O lines,each contains"C"or"P B"(herstainger A,arefirs A,arever.)
Output
Ouut result of the output operation in order、each line contains a number.
Sample Input

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

Sample Output

2
1

壁の色の種類を求めます.色の種類が一番多いから、色の総数はバイナリで表します.

#include
#include
#include
#include
#include
using namespace std;
#define ll __int64
#define N 100005
struct node
{
    int l,r;
    int s,v,f;   //         ，    、        
}f[N*3];
void creat(int t,int l,int r)
{
    f[t].l=l;
    f[t].r=r;
    f[t].v=1;
    f[t].f=0;
    f[t].s=1;  //     1,        
    if(l==r)
    {
        return ;
    }
    int tmp=t<<1,mid=(l+r)>>1;
    creat(tmp,l,mid);
    creat(tmp|1,mid+1,r);
}

void update(int t,int l,int r,int v)
{
    int tmp=t<<1,mid=(f[t].l+f[t].r)>>1;
    if(f[t].l==l&&f[t].r==r)
    {
        f[t].v=v;
        f[t].s=(1<mid)
        update(tmp|1,l,r,v);
    else
    {
        update(tmp,l,mid,v);
        update(tmp|1,mid+1,r,v);
    }
    f[t].f=0;          //    
    f[t].s=f[tmp].s|f[tmp|1].s;     
}
int query(int t,int l,int r)
{
    if(f[t].l==l&&f[t].r==r)
    {
        return f[t].s;
    }
    int tmp=t<<1,mid=(f[t].l+f[t].r)>>1;
    if(f[t].f)
    {
        f[tmp].f=f[tmp|1].f=1;
        f[tmp].v=f[tmp|1].v=f[t].v;
        f[tmp].s=f[tmp|1].s=(1<mid)
        return query(tmp|1,l,r);
    else
    {
        return query(tmp,l,mid)|query(tmp|1,mid+1,r);
    }
}
int main()
{
    int n,t,q,l,r,c;
    char ch;
    while(~scanf("%d%d%d",&n,&t,&q))
    {
        creat(1,1,n);
        while(q--)
        {
            getchar();
            scanf("%c ",&ch);
            if(ch=='C')
            {
                scanf("%d%d%d",&l,&r,&c);
                if(l>r)
                    swap(l,r);
                update(1,l,r,c-1);
            }
            else
            {
                scanf("%d%d",&l,&r);
                if(l>r)
                    swap(l,r);
                int tmp=query(1,l,r),ans=0;
                while(tmp)
                {
                    if(tmp&1)
                        ans++;
                    tmp>>=1;
                }
                printf("%d
",ans);
            }
        }
    }
    return 0;
}