线段树

围观dalao:http://www.cnblogs.com/DragoonKiller/p/4295945.html#3135008
dalao2:http://www.yhzq-blog.cc/%e7%ba%bf%e6%ae%b5%e6%a0%91%e9%ab%98%e9%98%b6%e6%80%bb%e7%bb%93/
资料:http://blog.csdn.net/zearot/article/details/48299459
进阶:http://www.vyess.top/archives/301

最终基本模板
HDU1754

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 200017;
const int maxn = N<<2;
const int INF = 0x3f3f3f3f;
int n,m,a[N],l,r,k,v;
struct ST{
    int lc[maxn],rc[maxn],lx[maxn],rx[maxn],mx[maxn],mn[maxn],lazy[maxn];
    int root,tot;
    void init(){
        root=tot=0;
//        memset(lx,-1,sizeof lx);
//        memset(rx,-1,sizeof rx);
//        memset(rc,-1,sizeof rc);
//        memset(lc,-1,sizeof lc);
    }
    void pu(int now){
        mx[now]=max(mx[lc[now]],mx[rc[now]]);
        mn[now]=min(mn[lc[now]],mn[rc[now]]);
    }
    void pd(int now){
        if(lazy[now]){
            ;;;;;;;
        }
    }
    int build(int l,int r){
        int now=tot++,m=(l+r)>>1;
        lx[now]=l;rx[now]=r;
        if(r-l<1){
            mn[now]=mx[now]=a[l];
            return now;//NOTE 
        }
        lc[now]=build(l,m);
        rc[now]=build(m+1,r);
        pu(now);
        return now;
    }
    void update(int now,int k,int v){
        if(lx[now]==-1||rx[now]==-1) return;
        int m=(lx[now]+rx[now])>>1;
        if(lx[now]==rx[now]){
            mn[now]=v;
            mx[now]=v;
            return;
        }
        if(k<=m) update(lc[now],k,v);//左边包含m 
        else update(rc[now],k,v);
        pu(now);
    }
    int query(int now,int L,int R){
        if(lx[now]>R||rx[now]<L) return -INF;//完全越界 
        if(lx[now]>=L&&rx[now]<=R) return mx[now];//完全内部
        return max(query(lc[now],L,R),query(rc[now],L,R)); 
    }
}st;
char str[5];
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        st.init();st.build(1,n);
        for(int i = 0; i < m; i++){
            scanf("%s",str);
            if(str[0]=='Q'){
                scanf("%d%d",&l,&r);
                printf("%d\n",st.query(0,l,r));
            }
            else{
                scanf("%d%d",&k,&v);
                st.update(0,k,v);
            }
        }
    }
    return 0;
} 

lazy
SCU3099

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5+11;
int a[maxn],l,r,n,q;ll v;
char str[10];
struct ST{
    int lc[maxn<<2],rc[maxn<<2],lx[maxn<<2],rx[maxn<<2];
    ll lazy[maxn<<2],sum[maxn<<2];
    ll root,tot;
    void init(){
        root=tot=0;
        memset(lazy,0,sizeof lazy);
    }
    ll node(){
        lc[tot]=rc[tot]=lx[tot]=rx[tot]=sum[tot]=lazy[tot]=0;
        return tot++;
    }
    inline void pu(int now){
        sum[now]=sum[lc[now]]+sum[rc[now]];
    }
    inline ll len(int now){
        return rx[now]-lx[now]+1;
    }
    inline void pd(int now){
        if(lazy[now]){
//            sum[now]+=(rx[now]-lx[now]+1)*lazy[now];
            lazy[lc[now]]+=lazy[now];
            lazy[rc[now]]+=lazy[now];
            sum[lc[now]]+=lazy[now]*len(lc[now]);
            sum[rc[now]]+=lazy[now]*len(rc[now]);
            lazy[now]=0;
        } 
    }
    ll build(int l,int r){
        int now=node();
        lx[now]=l;rx[now]=r;
        if(l==r){
            sum[now]=a[l];
            return now; 
        }
        int m=(l+r)>>1;
        lc[now]=build(l,m);//1 l
        rc[now]=build(m+1,r);
        pu(now);
        return now;
    }
    void update(int now,int L,int R,ll v){
//        if(lx[now]==rx[now]){
        if(L<=lx[now]&&rx[now]<=R){
            sum[now]+=len(now)*v; //向上显示正确 
            lazy[now]+=v;///////////
//            pd(now);//WA if added 
            return;
        }
        int m=(lx[now]+rx[now])>>1;
        pd(now);//////////////
        if(L<=m) update(lc[now],L,R,v);
//        else update(rc[now],k,v);
        if(R>m) update(rc[now],L,R,v);
        pu(now);
    }
    ll query(int now,int L,int R){
        if(L<=lx[now]&&rx[now]<=R){
            return sum[now];
        }
        //wawawa
        pd(now);
        //wawawa
        int m=(lx[now]+rx[now])>>1;
        ll ans=0;
        if(L<=m) ans+=query(lc[now],L,R);
        if(r>m) ans+=query(rc[now],L,R);
        return ans;
    }
}st;
int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        st.init();st.build(1,n);
        for(int i = 1; i <= q; i++){
            scanf("%s",str);
            if(str[0]=='C'){
                scanf("%d%d%lld",&l,&r,&v);
                st.update(st.root,l,r,v);
            } 
            else{
                scanf("%d%d",&l,&r);
                printf("%lld\n",st.query(st.root,l,r));
            }
        }
    }
    return 0;
} 

美化版

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
typedef long long ll;
int a[maxn],l,r,n,q;ll v;
char str[10];
struct ST{
    int lc[maxn<<2],rc[maxn<<2],lx[maxn<<2],rx[maxn<<2];;
    ll lazy[maxn<<2],sum[maxn<<2];
    int root,tot;
    inline void init(){
        root=tot=0;
        memset(lazy,0,sizeof lazy);
    }
    inline int node(){
        lc[tot]=rc[tot]=lx[tot]=rx[tot]=0;
        lazy[tot]=sum[tot]=0;
        return tot++;
    }
    inline void pu(int now){
        sum[now]=sum[lc[now]]+sum[rc[now]];
    }
    int build(int l,int r){
        int now=node();
        lx[now]=l;rx[now]=r;
        if(l==r){
            sum[now]=a[l];
            return now;
        }
        int m=(l+r)>>1;
        lc[now]=build(l,m);
        rc[now]=build(m+1,r);
        pu(now);
        return now; 
    }
    inline int len(int now){
        return rx[now]-lx[now]+1;
    }
    inline void pd(int now){
        if(lazy[now]){
            sum[lc[now]]+=len(lc[now])*lazy[now];
            sum[rc[now]]+=len(rc[now])*lazy[now];
            lazy[lc[now]]+=lazy[now];
            lazy[rc[now]]+=lazy[now];
            lazy[now]=0; 
        }
    }
    inline void update(int now,int L,int R,ll v){
        if(L<=lx[now]&&rx[now]<=R){
            sum[now]+=len(now)*v;
            lazy[now]+=v;
            return;
        }
        int m=(lx[now]+rx[now])>>1;
        pd(now);
        if(L<=m) update(lc[now],L,R,v);
        if(R>m) update(rc[now],L,R,v);
        pu(now); 
    }
    ll query(int now,int L,int R){
        if(L<=lx[now]&&rx[now]<=R){
            return sum[now];
        }
        int m=(lx[now]+rx[now])>>1;
        pd(now);
        ll ans=0;
        if(L<=m) ans+=query(lc[now],L,R);
        if(R>m) ans+=query(rc[now],L,R);
        return ans;
    }
}st;
int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        st.init();st.build(1,n);
        for(int i = 1; i <= q; i++){
            scanf("%s",str);
            if(str[0]=='C'){
                scanf("%d%d%lld",&l,&r,&v);
                st.update(st.root,l,r,v);
            } 
            else{
                scanf("%d%d",&l,&r);
                printf("%lld\n",st.query(st.root,l,r));
            }
        }
    }
    return 0;
} 

