The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2777

线段树 经典的题目,以前曾经做过一遍,现在为了练手在做一次,刚学了splay树,反倒是加深了对线段树的理解,就是那个延迟标记(也就是懒操作)。虽然线段树已经写过多次,但是这题仍然不能1A,Query函数中有个地方应该是mid=(ST[i].l+ST[i].r)>>1写成了(l+r)>>1,导致wa了几次,今后要注意啊。
#include<iostream>
using namespace std;

int const maxn=100010;
int n,t,q;

struct node
{
    
int l,r;
    
int col;//用位来存储颜色
    int cover;//延迟标记
}
ST[maxn*4];

void Build(int l,int r,int i)
{
    ST[i].l
=l;
    ST[i].r
=r;
    ST[i].col
=0;
    ST[i].cover
=0;
    
if(l==r)
        
return;
    
int mid=(l+r)>>1;
    Build(l,mid,i
*2);
    Build(mid
+1,r,i*2+1);
}



void push_down(int i)
{
    ST[i
*2].col=ST[i].col;
    ST[i
*2+1].col=ST[i].col;
    ST[i].cover
=0;
    ST[i
*2].cover=1;
    ST[i
*2+1].cover=1;
}

void insert(int l,int r,int col,int i)
{
    
if(ST[i].l==l&&ST[i].r==r)
    
{
        ST[i].cover
=1;
        ST[i].col
=(1<<(col-1));
        
return ;
    }

    
if(ST[i].cover)//如果当前区间有效,下沿延迟标记
        push_down(i);
    
    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(r<=mid)
        insert(l,r,col,i
*2);
    
else if(l>mid)
        insert(l,r,col,i
*2+1);
    
else
    
{
        insert(l,mid,col,i
*2);
        insert(mid
+1,r,col,i*2+1);
    }

    ST[i].col
=ST[i*2].col|ST[i*2+1].col;
}


int fun(int num)//检查最后返回的整数中有多少颜色
{
    
int ans=0;
    
int i;
    
for(i=0;i<t;i++)
        
if(num&(1<<i))
            ans
++;
    
return ans;
}


int Que(int l,int r,int i)
{
    
if( (ST[i].l==l&&ST[i].r==r)||ST[i].cover==1)
        
return ST[i].col;
    
int mid=(ST[i].l+ST[i].r)>>1;
    
if(r<=mid)
        
return Que(l,r,i*2);
    
else if(l>mid)
        
return Que(l,r,i*2+1);
    
else
        
return Que(l,mid,i*2)|Que(mid+1,r,i*2+1);
}



int main()
{
    
while(scanf("%d%d%d",&n,&t,&q)!=EOF)
    
{
        Build(
1,n,1);
        ST[
1].cover=1;
        ST[
1].col=1;
        
char op[20];
        
int a,b,c;
        
for(int i=1;i<=q;i++)
        
{
            scanf(
"%s",op);
            
if(op[0]=='C')
            
{
                scanf(
"%d%d%d",&a,&b,&c);
                
if(a>b)
                    swap(a,b);
                insert(a,b,c,
1);
            }

            
else
            
{

                scanf(
"%d%d",&a,&b);
                
if(a>b)
                    swap(a,b);
                printf(
"%d\n",fun(Que(a,b,1)));
            }

        }

    }

    
return 0;
}

posted on 2010-08-02 21:24 abilitytao 阅读(664) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理