posts - 217, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
//用于计数的线段树
class SegTree{
    
static const int UPBOUND=(1<<17);//UPBOUND需为2的幂,所有线段应在[0,UPBOUND)上
    int segbg[(UPBOUND<<1)];
    
int segen[(UPBOUND<<1)];
    
int cover[(UPBOUND<<1)];//覆盖次数
    int a,b,x;

    
void _makeSegTree(int i,int a,int b)
    {
        segbg[i]
=a;
        segen[i]
=b;
        
if(a+1<b){//如果线段长度大于1
            _makeSegTree(i*2+1,a,a+(b-a)/2);
            _makeSegTree(i
*2+2,a+(b-a)/2,b);
        }
    }

    
void _insertSeg(int i)
    {
        
if(a<=segbg[i] && segen[i]<=b){
            cover[i]
+=x;
        }
        
else if(segen[i]-segbg[i]>1){
            
if(a < segbg[i]+(segen[i]-segbg[i])/2){
                _insertSeg(i
*2+1);
            }
            
if(segbg[i]+(segen[i]-segbg[i])/2 <= b){
                _insertSeg(i
*2+2);
            }
        }
    }

    
void _deleteSeg(int i)
    {
        
if(a<=segbg[i] && segen[i]<=b){
            cover[i]
-=x;
        }
        
else if(segen[i]-segbg[i]>1){
            
if(a < segbg[i]+(segen[i]-segbg[i])/2){
                _deleteSeg(i
*2+1);
            }
            
if(segbg[i]+(segen[i]-segbg[i])/2 <= b){
                _deleteSeg(i
*2+2);
            }
        }
    }

    
int _queryCover(int i,int n)
    {
        
if(n<segbg[i]+(segen[i]-segbg[i])/2){
            
return cover[i]+((segen[i]-segbg[i]>1)?_queryCover(i*2+1,n):0);
        }
        
else {
            
return cover[i]+((segen[i]-segbg[i]>1)?_queryCover(i*2+2,n):0);
        }
    }

public:
    SegTree(){
        clearCover();
        makeSegTree(
0,UPBOUND);
    }
    
void makeSegTree(int a,int b){_makeSegTree(0,a,b);}
    
void clearCover(){mset(cover,0);}
    
//默认区间为[a,b)
    void insertSeg(int a,int b,int x=1){
        SegTree::a
=a;
        SegTree::b
=b;
        SegTree::x
=x;
        _insertSeg(
0);
    }
    
void deleteSeg(int a,int b,int x=1){
        SegTree::a
=a+1;
        SegTree::b
=b+1;
        SegTree::x
=x;
        _deleteSeg(
0);
    }
    
int queryCover(int n){return _queryCover(0,n);}
}segTree;

//用于着色的线段树,颜色可以重复着,后着的颜色覆盖之前的。
//颜色编号从1开始,特别地,color[i]=0表示未着色,color[i]=-1表示该线段上颜色不一致
class SegTree{
    
static const int UPBOUND=(1<<10);//UPBOUND需为2的幂,所有线段应在[0,UPBOUND)上
    int segbg[(UPBOUND<<1)];
    
int segen[(UPBOUND<<1)];
    
int color[(UPBOUND<<1)];
    
int bj[(UPBOUND<<1)];
    
int a,b,x;

    
void mainTain(int i){
        
if(bj[i]){
            color[i]
=bj[i];
            
if(segen[i]-segbg[i]>1){
                bj[i
*2+1]=bj[i];
                bj[i
*2+2]=bj[i];
            }
            bj[i]
=0;
        }
    }

    
void _makeSegTree(int i,int a,int b){
        segbg[i]
=a;
        segen[i]
=b;
        
if(a+1<b){//如果线段长度大于1
            _makeSegTree(i*2+1,a,a+(b-a)/2);
            _makeSegTree(i
*2+2,a+(b-a)/2,b);
        }
    }

    
void _colorSeg(int i){
        mainTain(i);
        
if(a<=segbg[i] && segen[i]<=b){
            bj[i]
=x;
        }
        
else if(segen[i]-segbg[i]>1){
            color[i]
=-1;//-1表示这段的颜色不一致
            if(a < segbg[i]+(segen[i]-segbg[i])/2){
                _colorSeg(i
*2+1);
            }
            
if(segbg[i]+(segen[i]-segbg[i])/2 <= b){
                _colorSeg(i
*2+2);
            }
        }
    }

    
int _queryColor(int i,int n){
        mainTain(i);
        
if(color[i]!=-1)return color[i];
        
if(n<segbg[i]+(segen[i]-segbg[i])/2){
            
return _queryColor(i*2+1,n);
        }
        
else {
            
return _queryColor(i*2+2,n);
        }
    }

public:
    SegTree(){
        clearColor();
        makeSegTree(
0,UPBOUND);
    }
    
void makeSegTree(int a,int b){_makeSegTree(0,a,b);}
    
void clearColor(){
        mset(color,
0);
        mset(bj,
0);
    }
    
//为线段[a,b)着颜色x
    void colorSeg(int a,int b,int x){
        SegTree::a
=a;
        SegTree::b
=b;
        SegTree::x
=x;
        _colorSeg(
0);
    }
    
//询问点n的颜色(即线段[n,n+1)上的颜色)
    int queryColor(int n){return _queryColor(0,n);}
}segTree;

参考资料:国家集训队2004论文集 薛矛 《解决动态统计问题的两把利刃——剖析线段树与矩形切割》

只有注册用户登录后才能发表评论。