A Corrupt Mayor‘s Performance Art

5 10
P 1 2 3
P 2 3 4
Q 2 3
Q 1 3
P 3 5 4
P 1 2 7
Q 1 3
Q 3 4
P 5 5 8
Q 1 5
0 0

4
3 4
4 7
4
4 7 8

具体细节见代码：

#include"stdio.h"
#include"string.h"
#include"iostream"
#include"algorithm"
#include"queue"
using namespace std;
#define N 1000005
struct node
{
	int l,r;
	int s,v;
	int mid()  //定义函数
	{
	    return (l+r)/2;
	}
}f[N*3];
int s;
void Creat(int t,int l,int r)  //建树
{
    f[t].l=l;
    f[t].r=r;
    f[t].s=4;
    f[t].v=0;
    if(l==r)
        return ;
    Creat(t<<1,l,f[t].mid());
    Creat(t<<1|1,f[t].mid()+1,r);
}
void Update(int t,int l,int r,int v)
{
    if(f[t].l==l&&f[t].r==r)
    {
        f[t].s=(1<<v);
        f[t].v=v;
        return ;
    }
    if(f[t].v)      //该段区间的某一段颜色要改变，向下更新[l,r]区间
    {
        f[t<<1].s=f[t<<1|1].s=1<<f[t].v;
        f[t<<1].v=f[t<<1|1].v=f[t].v;
    }
    f[t].v=0;      //该层已经更新完毕
    if(r<=f[t].mid())
        Update(t<<1,l,r,v);
    else if(l>f[t].mid())
        Update(t<<1|1,l,r,v);
    else
    {
        Update(t<<1,l,f[t].mid(),v);
        Update(t<<1|1,f[t].mid()+1,r,v);
    }
    f[t].s=f[t<<1].s|f[t<<1|1].s;  //向上求和
}
void Query(int t,int l,int r)
{
    if(f[t].l==l&&f[t].r==r)
    {
        s|=f[t].s;
        return ;
    }
    if(f[t].v)  //同函数Update，向下更新颜色
    {
        f[t<<1].s=f[t<<1|1].s=1<<f[t].v;
        f[t<<1].v=f[t<<1|1].v=f[t].v;
    }
    f[t].v=0;  
    if(r<=f[t].mid())
        Query(t<<1,l,r);
    else if(l>f[t].mid())
        Query(t<<1|1,l,r);
    else
    {
        Query(t<<1,l,f[t].mid());
        Query(t<<1|1,f[t].mid()+1,r);
    }
}
int main()
{
    int n,q,i,l,r,v;
    char ch;
	while(scanf("%d%d",&n,&q),n||q)
    {
        Creat(1,1,n);
        while(q--)
        {
            getchar();
            scanf("%c",&ch);
            if(ch=='Q')
            {
                scanf("%d%d",&l,&r);
                int f=0;
                s=0;
                Query(1,l,r);
                for(i=0;i<=30;i++)
                {
                    if(s&(1<<i))
                    {
                        if(f)
                            printf(" %d",i);
                        else
                        {
                            printf("%d",i);
                            f=1;
                        }
                    }
                }
                puts("");
            }
            else
            {
                scanf("%d%d%d",&l,&r,&v);
                Update(1,l,r,v);
            }
        }
    }
	return 0;
}

hdu 5023 A Corrupt Mayor's Performance Art (线段树+区间更新+状压)

原文：http://blog.csdn.net/u011721440/article/details/39524095