multi-lazy
http://blog.csdn.net/codeforcer/article/details/46867851
HDU1166
测试模板(旧) 343ms

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1e6;
int st[maxn<<2],a[maxn],n;
void pushup(int rt){
    st[rt]=st[rt<<1]+st[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        st[rt]=a[l];
        return;
    }
    int m = (l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt); 
}
void update(int k,int v,int l,int r,int rt){
    if(l==r){
        st[rt]+=v;
        return;
    }
    int m = (l+r)>>1;
    if(k<=m) update(k,v,l,m,rt<<1);
    else update(k,v,m+1,r,rt<<1|1);
    pushup(rt);
}

int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r) return st[rt];
    int m = (l+r)>>1;
    int ans = 0;
    if(L<=m) ans+=query(L,R,l,m,rt<<1);
    if(R>m) ans+=query(L,R,m+1,r,rt<<1|1);
    return ans;
}
void update(int k,int v){
    update(k,v,1,n,1);
}
int query(int L,int R){
    return query(L,R,1,n,1);
}
int main(){
    int k,v,s,e,flag;
    int T,kase=0;scanf("%d",&T);
    while(T--){
        ++kase;flag=0;
        cin>>n;memset(st,0,sizeof st);
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        build(1,n,1);
        char str[100];
        while(scanf("%s",str)!=EOF){
            if(str[0]=='E') break;
            else if(str[0]=='A'){
                scanf("%d%d",&k,&v); 
                update(k,v);
            }
            else if(str[0]=='S'){
                scanf("%d%d",&k,&v); 
                update(k,-v);
            }
            else if(str[0]=='Q'){
                scanf("%d%d",&s,&e); 
                if(flag==0){
                    flag=1;
                    printf("Case %d:\n",kase);
                }
                printf("%d\n",query(s,e));
            }
        }
    }
    return 0;
}

POJ3264
小技巧可直接省去a数组

    if(l==r){
//        st[rt].mmin=st[rt].mmax=a[l];
        scanf("%d",&st[rt].mmax);st[rt].mmin=st[rt].mmax;
        return;

主席树
参考资料:http://www.cnblogs.com/Empress/p/4652449.html

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+11;
int L[maxn<<5],R[maxn<<5],st[maxn<<5];
int tot;
int a[maxn],T[maxn],hash[maxn];
int build(int l,int r){
    int rt=(++tot);
    st[rt]=0;
    if(l<r){
        int m = (l+r)>>1;
        L[rt]=build(l,m); //0 1 2 3 4....
        R[rt]=build(m+1,r);
    }
    return rt;
}
int update(int pre,int l,int r,int x){
    int rt=(++tot);//new root
    L[rt]=L[pre];R[rt]=R[pre];st[rt]=st[pre]+1;//?
    if(l<r){
        int m = (l+r)>>1;
        if(x<=m) L[rt]=update(L[pre],l,m,x);
        else R[rt]=update(R[pre],m+1,r,x);
    }
    return rt;
}
int query(int u,int v,int l,int r,int k){
    if(l>=r) return l;
    int m = (l+r)>>1;
    int num=st[L[v]]-st[L[u]];//?递归处理两树相减 
    if(num>=k) return query(L[u],L[v],l,m,k);
    else return query(R[u],R[v],m+1,r,k-num);
}
int main(){
    tot=0;
    int n,m; scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        hash[i]=a[i];
    }
    sort(hash+1,hash+1+n);
    int d=unique(hash+1,hash+1+n)-hash-1;
    T[0]=build(1,d);
    for(int i = 1; i <= n; i++){
        int x = lower_bound(hash+1,hash+1+n,a[i])-hash;
        T[i]=update(T[i-1],1,d,x);//return new rootID
//        cout<<T[i]<<endl;
    }
    for(int i = 1; i <= m; i++){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        int x = query(T[l-1],T[r],1,d,k);
        printf("%d\n",hash[x]);
    }
    return 0;
}

单点修改
ZOJ2112(未完成)

/#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<stdio.h>
#include <string>
#include<string.h>
#include<utility>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define eps 1e-8
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define ll long long int
#define mod 1000000007
#define maxn 60005
#define maxm 2500005
int m,n,nn,tot;
int a[maxn],f[maxn],T[maxn],S[maxn];
int sum[maxm],l[maxm],r[maxm];
int use[maxn];
int h(int x){//该值在离散化后线段树的位置
    return lower_bound(f+1,f+1+nn,x)-f;
}
void update(int pr,int lx,int rx,int v,int k){//插入,即新建第i个线段树
    l[++tot]=l[pr];r[tot]=r[pr];sum[tot]=sum[pr]+k;
    if(lx==rx) return;
    int mid=(lx+rx)>>1;
    if(v<=mid) {
            l[tot]=tot+1;
            update(l[pr],lx,mid,v,k);
    }
    else {
            r[tot]=tot+1;
            update(r[pr],mid+1,rx,v,k);
    }
}
void build(int rt,int lx,int rx){//初始化空树
    sum[rt]=0;
    if(lx==rx) return;
    l[rt]=++tot;
    int mid=(lx+rx)>>1;
    build(tot,lx,mid);
    r[rt]=++tot;
    build(tot,mid+1,rx);
}
int lowbit(int x){return x&(-x);}
int Sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=sum[l[use[i]]];
    return res;
}
void add(int x,int v,int k)
 {
     int tt;
    for(int i=x;i<=n;i+=lowbit(i)){
        tt=S[i];
        S[i]=tot+1;
        update(tt,1,nn,v,k);
    }
 }
