Luogu P1558 色板游戏

　　（此题与POJ2777重题）

　　为了加深对线段树的记忆，然后开始搞这道题。

　　TM的WA了一下午就是发现x可能大于y（然而题目里说的还很清楚，我TM没看见）

　　这道题只需要在线段树的板子上改一些地方就可以了：

　　1.存储时不是存储颜色，而是将它状压成一个整数（如序号为3的颜色存为1<<3=8）

　　2.回溯时不是取和相加，而是直接按位或（|），原理等下讲

　　3.最后的查询完毕的值统计一下二进制下有多少个1就是ans

　　最后讲一下为什么要|

　　假如3种颜色 2,3,3，在树上记为4,8,8，它们对应的二进制就是（100,1000,1000）

　　有没有发现，每个数的二进制下都只有一位上有1，而且不同颜色的数1的位置不同

　　因此在|的时候，只要这一位上有1，那么就一定有这种颜色

　　线段树就是板子，套一套就好了

　　CODE

#include<cstdio>

#include<iostream>

using namespace std;

const int N=;

int tree[N*],add[N*],l,t,o,x,y,z;

char ch;

inline void read(int &x)

{

    x=; char ch=getchar(); int flag=;

    while (ch<''||ch>'') { if (ch=='-') flag=-; ch=getchar(); }

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    x*=flag;

}

inline void write(int x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

inline void up(int root)

{

    tree[root]=tree[root*]|tree[root*+];

}

inline void down(int root)

{

    if (add[root])

    {

        tree[root*]=add[root];

        tree[root*+]=add[root];

        add[root*]=add[root];

        add[root*+]=add[root];

        add[root]=;

    }

}

inline void build(int root,int l,int r)

{

    if (l==r)

    {

        tree[root]=;

        return;

    }

    int mid=l+r>>;

    build(root*,l,mid);

    build(root*+,mid+,r);

    up(root);

}

inline void change(int root,int l,int r,int beg,int end,int col)

{

    if (l>=beg&&r<=end)

    {

        tree[root]=<<col;

        add[root]=<<col;

        return;

    }

    down(root);

    int mid=l+r>>;

    if (beg<=mid) change(root*,l,mid,beg,end,col);

    if (end>mid) change(root*+,mid+,r,beg,end,col);

    up(root);

}

inline int query(int root,int l,int r,int beg,int end)

{

    if (l>=beg&&r<=end) return tree[root];

    down(root);

    int mid=l+r>>,res=;

    if (beg<=mid) res|=query(root*,l,mid,beg,end);

    if (end>mid) res|=query(root*+,mid+,r,beg,end);

    up(root);

    return res;

}

inline int calc(int x)

{

    int res=;

    while (x)

    {

        if (x%==) res++;

        x>>=;

    }

    return res;

}

int main()

{

    read(l); read(t); read(o);

    build(,,l);

    while (o--)

    {

        cin>>ch;

        if (ch=='C')

        {

            read(x); read(y); read(z);

            if (x>y) swap(x,y);

            change(,,l,x,y,z);

        }else

        {

            read(x); read(y);

            if (x>y) swap(x,y);

            write(calc(query(,,l,x,y))); putchar('\n');

        }

    }

    return ;

}