线段树是一种作用于静态区间上的数据结构，可以高效查询连续区间和单点，类似于一种静态的分治。他最迷人的地方在于“lazy标记”，对于lazy标记一般随我们从父区间进入子区间而下传，最终给到叶子节点，但还有一种做法就是对于作用域一整个区间的标记，就将其放置在此区间节点，查询时再结算其贡献，但无论怎样我们都要保证我们查询到的区间信息的真实性完整性，这就意味着我们接触一个区间若要了解到他的全部有用信息，并不用进入其下层区间（以上两种标记方式往往再结合出现时有巧妙的用处）。于是我们必须高效地合并子区间的信息以维护此区间的信息，对于多数信息我们可以在O（1）时间内高效完成，但是有一些时候我们的合并并不顺利，并不能直接结算，这个时候我们会多记录一些附加信息来便于合并，但是如果这样行不通我们还有另外一种高效的方式，就是在合并的时候我们再对子区间进行分治（往往利用线段树静态分治的天然优势），如果能得到O（log）的复杂度（或者其他可以接受的复杂度），那么就是可行的，这种方法在题目中的三道题中均有应用。
关于【BZOJ 2957】楼房重建，比较裸，直接讲解下两道。
Codechef COT5 Count on a Treap
关于这道题你一看题干就不能去打Treap。我们想一想笛卡尔树，那么我们就把这些点用key值（二叉树）排序，然后发现得到的区间里，如果用val值（堆）从大到小切割区间，就得到了我们想要的Treap。两个数之间的最大值（val）就他们的lca，那么我们又发现，每个点向两边的上升序列长度和就是他的深度，这样我们就得到了一种可行方案，现在我们就是要找上升序列列长度，方法同上题。
#pragma GCC optimize("O3")#include #include #include #include #define mid ((l+r)>>1)typedef long long LL;const LL N=200010;typedef std::pair pii;struct Segment_Tree{ Segment_Tree *ch[2]; int zlen,ylen,pos;LL max; inline void pushup(){ if(ch[0]->max>ch[1]->max) max=ch[0]->max,pos=ch[0]->pos; else max=ch[1]->max,pos=ch[1]->pos; }}*root,node[N<<4];int n,sz,T;LL q[N][3];pii poi[N];inline void build(Segment_Tree *&p,int l,int r){ p=node+(sz++),p->zlen=p->ylen=1; if(l==r){p->max=0,p->pos=l;return;} build(p->ch[0],l,mid),build(p->ch[1],mid+1,r); p->pushup();}inline int zcalc(Segment_Tree *p,int l,int r,LL max){ if(p==NULL||p->max<=max)return 0; if(l==r)return p->max>max; if(p->ch[0]->max<=max)return zcalc(p->ch[1],mid+1,r,max); else return zcalc(p->ch[0],l,mid,max)+p->zlen-p->ch[0]->zlen;}inline int ycalc(Segment_Tree *p,int l,int r,LL max){ if(p==NULL||p->max<=max)return 0; if(l==r)return p->max>max; if(p->ch[1]->max<=max)return ycalc(p->ch[0],l,mid,max); else return ycalc(p->ch[1],mid+1,r,max)+p->ylen-p->ch[1]->ylen;}inline void U(Segment_Tree *p,int l,int r,int pos,LL val){ if(l==r){p->max=val;return;} if(pos<=mid)U(p->ch[0],l,mid,pos,val); else U(p->ch[1],mid+1,r,pos,val); p->pushup(); p->zlen=p->ch[0]->zlen+zcalc(p->ch[1],mid+1,r,p->ch[0]->max); p->ylen=p->ch[1]->ylen+ycalc(p->ch[0],l,mid,p->ch[1]->max);}inline pii Q(Segment_Tree *p,int l,int r,int z,int y){ if(z<=l&&r<=y)return std::make_pair(p->max,p->pos); pii ret=std::make_pair(-1,-1),temp; if(z<=mid)temp=Q(p->ch[0],l,mid,z,y); if(temp.first>ret.first)ret=temp; if(mid ch[1],mid+1,r,z,y); if(temp.first>ret.first)ret=temp; return ret;}inline void Qz(Segment_Tree *p,int l,int r,int z,int y,int &ans,LL &max){ if(z<=l&&r<=y){ans+=zcalc(p,l,r,max),max=std::max(max,p->max);return;} if(z<=mid)Qz(p->ch[0],l,mid,z,y,ans,max); if(mid ch[1],mid+1,r,z,y,ans,max);}inline void Qy(Segment_Tree *p,int l,int r,int z,int y,int &ans,LL &max){ if(z<=l&&r<=y){ans+=ycalc(p,l,r,max),max=std::max(max,p->max);return;} if(mid ch[1],mid+1,r,z,y,ans,max); if(z<=mid)Qy(p->ch[0],l,mid,z,y,ans,max);}inline int Q(int pos){ int ret=0,ans=0;LL max=poi[pos].second; if(pos!=1)Qy(root,1,n,1,pos-1,ans,max); ret+=ans,ans=0,max=poi[pos].second; if(pos!=n)Qz(root,1,n,pos+1,n,ans,max); ret+=ans;return ret;}int main(){ scanf("%d",&T);for(int i=1;i<=T;++i){ scanf("%lld",&q[i][0]); if(q[i][0]&1)scanf("%lld",&q[i][1]); else scanf("%lld%lld",&q[i][1],&q[i][2]); if(q[i][0]==0)poi[++n]=std::make_pair(q[i][1],q[i][2]); } std::sort(poi+1,poi+(n+1)),build(root,1,n); for(int i=1,pos,l,r,mi;i<=T;++i) switch(q[i][0]){ case 0: pos=std::lower_bound(poi+1,poi+(n+1),std::make_pair(q[i][1],0LL))-poi; U(root,1,n,pos,q[i][2]);break; case 1: pos=std::lower_bound(poi+1,poi+(n+1),std::make_pair(q[i][1],0LL))-poi; U(root,1,n,pos,0);break; case 2: l=std::lower_bound(poi+1,poi+(n+1),std::make_pair(q[i][1],0LL))-poi; r=std::lower_bound(poi+1,poi+(n+1),std::make_pair(q[i][2],0LL))-poi; if(l>r)l^=r^=l^=r;mi=Q(root,1,n,l,r).second; printf("%d\n",Q(l)+Q(r)-Q(mi)*2);break; }} 【NOIP模拟赛】Weed
这道题十分巧妙，我们在线段树上记录三个值，要删之前的多少点，剩下多少点，剩下多少东西，然后单点修改，查询root，维护同理。
#pragma GCC optimize("O3")#include #include #include #include #define mid ((l+r)>>1)const int N=200010;inline void read(int &sum){ register char ch=getchar(); for(sum=0;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';sum=(sum<<1)+(sum<<3)+ch-'0',ch=getchar());}struct Segment_Tree{ Segment_Tree *ch[2]; int del,sum,num;}*root,node[N<<2];int sz,n,m;inline void build(Segment_Tree *&p,int l,int r){ p=node+(sz++);if(l==r)return; build(p->ch[0],l,mid),build(p->ch[1],mid+1,r);}inline int Q(Segment_Tree *p,int l,int r,int del){ if(p->num<=del)return 0; if(l==r)return p->sum; if(p->ch[1]->num>=del)return p->sum-p->ch[1]->sum+Q(p->ch[1],mid+1,r,del); else return Q(p->ch[0],l,mid,del-p->ch[1]->num+p->ch[1]->del);}inline void U(Segment_Tree *p,int l,int r,int pos,int key,int opt){ if(l==r){ if(opt)p->sum=0,p->num=0,p->del=key; else p->del=0,p->num=1,p->sum=key; return; } if(pos<=mid)U(p->ch[0],l,mid,pos,key,opt); else U(p->ch[1],mid+1,r,pos,key,opt); if(p->ch[0]->num<=p->ch[1]->del) p->del=p->ch[0]->del+p->ch[1]->del-p->ch[0]->num,p->sum=p->ch[1]->sum,p->num=p->ch[1]->num; else p->del=p->ch[0]->del,p->num=p->ch[1]->num+p->ch[0]->num-p->ch[1]->del, p->sum=p->ch[1]->sum+Q(p->ch[0],l,mid,p->ch[1]->del);}int main(){ read(n),read(m),build(root,1,n); for(int i=1,x,y;i<=n;++i) read(x),read(y),U(root,1,n,i,y,x); int pos,opt,key; while(m--){ read(pos),read(opt),read(key); U(root,1,n,pos,key,opt); printf("%d\n",root->sum); }}