int query(int L,int R,int k){
    for(int i=L-1;i;i-=lowbit(i)) use[i]=S[i];//use记录要操作的线段树下标
    for(int i=R;i;i-=lowbit(i)) use[i]=S[i];
    int lx=1,rx=nn;
    int lt=T[L-1],rt=T[R];
    while(lx<rx){
        int mid=(lx+rx)>>1;
        int tmp=Sum(R)-Sum(L-1)+sum[l[rt]]-sum[l[lt]];
        if(k<=tmp){
            rx=mid;
            for(int i=L-1;i;i-=lowbit(i)) use[i]=l[use[i]];
            for(int i=R;i;i-=lowbit(i)) use[i]=l[use[i]];
            lt=l[lt];rt=l[rt];
        }
        else{
            lx=mid+1;k-=tmp;
            for(int i=L-1;i;i-=lowbit(i)) use[i]=r[use[i]];
            for(int i=R;i;i-=lowbit(i)) use[i]=r[use[i]];
            lt=r[lt];rt=r[rt];
        }
    }
    return f[lx];
}
char op[5];
int q[10005][4],t;
int main()
{
    rd(t);
    while(t--){
    rd2(n,m);
    for(int i=1;i<=n;i++) {
            rd(a[i]);f[i]=a[i];
    }
    nn=n;
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='Q') {
            scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]);
            q[i][0]=1;
        }
        else{
            scanf("%d%d",&q[i][1],&q[i][2]);
            q[i][0]=0;
            f[++nn]=q[i][2];
        }
    }
    sort(f+1,f+1+nn);
    nn=unique(f+1,f+1+nn)-f-1;//离散化线段树,并去重
    tot=0;
    T[0]=0;
    build(0,1,nn);
    for(int i=1;i<=n;i++){
        T[i]=tot+1;          //T[i]记录第i个线段树的根
        update(T[i-1],1,nn,h(a[i]),1);
    }
    for(int i=1;i<=n;i++) S[i]=T[0];
   // int L,R,k,x;
    for(int i=1;i<=m;i++){
        if(q[i][0]){
            printf("%d\n",query(q[i][1],q[i][2],q[i][3]));
        }
        else{
            add(q[i][1],h(a[q[i][1]]),-1);
            add(q[i][1],h(q[i][2]),1);
            a[q[i][1]]=q[i][2];
        }
    }
    }
    return 0;
}
//just test

区间修改
SPOJ - TTM

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+11;
int lc[maxn<<5],rc[maxn<<5],lazy[maxn<<5],T[maxn],tot;
ll st[maxn<<5];
int n,mm,cur,L,R,v,t;char str[50];
inline void init(){
    memset(lc,0,sizeof lc);memset(rc,0,sizeof rc);memset(st,0,sizeof st);
    memset(lazy,0,sizeof lazy);memset(T,0,sizeof T);
    tot=0;cur=0;
}
inline int build(int l,int r){
    int now=tot++;
    if(l==r){
        scanf("%lld",&st[now]);
        return now;
    }
    int m=(l+r)>>1;
    lc[now]=build(l,m);
    rc[now]=build(m+1,r);
    st[now]=st[lc[now]]+st[rc[now]];
    return now;
}
inline int update(int pre,int L,int R,int v,int l,int r){
    int now=tot++;
    lc[now]=lc[pre];rc[now]=rc[pre];lazy[now]=lazy[pre];st[now]=st[pre];
    st[now]+=(ll)v*(R-L+1);
    if(L==l&&R==r){
        lazy[now]+=v;
        return now;
    }
    int m=(l+r)>>1;
    if(R<=m) lc[now]=update(lc[now],L,R,v,l,m);
    else if(L>m) rc[now]=update(rc[now],L,R,v,m+1,r);
    else{
        lc[now]=update(lc[now],L,m,v,l,m);
        rc[now]=update(rc[now],m+1,R,v,m+1,r);
    }
    return now;
}
inline ll query(int pre,int L,int R,int l,int r){
    if(L==l&&r==R) return st[pre];
    int m = (l+r)>>1;
    ll ans = (ll)lazy[pre]*(R-L+1);
    if(R<=m) return ans+query(lc[pre],L,R,l,m);
    else if(L>m) return ans+query(rc[pre],L,R,m+1,r);
    else return ans+query(lc[pre],L,m,l,m)+query(rc[pre],m+1,R,m+1,r);
}
int main(){
    while(scanf("%d%d",&n,&mm)!=EOF){
        tot=0;cur=0;memset(lazy,0,sizeof lazy);
        T[0]=build(1,n);
        for(int i = 0; i < mm; i++){
            scanf("%s",str);
            if(str[0]=='C'){
                scanf("%d%d%d",&L,&R,&v);
                cur++;
                T[cur]=update(T[cur-1],L,R,v,1,n);
            }
            else if(str[0]=='Q'){
                scanf("%d%d",&L,&R);
                printf("%lld\n",query(T[cur],L,R,1,n));
            }
            else if(str[0]=='H'){
                scanf("%d%d%d",&L,&R,&t);
                printf("%lld\n",query(T[t],L,R,1,n));
            }
            else{
                scanf("%d",&cur);
            }
        }
    }
    return 0;
}

???
参考资料:https://segmentfault.com/a/1190000010831794

线段树维护几何
UVA1455

#include<bits/stdc++.h>
#define clr(a) memset((a),0,sizeof (a));
using namespace std;
const int maxn = 1e5+11;
const int maxy = 1e6+11;
struct ST{
    int lc[maxy<<2],rc[maxy<<2],lx[maxy<<2],rx[maxy<<2];
    int city[maxy<<2],state[maxy<<2];
    int addc[maxy<<2],adds[maxy<<2];
    int tot,root;
    void init(){
        tot=root=0;
        clr(city);clr(state);
        clr(addc);clr(adds);
    }
    int node(){
        lc[tot]=rc[tot]=0;
        return tot++;
    }
    int build(int l,int r){
        int now=node();
        lx[now]=l;rx[now]=r;
        if(l==r) return now;
        int m=l+r>>1;
        lc[now]=build(l,m);
        rc[now]=build(m+1,r);
        return now;
    }
    void pd(int now){
        if(addc[now]){
            city[lc[now]]+=addc[now];
            city[rc[now]]+=addc[now];
            addc[lc[now]]+=addc[now];
            addc[rc[now]]+=addc[now];
            addc[now]=0;
        }
        if(adds[now]){
            state[lc[now]]+=adds[now];
            state[rc[now]]+=adds[now];
            adds[lc[now]]+=adds[now];
            adds[rc[now]]+=adds[now];
            adds[now]=0;
        }
    }
    void update(int now,int L,int R,int v,int flag){
        if(L<=lx[now]&&rx[now]<=R){
            if(!flag){
                city[now]+=v;
                addc[now]+=v;
                return;
            }
            else{
                state[now]+=v;//没有len
                adds[now]+=v;
                return;
            }
            return;
        }
        int m=lx[now]+rx[now]>>1;
        pd(now);
        if(L<=m) update(lc[now],L,R,v,flag);
        if(R>m) update(rc[now],L,R,v,flag);
    }
    int query(int now,int k,int flag){
        if(lx[now]==rx[now]){
            return flag?state[now]:city[now];
        }
        pd(now); 
        int m=lx[now]+rx[now]>>1;
        if(k<=m) return query(lc[now],k,flag);
        return query(rc[now],k,flag);
    }
}st;
struct UF{
    int p[maxn];
    int city[maxn],state[maxn];
    int low[maxn],high[maxn];
    void init(int y[],int n){
        for(int i = 0; i < n; i++){
            p[i]=i;
            city[i]=state[i]=1;
            low[i]=high[i]=y[i];
        }
    }
    int find(int x){
        return p[x]==x?x:p[x]=find(p[x]);
    }
    void link(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return;
        
        st.update(st.root,low[a]+1,high[a],-city[a],0);
        st.update(st.root,low[a]+1,high[a],-state[a],1);
        
        st.update(st.root,low[b]+1,high[b],-city[b],0);
        st.update(st.root,low[b]+1,high[b],-state[b],1);
        
        if(a>b) swap(a,b);
        p[b]=a;
        low[a]=min(low[a],low[b]);
        high[a]=max(high[a],high[b]);
        city[a]+=city[b]; state[a]=1;
        st.update(st.root,low[a]+1,high[a],city[a],0);
        st.update(st.root,low[a]+1,high[a],state[a],1);
    }
}uf;
int y[maxn],t;
char str[1111];
int main(){
    int T,q,n,a,b;double pos; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 0; i < n; i++) scanf("%d%d",&t,&y[i]);
        uf.init(y,n);st.init();st.build(0,maxy);
        scanf("%d",&q);
        for(int i = 0; i < q; i++){
            scanf("%s",str);
            if(str[0]=='r'){
                scanf("%d%d",&a,&b);
                uf.link(a,b);
            }
            else{
                scanf("%lf",&pos);
                printf("%d %d\n",st.query(st.root,(int)(pos+1),1),st.query(st.root,(int)(pos+1),0));
            }
        }
    }
    return 0;
}

