//用于计数的线段树
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论文集 薛矛 《解决动态统计问题的两把利刃——剖析线段树与矩形切割》