看一个例子
[1,10]是1色
现在插入颜色为2的[4,7]
咋办捏？
错的函数：
-------------------------------------------------------------
void cover (int b,int e,int s,int c){
     //printf("Cover from %4d to %4d in setment %4d (%4d,%4d)Colored %x\n",b,e,s,seg[s].b,seg[s].e,c);
     segment &ts=seg[s];
     //segment ts;
     if (ts.b==b && ts.e==e){
        //printf("Colored\n");
        ts.cd=1;
        ts.c =c;
        return ;
        }
     int mid=(ts.b + ts.e)>>1;
     if (ts.cd==1){
        //printf("begin f %4d\n",mid);
        ts.cd=0;
        if (b>ts.b)
           if   (b-1<=mid)
                cover(ts.b,b-1,s<<1,ts.c);
           else{
                cover(ts.b,mid,s<<1,ts.c);
                cover(mid+1,b-1,(s<<1)+1,ts.c);
                }
        if (e<ts.e)
           if   (e>=mid)//e+1>=mid+1
                cover(e+1,ts.e,(s<<1)+1,ts.c);
           else {
                cover(e+1,mid,s<<1,c);
                cover(mid+1,ts.e,(s<<1)+1,c);
                }
        }
     ts.cd=0;
     
     if   (e <= mid)
          cover(b,e,s<<1    ,c);
     else if (b>mid)//b>=mid+1
          cover(b,e,(s<<1)+1,c);
     else{
          cover(b    ,mid,s<<1    ,c);
          cover(mid+1,e  ,(s<<1)+1,c);
          }
     }
正确的函数
----------------------------------------------------------------------
void cover (int b,int e,int s,int c){
     //printf("Cover from %4d to %4d in setment %4d (%4d,%4d)Colored %x\n",b,e,s,seg[s].b,seg[s].e,c);
     segment &ts=seg[s];
     //segment ts;
     if (ts.b==b && ts.e==e){
        //printf("Colored\n");
        ts.cd=1;
        ts.c =c;
        return ;
        }
     int mid=(ts.b + ts.e)>>1;
     if (ts.cd==1){
        cover(ts.b ,mid ,s<<1    ,ts.c);
        cover(mid+1,ts.e,(s<<1)+1,ts.c);
        }
     ts.cd=0;
     
     if   (e <= mid)
          cover(b,e,s<<1    ,c);
     else if (b>mid)//b>=mid+1
          cover(b,e,(s<<1)+1,c);
     else{
          cover(b    ,mid,s<<1    ,c);
          cover(mid+1,e  ,(s<<1)+1,c);
          }

• Re:Wa的原因 (23) comzyh 2010-10-13 13:13:34