区间合并
最大连续和(缺少update操作)
LA3938
参考lrj,query部分还需琢磨

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+11;
typedef long long ll;
typedef pair<int,int> P;
ll pre[maxn];
ll sum(int l,int r){//O(1)
    return pre[r]-pre[l-1];
}
ll sum(P p){
    return sum(p.first,p.second);
}
P better(P a,P b){//NOTE:字典序处理
    if(sum(a)!=sum(b)) return sum(a)>sum(b)?a:b;
    return a<b?a:b;//按字典序排序
}
// int qL,qR;
struct ST{
    int mp[maxn<<2],ms[maxn<<2]; P mx[maxn<<2];
    int lc[maxn<<2],rc[maxn<<2],lx[maxn<<2],rx[maxn<<2];
    int root,tot;
    void init(){
        memset(mp,0,sizeof mp);memset(ms,0,sizeof ms);
        memset(mx,0,sizeof mx);
        root=tot=0;
        lc[tot]=rc[tot]=0;
    }
    int node(){
        lc[tot]=rc[tot]=lx[tot]=rx[tot]=mp[tot]=ms[tot]=mx[tot].first=mx[tot].second=0;
        return tot++;
    }
    void pu(int now){
        ll v1=sum(lx[now],mp[lc[now]]);
        ll v2=sum(lx[now],mp[rc[now]]);
        //NOTE:前缀和必然与lx[now]相关联
        if(v1==v2) mp[now]=min(mp[lc[now]],mp[rc[now]]);//NOTE:字典序
        else mp[now]=v1>v2?mp[lc[now]]:mp[rc[now]];

        v1=sum(ms[lc[now]],rx[now]);
        v2=sum(ms[rc[now]],rx[now]);
        if(v1==v2) ms[now]=min(ms[lc[now]],ms[rc[now]]);
        else ms[now]=v1>v2?ms[lc[now]]:ms[rc[now]];

        mx[now]=better(mx[lc[now]],mx[rc[now]]);
        mx[now]=better(mx[now],P(ms[lc[now]],mp[rc[now]]));//中间
        //NOTE:左边的后缀和加右边的前缀和
    }
    int build(int l,int r){
        int now=node();
        lx[now]=l;rx[now]=r;
        if(l==r){
            mp[now]=ms[now]=l;
            mx[now]=P(l,l);
            return now;
        }
        int m=l+r>>1;
        lc[now]=build(l,m);
        rc[now]=build(m+1,r);
        pu(now);
        return now;
    }
    P query_p(int now,int L,int R){
        if(mp[now]<=R) return P(lx[now],mp[now]);//默认L<=m||R>m
        int m=lx[now]+rx[now]>>1;
        if(R<=m) return query_p(lc[now],L,R);
        P i = query_p(rc[now],L,R);//???
        i.first=lx[now];
        return better(i,P(lx[now],mp[lc[now]]));
    }
    P query_s(int now,int L,int R){
        if(L<=ms[now]) return P(ms[now],rx[now]);
        int m=lx[now]+rx[now]>>1;
        if(L>m) return query_s(rc[now],L,R);
        P i = query_s(lc[now],L,R);
        i.second=rx[now];
        return better(i,P(ms[rc[now]],rx[now]));
    }
    P query(int now,int L,int R){
        if(L<=lx[now]&&rx[now]<=R) return mx[now];
        int m=lx[now]+rx[now]>>1;
        if(R<=m) return query(lc[now],L,R);//完全在左子树
        if(L>m) return query(rc[now],L,R);//完全在右子树
        P i1=query_p(rc[now],L,R);
        P i2=query_s(lc[now],L,R);
        P i3=better(query(lc[now],L,R),query(rc[now],L,R));
        return better(P(i2.first,i1.second),i3);//跨区间L<=m||R>m
    }
}st;
int main(){
    int kase=0,n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF){
        pre[0]=0;st.init();
        for(int i = 1; i <= n; i++){
            scanf("%d",&a);
            pre[i]=pre[i-1]+a;
        }
        st.build(1,n);
        printf("Case %d:\n",++kase);
        while(m--){
            scanf("%d%d",&a,&b);
            // ql=l,qR=r;
            P ans=st.query(st.root,a,b);
            printf("%d %d\n",ans.first,ans.second);
        }
    }
    return 0;
}

二进制相关
https://comzyh.com/blog/archives/452/
浅谈线段树在信息学竞赛中的应用
POJ3277离散化入门
WHU1071拆圈成线
HH神总结的线段树专辑 POJ3225
bzoj 2962
Whu 1071 1224 1361 1344
Pku 3225 2482 1177 1029 2182 2750 2104 2528 2828 2777 2886 2761
Zju 2301 1128 1659 2112

二维线段树(β)
这种是自己yy的四分写法,应该和市面上的模板相差不大
树套树怎么写还不太清楚

