posts - 100,  comments - 15,  trackbacks - 0
//贡献6个WA
//先建树,然后插入,总计,mixcolor表示该段不止一色
  1#include<iostream>
  2#define MAX 100000
  3#define mixcolor -1
  4using namespace std;
  5
  6struct Seg
  7{
  8    int left,right;
  9    int color;
 10}
;
 11
 12Seg Segtree[3*MAX+1];
 13bool colortable[31];
 14
 15void buildsegtree(int v,int l,int r)
 16{
 17    
 18    Segtree[v].left=l;
 19    Segtree[v].right=r;
 20    Segtree[v].color=1;
 21    if(l==r) return ; 
 22
 23    int mid=(l+r)>>1// div 2
 24    buildsegtree(v*2,l,mid);
 25    buildsegtree(v*2+1,mid+1,r);
 26}

 27
 28void insertseg(int v,int l,int r,int c)
 29{
 30    if( Segtree[v].color != c)
 31    {
 32        if(Segtree[v].left==&& Segtree[v].right==r)
 33        {
 34            Segtree[v].color=c;
 35            return ;
 36        }

 37        //only one color
 38        if(Segtree[v].color != mixcolor)  
 39        {
 40            Segtree[2*v].color=Segtree[v].color;
 41            Segtree[2*v+1].color=Segtree[v].color;
 42            Segtree[v].color=mixcolor;
 43        }

 44        
 45        int mid=(Segtree[v].left + Segtree[v].right) >> 1 ;
 46
 47        if(r<=mid) insertseg(2*v,l,r,c);
 48        else 
 49            if(mid<l) insertseg(2*v+1,l,r,c);
 50        else 
 51        {
 52            insertseg(2*v,l,mid,c);
 53            insertseg(2*v+1,mid+1,r,c);
 54        }

 55        
 56    }

 57}

 58
 59void count(int v ,int l,int r)
 60{
 61    if(Segtree[v].color!=mixcolor ) 
 62    {
 63        colortable[Segtree[v].color]=true;
 64        return ;
 65    }

 66    int mid=(Segtree[v].left + Segtree[v].right) >> 1;
 67    if(r<=mid) count(2*v,l,r);
 68    else if(mid<l) count(2*v+1,l,r);
 69        else 
 70        {
 71            count(2*v,l,mid);
 72            count(2*v+1,mid+1,r);
 73        }

 74}

 75
 76int main()
 77{
 78    int L,T,O,i,sum=0;
 79    char op;
 80    int a,b,c;
 81    scanf("%d%d%d",&L,&T,&O);
 82    buildsegtree(1,1,L);
 83    while(O--)
 84    {
 85        scanf(" %c",&op);
 86        if(op=='C')
 87        {
 88            scanf("%d%d%d",&a,&b,&c);
 89            if(a>b) {sum=a;a=b;b=sum;}
 90            insertseg(1,a,b,c);
 91        }

 92        else 
 93        {
 94            scanf("%d%d",&a,&b);
 95            if(a>b) {sum=a;a=b;b=sum;}
 96            count(1,a,b);
 97            sum=0;
 98            for(i=1;i<=30;i++)
 99                if(colortable[i]==true)
100                {
101                    sum++;
102                    colortable[i]=false;
103                }

104            printf("%d\n",sum);            
105        }

106    }

107    return 0;
108}

109
110
111
112
posted on 2009-04-16 17:01 wyiu 阅读(315) 评论(1)  编辑 收藏 引用 所属分类: POJ

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