C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 2777 Count Color 解题报告

Posted on 2011-11-16 13:18 C小加 阅读(5260) 评论(0)  编辑 收藏 引用 所属分类: 解题报告
Wednesday, November 16, 2011
线段树,WA了无数次,又TLE了两次。WA的原因是solve函数写错,TLE的原因是solve写的太挫了。。。。
题意:[1,L]的染色板,初始化都是1号色,[1,T]种不同的颜色,可进行O次操作。
操作有两种:
C A B C 将染色板A到B所有的格子染成C号色
P A B 询问染色板A到B中颜色的种数
思路:很简单的线段树,更新处理的时候更新到树根会超时,应该成段更新,询问的时候没处理好也可能会超时。

#include 
<iostream>
#include 
<cstdio>
#include 
<cstring>
using namespace std;
const int MAXN=100003;
int flag[33],color[MAXN];
typedef 
struct
{
    
int left,right,col;
}line;
line tree[
4*MAXN];
int sum;
void Create(int l,int r,int root) //建树
{
    tree[root].left
=l;
    tree[root].right
=r;
    tree[root].col
=1;
    
if(l==r) return;
    
int mid=(l+r)>>1;
    Create(l,mid,root
<<1);
    Create(mid
+1,r,(root<<1)+1);
}
void Updata(int l,int r,int colo,int root) //更新染色板
{
    
if(l<=tree[root].left&&tree[root].right<=r)
    {
        tree[root].col
=colo;
        
return;
    }
    
if(tree[root].col==colo) return;
    
if(tree[root].left==tree[root].right) return;
    
if(tree[root].col>=0)  //如果这一段的颜色超过1种,则向下更新之前的颜色,并将本段颜色赋值-1
    {
        tree[root
<<1].col=tree[root].col;
        tree[(root
<<1)+1].col=tree[root].col;
        tree[root].col
=-1;
    }
    
int mid=(tree[root].left+tree[root].right)>>1;
    
if(l>mid) Updata(l,r,colo,(root<<1)+1);
    
else if(r<=mid) Updata(l,r,colo,root<<1);
    
else
    {
        Updata(l,mid,colo,root
<<1);
        Updata(mid
+1,r,colo,(root<<1)+1);
    }
}
void solve(int l,int r,int root) //询问
{

    
if(tree[root].col>=0//如果父节点有单一的颜色,就直接更新,不需要找到子节点更新
    {
        flag[tree[root].col]
=1;//统计哪些颜色出现过
        return;
    }
    
if(tree[root].left==tree[root].right) return;
    
int mid=(tree[root].left+tree[root].right)>>1;
    
if(l>mid) solve(l,r,(root<<1)+1);
    
else if(r<=mid) solve(l,r,root<<1);
    
else
    {
        solve(l,mid,root
<<1);
        solve(mid
+1,r,(root<<1)+1);
    }
}

int main()
{
    
//freopen("input","r",stdin);
    int n,t,o;
    
while(scanf("%d %d %d",&n,&t,&o)!=EOF)
    {

        memset(color,
0,sizeof(color));
        Create(
1,n,1);
        
int tl,tr,tc;
        
char str[2];
        
for(int i=0;i<o;i++)
        {
            scanf(
"%s",str);
            
if(str[0]=='C')
            {
                scanf(
"%d %d %d",&tl,&tr,&tc);
                
if(tl>tr)
                {
                    
int temp=tl;
                    tl
=tr;
                    tr
=temp;
                }
                Updata(tl,tr,tc,
1);
            }
            
else if(str[0]=='P')
            {
                memset(flag,
0,sizeof(flag));
                scanf(
"%d %d",&tl,&tr);
                
if(tl>tr)
                {
                    
int temp=tl;
                    tl
=tr;
                    tr
=temp;
                }
                sum
=0;
                solve(tl,tr,
1);
                
for(int i=1;i<=t;i++)
                
if(flag[i]) sum++;
                printf(
"%d\n",sum);
            }
        }
    }

    
return 0;
}

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