#include<bits/stdc++.h>
#define ch1 x1,m1,y1,m2
#define ch2 m1+1,x2,y1,m2
#define ch3 x1,m1,m2+1,y2
#define ch4 m1+1,x2,m2+1,y2
#define sz1 (m1-x1+1)*(m2-y1+1)
#define sz2 (x2-m1)*(m2-y1+1)
#define sz3 (m1-x1+1)*(y2-m2)
#define sz4 (x2-m1)*(y2-m2)
#define min(a,b,c,d) min(a,min(b,min(c,d)))
#define max(a,b,c,d) max(a,max(b,max(c,d)))
using namespace std;
const int maxn = 1e5+11;
const int oo = 0x3f3f3f3f;
const int xx = 0x80;
int a[100][100];
struct ST{
    int mn[maxn<<2],mx[maxn<<2];
    void init(){//NOTE
        memset(mn,oo,sizeof mn);
        memset(mx,xx,sizeof mx);
    }
    void pu(int o){
        int ch=o<<2;
        mn[o]=min(mn[ch+1],mn[ch+2],mn[ch+3],mn[ch+4]);
        mx[o]=max(mx[ch+1],mx[ch+2],mx[ch+3],mx[ch+4]);
    }
    void build(int o,int x1,int x2,int y1,int y2){
        if(x1==x2&&y1==y2){
            mn[o]=mx[o]=a[y1][x1];
            return;
        }
        int m1=x1+x2>>1;
        int m2=y1+y2>>1;
        int ch=o<<2;
        if(x1<=m1&&y1<=m2) build(ch+1,ch1);
        if(x2>m1&&y1<=m2) build(ch+2,ch2);
        if(x1<=m1&&y2>m2) build(ch+3,ch3);
        if(x2>m1&&y2>m2) build(ch+4,ch4);
        pu(o);
    }
    void update(int o,int x1,int x2,int y1,int y2,int x,int y,int v){
        if(x1==x2&&y1==y2){
            mn[o]=mx[o]=v;
            return;
        }
        int m1=x1+x2>>1;
        int m2=y1+y2>>1;
        int ch=o<<2;
        if(x<=m1&&y<=m2) update(ch+1,ch1,x,y,v);
        else if(x>m1&&y<=m2) update(ch+2,ch2,x,y,v);
        else if(x<=m1&&y>m2) update(ch+3,ch3,x,y,v);
        else update(ch+4,ch4,x,y,v);
        pu(o);
    }
    int query(int o,int x1,int x2,int y1,int y2,int xx1,int xx2,int yy1,int yy2,int flag){
        if(xx1<=x1&&x2<=xx2&&yy1<=y1&&y2<=yy2) return flag?mx[o]:mn[o];
        int m1=x1+x2>>1;
        int m2=y1+y2>>1;
        int ch=o<<2;
        int ans1,ans2,ans3,ans4=flag?-oo:+oo; ans1=ans2=ans3=ans4;
        if(xx1<=m1&&yy1<=m2) ans1=query(ch+1,ch1,xx1,xx2,yy1,yy2,flag);
        if(xx2>m1&&yy1<=m2) ans2=query(ch+2,ch2,xx1,xx2,yy1,yy2,flag);
        if(xx1<=m1&&yy2>m2) ans3=query(ch+3,ch3,xx1,xx2,yy1,yy2,flag);
        if(xx2>m1&&yy2>m2) ans4=query(ch+4,ch4,xx1,xx2,yy1,yy2,flag);
        return flag?max(ans1,ans2,ans3,ans4):min(ans1,ans2,ans3,ans4);
    }
}st;
int main(){
    for(int i = 0; i < 21; i++){
        for(int j = 0; j < 21; j++){
            a[i][j]=i*21+j;
            cout<<a[i][j]<<" ";
        }cout<<endl;
    }
    st.init();st.build(0,0,20,0,20);
    cout<<st.query(0,0,20,0,20,1,2,3,4,1)<<endl;
    cout<<st.query(0,0,20,0,20,1,2,3,4,0)<<endl;
    st.update(0,0,20,0,20,2,4,40);
    cout<<st.query(0,0,20,0,20,1,2,3,4,1)<<endl;
    cout<<st.query(0,0,20,0,20,1,2,3,4,0)<<endl;
    return 0;
}

HDU4819

//TLE
#include<bits/stdc++.h>
#define ch1 x1,m1,y1,m2
#define ch2 m1+1,x2,y1,m2
#define ch3 x1,m1,m2+1,y2
#define ch4 m1+1,x2,m2+1,y2
#define sz1 (m1-x1+1)*(m2-y1+1)
#define sz2 (x2-m1)*(m2-y1+1)
#define sz3 (m1-x1+1)*(y2-m2)
#define sz4 (x2-m1)*(y2-m2)
#define mmin(a,b,c,d) min(a,min(b,min(c,d)))
#define mmax(a,b,c,d) max(a,max(b,max(c,d)))
using namespace std;
const int maxn = 1e6+11;
const int oo = 0x3f3f3f3f;
const int xx = 0x80;
int a[100][100];
struct ST{
    int mn[maxn<<2],mx[maxn<<2];
    void init(){//NOTE
        memset(mn,oo,sizeof mn);
        memset(mx,xx,sizeof mx);
    }
    void pu(int o){
        int ch=o<<2;
        mn[o]=mmin(mn[ch+1],mn[ch+2],mn[ch+3],mn[ch+4]);
        mx[o]=mmax(mx[ch+1],mx[ch+2],mx[ch+3],mx[ch+4]);
    }
    void build(int o,int x1,int x2,int y1,int y2){
        if(x1==x2&&y1==y2){
            mn[o]=mx[o]=a[x1][y1];
            return;
        }
        int m1=x1+x2>>1;
        int m2=y1+y2>>1;
        int ch=o<<2;
        if(x1<=m1&&y1<=m2) build(ch+1,ch1);
        if(x2>m1&&y1<=m2) build(ch+2,ch2);
        if(x1<=m1&&y2>m2) build(ch+3,ch3);
        if(x2>m1&&y2>m2) build(ch+4,ch4);
        pu(o);
    }
    void update(int o,int x1,int x2,int y1,int y2,int x,int y,int v){
        if(x1==x2&&y1==y2){
            mn[o]=mx[o]=v;
            return;
        }
        int m1=x1+x2>>1;
        int m2=y1+y2>>1;
        int ch=o<<2;
        if(x<=m1&&y<=m2) update(ch+1,ch1,x,y,v);
        else if(x>m1&&y<=m2) update(ch+2,ch2,x,y,v);
        else if(x<=m1&&y>m2) update(ch+3,ch3,x,y,v);
        else update(ch+4,ch4,x,y,v);
        pu(o);
    }
    int query(int o,int x1,int x2,int y1,int y2,int xx1,int xx2,int yy1,int yy2,int flag){
        if(xx1<=x1&&x2<=xx2&&yy1<=y1&&y2<=yy2) return flag?mx[o]:mn[o];
        int m1=x1+x2>>1;
        int m2=y1+y2>>1;
        int ch=o<<2;
        int ans1,ans2,ans3,ans4=flag?-oo:+oo; ans1=ans2=ans3=ans4;
        if(xx1<=m1&&yy1<=m2) ans1=query(ch+1,ch1,xx1,xx2,yy1,yy2,flag);
        if(xx2>m1&&yy1<=m2) ans2=query(ch+2,ch2,xx1,xx2,yy1,yy2,flag);
        if(xx1<=m1&&yy2>m2) ans3=query(ch+3,ch3,xx1,xx2,yy1,yy2,flag);
        if(xx2>m1&&yy2>m2) ans4=query(ch+4,ch4,xx1,xx2,yy1,yy2,flag);
        return flag?mmax(ans1,ans2,ans3,ans4):mmin(ans1,ans2,ans3,ans4);
    }
}st;
int main(){
    int T,n,q,kase=0; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d",&a[i][j]);
            }
        }
        st.init();st.build(0,1,n,1,n);
        scanf("%d",&q);
        printf("Case #%d:\n",++kase);
        while(q--){
            int x,y,L;
            scanf("%d%d%d",&x,&y,&L);
            int x1=max(x-L/2,1);
            int x2=min(x+L/2,n);
            int y1=max(y-L/2,1);
            int y2=min(y+L/2,n);
            int mn=st.query(0,1,n,1,n,x1,x2,y1,y2,0);
            int mx=st.query(0,1,n,1,n,x1,x2,y1,y2,1);
            printf("%d\n",mn+mx>>1);
            st.update(0,1,n,1,n,x,y,mn+mx>>1);
        }
    }
    return 0;
}

树套树实现:http://blog.csdn.net/u012469987/article/details/47341457

#include<bits/stdc++.h>
using namespace std;
const int maxn = 803;
const int oo = 0x3f3f3f3f;
const int xx = 0x80;
#define lc(o) (o)<<1
#define rc(o) (o)<<1|1
int a[maxn][maxn],n;
struct ST{
    int mn[maxn<<2][maxn<<2],mx[maxn<<2][maxn<<2];

    int mmin,mmax;
    void init(){
        memset(mn,oo,sizeof mn);
        memset(mx,xx,sizeof mx);
        mmin=oo;mmax=-oo;
    }
    void pu(int ox,int oy){
        mn[ox][oy]=min(mn[ox<<1][oy],mn[ox<<1|1][oy]);
        mx[ox][oy]=max(mx[ox<<1][oy],mx[ox<<1|1][oy]);
    }
    void _pu(int ox,int oy){
        mn[ox][oy]=min(mn[ox][oy<<1],mn[ox][oy<<1|1]);
        mx[ox][oy]=max(mx[ox][oy<<1],mx[ox][oy<<1|1]);
    }
    void _build(int oy,int l,int r,int ox,int x,int flag){//x:id为ox的外层线段树管辖的行边界(lx==rx)
        if(l==r){
            if(flag) mn[ox][oy]=mx[ox][oy]=a[x][l];
            else pu(ox,oy);
            return;
        }
        int m=l+r>>1;
        _build(oy<<1,l,m,ox,x,flag);
        _build(oy<<1|1,m+1,r,ox,x,flag);
        _pu(ox,oy);
    }
    void build(int ox,int l,int r){
        if(l==r){
            _build(1,1,n,ox,l,1);//[oy yl yr] [ox lx] flag
            return;
        }
        int m=l+r>>1;
        build(ox<<1,l,m);
        build(ox<<1|1,m+1,r);
        // pu(ox,oy);
        _build(1,1,n,ox,0,0);//lx==0? pu
    }
    void _update(int oy,int l,int r,int y,int v,int ox,int flag){
        if(l==y&&r==y){
            if(flag) mx[ox][oy]=mn[ox][oy]=v;
            else pu(ox,oy);
            return;
        }
        int m=l+r>>1;
        if(y<=m) _update(oy<<1,l,m,y,v,ox,flag);
        else _update(oy<<1|1,m+1,r,y,v,ox,flag);
        _pu(ox,oy);
    }
    void update(int ox,int l,int r,int x,int y,int v){//[ox,l,r][x,y->v]
        if(l==x&&r==x){
            _update(1,1,n,y,v,ox,1);
            return;
        }
        int m=l+r>>1;
        if(x<=m) update(ox<<1,l,m,x,y,v);
        if(x>m) update(ox<<1|1,m+1,r,x,y,v);
        _update(1,1,n,y,0,ox,0);//v==0 //pushup
    }
    void _query(int oy,int l,int r,int y1,int y2,int ox){
        if(y1<=l&&r<=y2){
            mmax=max(mmax,mx[ox][oy]);
            mmin=min(mmin,mn[ox][oy]);
            return;
        }
        int m=l+r>>1;
        if(y1<=m) _query(oy<<1,l,m,y1,y2,ox);
        if(y2>m) _query(oy<<1|1,m+1,r,y1,y2,ox);
    }
    void query(int ox,int l,int r,int x1,int x2,int y1,int y2){
        if(x1<=l&&r<=x2){
            _query(1,1,n,y1,y2,ox);
            return;
        }
        int m=l+r>>1;
        if(x1<=m) query(ox<<1,l,m,x1,x2,y1,y2);
        if(x2>m) query(ox<<1|1,m+1,r,x1,x2,y1,y2);
    }
}st;
int main(){
    int T,q,kase=0; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d",&a[i][j]);
            }
        }
        st.init();st.build(1,1,n);
        scanf("%d",&q);
        printf("Case #%d:\n",++kase);
        while(q--){
            int x,y,L;
            scanf("%d%d%d",&x,&y,&L);
            int x1=max(x-L/2,1);
            int x2=min(x+L/2,n);
            int y1=max(y-L/2,1);
            int y2=min(y+L/2,n);
            st.query(1,1,n,x1,x2,y1,y2);
            printf("%d\n",st.mmax+st.mmin>>1);
            st.update(1,1,n,x,y,st.mmin+st.mmax>>1);
            st.mmin=oo;st.mmax=-oo;
        }
    }
    return 0;
}

又是一大波题集

10.pku3667 Hotel
成段更新,寻找空间(经典类型,求一块满足条件的最左边的空间)

.
11.hdu1540 Tunnel Warfare
更新节点,询问节点所在区间(同上一道Hotel一样类型的题目)
.
12.hdu2871 Memory Control
hotel变形题目,三个都函数一样(vector忘记清空检查了好久)
.
13.hdu3016 Man Down
成段更新,单点查询(简单线段树+简单DP)
.
14.hdu1542 Atlantis
矩形面积并,扫描线法(发现我们HDU的队员的矩形面积交模板基本都是在最坏情况下更新到底,宁波惨痛的教训啊..)
.
15.hdu1255 覆盖的面积
同上,扫描线法,我多加了一个系数csum,来统计覆盖两次的长度(156MS,第一次做线段树排到第一,纪念下)
.
16.hdu1828 Picture
扫描线,同面积统计,加了一个num_Seg统计一个扫描区域里的边
.
17.pku1436 Horizontally Visible Segments
成段更新,成段询问(染色问题,坐标*2后很简单,最后统计用暴力- -)
.
18.pku3225 Help with Intervals
成段更新,总询问区间(有个异或操作比较新颖)
.
19.pku2482 Stars in Your Window
成段更新,区间最值 + 扫描线(转化成区间最值有点巧妙,数据太TMD的恶心了,中间二分的地方会int溢出,检查了半个小时)
.
20.pku2828 Buy Tickets
思维很巧妙,倒过来做的话就能确定此人所在的位置
.
21.pku2464 Brownie Points II
更新节点,区间求和 + 扫描线(很好玩的一道题目,用两个线段树沿着扫描线更新,然后按”自己最多,对方最少”的方案一路统计)
(因为两棵树,我就直接写成类了)
.
22.pku3145 Harmony Forever
查找一个区间内最左边的数,询问的val大的话用线段树,小的话线性扫描,很囧的题目
.
23.pku2886 Who Gets the Most Candies?
寻找区间中的左数第N个数,约瑟夫环(学到了反素数表,可以不用把所有数字预处理出来了)
.
24.pku2991 Crane
记录了线段的两端点以及转过的角度,成段的转,超有意思的题目,做了之后会对线段树理解更深刻
(wy教主推荐的,不过我的代码写的太搓了..没啥学习的价值)
.
25.hdu1823 Luck and Love
二维线段树,没啥意思,代码量大了一倍而已,题目和运用范围都没一维的广,随便找了道题目练习下就好

线段树与其他结合练习(欢迎大家补充):

hdu3333 Turing Tree

hdu3874 Necklace

hdu3016 Man Down

hdu3340 Rain in ACStar

zju3511 Cake Robbery

UESTC1558 Charitable Exchange

CF85-D Sum of Medians

spojGSS2 Can you answer these queries II

POJ2750
环形区间合并
结论:不全覆盖1到n的最长连续和为sum-最小连续和

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int maxn = 1e5+11;
int a[maxn];
struct ST{
    int sum[maxn<<2],mx[maxn<<2],mn[maxn<<2];
    int maxl[maxn<<2],maxr[maxn<<2],minl[maxn<<2],minr[maxn<<2];
    void pu(int o){
        sum[o]=sum[lc]+sum[rc];

        maxl[o]=max(maxl[lc],sum[lc]+maxl[rc]);
        maxr[o]=max(maxr[rc],sum[rc]+maxr[lc]);
        mx[o]=max(mx[lc],mx[rc]);
        mx[o]=max(mx[o],maxr[lc]+maxl[rc]);

        minl[o]=min(minl[lc],sum[lc]+minl[rc]);
        minr[o]=min(minr[rc],sum[rc]+minr[lc]);
        mn[o]=min(mn[lc],mn[rc]);
        mn[o]=min(mn[o],minr[lc]+minl[rc]);

    }
    void build(int o,int l,int r){
        if(l==r){
            sum[o]=mx[o]=mn[o]=maxl[o]=maxr[o]=minl[o]=minr[o]=a[l];
            return;
        }
        int m = l+r>>1;
        build(lc,l,m);
        build(rc,m+1,r);
        pu(o);
    }
    void update(int o,int l,int r,int k,int v){
        if(l==r){
            sum[o]=mx[o]=mn[o]=maxl[o]=maxr[o]=minl[o]=minr[o]=v;
            return;
        }
        int m = l+r>>1;
        if(k<=m) update(lc,l,m,k,v);
        else update(rc,m+1,r,k,v);
        pu(o);
    }
}st; 
int n,m,k,v;
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 1; i <= n; i++)scanf("%d",&a[i]);
        st.build(1,1,n);
        scanf("%d",&m);
        for(int i = 1; i <= m; i++){
            scanf("%d%d",&k,&v);
            st.update(1,1,n,k,v);
            if(st.sum[1]==st.mx[1]){
                printf("%d\n",st.sum[1]-st.mn[1]);
            }
            else{
                printf("%d\n",max(st.sum[1]-st.mn[1],st.mx[1]));
            }
        }
    }
    return 0;
}

POJ3667

#include<bits/stdc++.h>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int maxn = 1e5+11;
struct ST{
    int ls[maxn<<2],rs[maxn<<2],ms[maxn<<2];//最长连续1-有位子 
    int lazy[maxn<<2];
    void init(){
        memset(lazy,-1,sizeof lazy);
    }
    void pu(int o,int l,int r){
        ls[o]=ls[lc];
        rs[o]=rs[rc];
        int m=l+r>>1;
        if(ls[o]==m-l+1) ls[o]+=ls[rc];
        if(rs[o]==r-m) rs[o]+=rs[lc];
        ms[o]=max(ms[lc],ms[rc]);
        ms[o]=max(ms[o],rs[lc]+ls[rc]);
    }
    void build(int o,int l,int r){
        if(l==r){
            ls[o]=rs[o]=ms[o]=1;
            return;
        }
        int m=l+r>>1;
        build(lc,l,m);
        build(rc,m+1,r);
        pu(o,l,r);
    }
    void pd(int o,int l,int r){
        if(lazy[o]==0){
            ls[lc]=rs[lc]=ms[lc]=0;
            ls[rc]=rs[rc]=ms[rc]=0;
            lazy[lc]=lazy[rc]=0;
            lazy[o]=-1;
        }
        else if(lazy[o]==1){
            int m=l+r>>1;
            ls[lc]=rs[lc]=ms[lc]=m-l+1;
            ls[rc]=rs[rc]=ms[rc]=r-m;
            lazy[lc]=lazy[rc]=1;
            lazy[o]=-1;
        }
    }
    void update(int o,int l,int r,int L,int R,int v){
        if(L<=l&&r<=R){
            ls[o]=rs[o]=ms[o]=v?(r-l+1):0;
            lazy[o]=v;
            return;
        }
        pd(o,l,r);
        int m=l+r>>1;
        if(L<=m)update(lc,l,m,L,R,v);
        if(R>m)update(rc,m+1,r,L,R,v);
        pu(o,l,r);
    }
    int query(int o,int l,int r,int len){//pos
        if(l==r) return l;//
        pd(o,l,r);
        int m=l+r>>1;
        if(ms[lc]>=len) return query(lc,l,m,len);//注意优先度 左-中间-右 
        else if(rs[lc]+ls[rc]>=len) return m-rs[lc]+1;
        else return query(rc,m+1,r,len);
    }
}st;
int n,m,pos,len,op;
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        st.init();st.build(1,1,n);
        for(int i = 0; i < m; i++){
            scanf("%d",&op);
            if(op==1){
                scanf("%d",&len);
                if(st.ms[1]<len) printf("0\n");
                else{
                    pos=st.query(1,1,n,len);
                    printf("%d\n",pos);
                    st.update(1,1,n,pos,pos+len-1,0);
                }
            }
            else{
                scanf("%d%d",&pos,&len);
                st.update(1,1,n,pos,pos+len-1,1);
            }
        }
    }
    return 0;
}

HDU1540

#include<bits/stdc++.h>
#define lc o<<1
#define rc o<<1|1
using namespace std;
const int maxn = 2e5+11;
struct ST{
    int ls[maxn<<2],rs[maxn<<2],ms[maxn<<2];
    void pu(int o,int l,int r){
        ls[o]=ls[lc];rs[o]=rs[rc];
        int m = l+r>>1;
        if(ls[o]==m-l+1) ls[o]+=ls[rc];
        if(rs[o]==r-m) rs[o]+=rs[lc];
        ms[o]=max(ms[lc],ms[rc]);
        ms[o]=max(ms[o],rs[lc]+ls[rc]);
    }
    void build(int o,int l,int r){
        ls[o]=rs[o]=ms[o]=r-l+1;
        if(l!=r){
            int m = l+r>>1;
            build(lc,l,m);
            build(rc,m+1,r);
        }
    }
    void update(int o,int l,int r,int k,int v){
        if(l==r){
            ls[o]=rs[o]=ms[o]=v;
            return;
        }
        int m = l+r>>1;
        if(k<=m) update(lc,l,m,k,v);
        else update(rc,m+1,r,k,v);
        pu(o,l,r);
    }
    int query(int o,int l,int r,int k){
        if(l==r||ms[o]==0||ms[o]==r-l+1){//满也不往下走 
            return ms[o];
        }
        int m = l+r>>1;
        if(k<=m){//NOTE
            if(k>=m-rs[lc]+1) return query(lc,l,m,k)+query(rc,m+1,r,m+1);
            else return query(lc,l,m,k);
        }
        else{
            if(k<=m+1+ls[rc]-1) return query(rc,m+1,r,k)+query(lc,l,m,m);
            else return query(rc,m+1,r,k);
        }
    }
}st; 
int n,m,k;
char str[100];
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        st.build(1,1,n);
        stack<int> stk; while(!stk.empty())stk.pop();
        for(int i = 0; i < m; i++){
            scanf("%s",str);
            if(str[0]=='D'){
                scanf("%d",&k);
                st.update(1,1,n,k,0);
                stk.push(k);
            }
            else if(str[0]=='R'){
                if(stk.empty())continue;
                k=stk.top();stk.pop();
                st.update(1,1,n,k,1);
            }
            else{
                scanf("%d",&k);
                if(k>n||k<0)continue;
                printf("%d\n",st.query(1,1,n,k));
            }
        }
    }
    return 0;
}

矩阵切割
参考:剖析线段树与矩形切割
当我们每次插入一条线段,就跟线段集合中的每一条线段[a,b]都判断
一下是否出现重叠,若出现重叠则对[a,b]进行切割。判断重叠的方法为:若 a≥d
或者 c≥b,就不出现重叠,否则重叠。切割的方法就是:取线段[a,b],[c,d]的交
集[k1,k2]。若 a<k1,则加入线段[a,k1];若 k2<b,则加入线段[k2,b]。删除线段[a,b]。

struct Line{
    int l,r;
}line[maxn]; 
void add(int l,int r){
    line[tot].l=l;
    line[tot++].r=r;
}
void dele(int now){
    line[now]=line[--tot];//swap
}
void cut(int now,int l,int r){
    if(line[now].l<l)add(line[now].l,l);
    if(r<line[now].r)add(r,line[now].r);
    dele(now);
}

CodeForces - 240F
26棵线段树维护回文串,用于加速查询、覆盖字符
题目超出要求这是A不了的,仅当思路提供//A了啊~
注意奇数情况0也得清空,因为之前减一了
multi-lazy不熟练只能强行打单一的绝对标记,幸好题目不为难

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+11;
typedef long long ll;
char str[maxn];
int a[26][maxn];
struct ST{
    #define lc o<<1
    #define rc o<<1|1
    int num[maxn<<2],lazy[maxn<<2],lazy2[maxn<<2];
    void pu(int o){
        num[o]=num[lc]+num[rc];
    }
    void pd(int o,int l,int r){
        if(~lazy[o]){
            int m = l+r>>1;
            lazy[lc]=lazy[rc]=lazy[o];
            num[lc]=lazy[o]*(m-l+1);
            num[rc]=lazy[o]*(r-m);
            lazy[o]=-1;
        }
    }
    void build(int o,int l,int r,int i){
        lazy[o]=-1;
        if(l==r){
            num[o]=a[i][l];
            return;
        }
        int m = l+r>>1;
        build(lc,l,m,i);
        build(rc,m+1,r,i);
        pu(o);
    }
    void update(int o,int l,int r,int L,int R,int v){
        if(L<=l&&r<=R){
            lazy[o]=v;
            num[o]=lazy[o]*(r-l+1);
            return;
        }
        pd(o,l,r);
        int m=l+r>>1;
        if(L<=m) update(lc,l,m,L,R,v);
        if(R>m) update(rc,m+1,r,L,R,v);
        pu(o);
    }
    void pd2(int o,int l,int r,int L,int R){
        lazy[o]=num[lc]=num[rc]=lazy[lc]=lazy[rc]=0;
    }
    inline void clean(int o,int l,int r,int L,int R){
        update(o,l,r,L,R,0);
    }
    ll query(int o,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            return num[o];
        }
        pd(o,l,r);
        int m = l+r>>1;
        ll ans = 0;
        if(L<=m) ans+=query(lc,l,m,L,R);
        if(R>m) ans+=query(rc,m+1,r,L,R);
        return ans;
    }
}st[26]; 
int n,m,li,ri,pos;
int t[26],odd,even;
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(a,0,sizeof a);
        scanf("%s",str+1);
        for(int i = 1; i <= n; i++){
            a[str[i]-'a'][i]++;
        }
        for(int i = 0; i < 26; i++){
            st[i].build(1,1,n,i);
        } 
        for(int i = 1; i <= m; i++){
            scanf("%d%d",&li,&ri);
            int shift=0;
            odd=even=pos=0;pos--;
            for(int j = 0; j < 26; j++){
                t[j]=st[j].query(1,1,n,li,ri);
                if(t[j]&1){odd++;pos=j;}
                else even++;
            }
//            
            if(odd>1)continue;
            else{
                int lii=li,rii=ri;
                if(~pos)t[pos]--; 
                for(int j = 0; j < 26; j++){
                    if(pos==j)st[j].clean(1,1,n,lii,rii);
                    if(0==t[j])continue;
                    st[j].clean(1,1,n,lii,rii);
                    st[j].update(1,1,n,li,li+(t[j]/2)-1,1);
                    li+=(t[j]/2);
                }
                for(int j = 0; j < 26; j++){
                    if(t[j]==0)continue;
                    st[j].update(1,1,n,ri-(t[j]/2)+1,ri,1);
                    ri-=(t[j]/2);
                }
                if(~pos){
                    if(t[pos]!=-1){
                        st[pos].update(1,1,n,li,ri,1);
                    }
                }
            }
        }
//        
        for(int i = 1; i <= n; i++){ 
            int tmp=-1;
            for(int j = 0; j < 26; j++){
                if(st[j].query(1,1,n,i,i)){tmp=j;break;}
            }
            char opt=tmp+'a';
            if(i==n) printf("%c\n",opt);
            else printf("%c",opt);
        }
    }
    return 0;
}

标签: 算法, 学习

添加新评论