kuangbin线段树专题（已更一半

啊。。这个专题才开的时候，学校就恢复了vj挂题的制度，加上各种比赛，以及文化课之类的，导致这个专题写的好慢。。。写完后也一直没时间总结博客。。就是懒…
-------------------------------------------------------------------------
感觉…自己越来越没有斗志了…天天像个废物一样，就只会写几个傻瓜题，比赛也是签个到就开始罚坐。。学个新的图论算法几乎要自闭，，
图论也太难了吧！！！
图论也太难了吧！！！
图论也太难了吧！！！
二分图写着写着就遇到了HK算法，然后看不懂，，只会套板子，写着写着觉得放到暑假集训再处理这个二分图吧，不如先去把次小生成树完善一下，，然后写了四个题就遇到了最小树形图。。。再次自闭。。。。
还是先把这个线段树专题总结一下吧
-------------------------------------------------------------------------
就三个题没补
一个是多重lazy标记。。写吐了。真不想写这个（不会。。
还有一个是扫描线处理周长问题（只学了处理面积，周长一时半会没看会。
最后一个就是很玄学的看都看不懂的题目。。说是三维线段树？？？？
我太菜了…
-------------------------------------------------------------
开始正文
专题链接
A - 敌兵布阵 HDU - 1166

单点修改 区间查询
最简单的线段树操作了，不如放个树状数组上来吧

int lowbit(int x){return x&(-x);}
int arr[maxn];
void updata(int pos,int val,int n){
    while(pos<=n){
        arr[pos]+=val;
        pos+=lowbit(pos);
    }
}
int query(int pos){
    int ans=0;
    while(pos>0){
        ans+=arr[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
int cas=0;
void solve(){
    ms(arr,0);
    int n;cin>>n;
    rep(i,1,n){
        int tmp;cin>>tmp;
        updata(i,tmp,n);
    }
    string ope;
    int a,b;
    cout<<"Case "<<++cas<<":"<<endl;
    while(cin>>ope&&ope[0]!='E'){
        cin>>a>>b;
        if(ope[0]=='A'){
            updata(a,b,n);
        }else if(ope[0]=='S'){
            updata(a,-b,n);
        }else{
            cout<<query(b)-query(a-1)<<endl;
        }
    }
}

B - I Hate It HDU - 1754

区间查询，单点更新
还是基本操作。。上题放树状数组，那这个就放线段树把

struct node{
    int l,r;
    int val;
}tree[maxn<<2];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        scanf("%d",&tree[rt].val);
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].val=max(tree[ls].val,tree[rs].val);
}
void updata(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==r&&r==a){
        tree[rt].val=b;
    }else{
        if(a<=md){
            updata(ls,a,b);
        }else{
            updata(rs,a,b);
        }
        tree[rt].val=max(tree[ls].val,tree[rs].val);
    }
}
int query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    }else{
        if(b<=md){
            return query(ls,a,b);
        }else if(a>=md+1){
            return query(rs,a,b);
        }else{
            return max(query(ls,a,md),query(rs,md+1,b));
        }
    }
}
void solve(){
    int n,m;while(~scanf("%d %d",&n,&m)){
        build(1,1,n);
        while(m--){
            char str[30];int a,b;
            scanf("%s %d %d",str,&a,&b);
            if(str[0]=='Q'){
                cout<<query(1,a,b)<<endl;
            }else{
                updata(1,a,b);
            }
        }
    }
}

C - A Simple Problem with Integers POJ - 3468

嗯。。区间更新，区间查询
考察的是lazy标记的思想，单点修改必定会超时的
算是lazy标记入门题
我想不明白的是。。用scanf就一直wa…改成cin…就过了
迷惑。。。

struct node{
    ll l,r;
    ll val,tag;
}tree[maxn<<2];
void build(ll rt,ll l,ll r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].tag=0;
    if(l==r){
        cin>>tree[rt].val;
    }else{
        build(lson);
        build(rson);
        tree[rt].val=tree[ls].val+tree[rs].val;
    }
}
inline void push_down(ll rt){
    if(!tree[rt].tag){
        return ;
    }
    ll l=tree[rt].l,r=tree[rt].r;
    tree[ls].tag+=tree[rt].tag;
    tree[rs].tag+=tree[rt].tag;
    tree[ls].val+=(md-l+1)*tree[rt].tag;
    tree[rs].val+=(r-md)*tree[rt].tag;
    tree[rt].tag=0;
}
void updata(ll rt,ll a,ll b,ll c){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        tree[rt].tag+=c;
        tree[rt].val+=(r-l+1)*c;
        return ;
    }else{
        push_down(rt);
        if(b<=md){
            updata(ls,a,b,c);
        }else if(a>=md+1){
            updata(rs,a,b,c);
        }else{
            updata(ls,a,md,c);
            updata(rs,md+1,b,c);
        }
        tree[rt].val=tree[ls].val+tree[rs].val;
    }
}
ll query(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    }else{
        push_down(rt);
        if(b<=md){
            return query(ls,a,b);
        }else if(a>=md+1){
            return query(rs,a,b);
        }else{
            return query(ls,a,md)+query(rs,md+1,b);
        }
    }
}
void solve(){
    ll n,q;
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        char ope[10];
        ll a,b,c;
        cin>>ope>>a>>b;
        if(ope[0]=='Q'){
            cout<<query(1,a,b)<<endl;
        }else{
            cin>>c;
            updata(1,a,b,c);
        }
    }
    
}

D - Mayor’s posters POJ - 2528


呃。线段树染色+离散化处理
数据太大了，需要离散化一下，不然无法建树
注意这里每一个点代表的是片段的颜色，比如3，4，5，6，7
4，6之间，3，4之间，6，7之间依次染了色，然后你离散化就成了，3，4，6，7，对应1，2，3，4，然后你记录出来的就是1，2有颜色，3，4有颜色，这就忽略了一种颜色！！，原本的应该是，3，4 ，，，5，，6，7
所以离散化的时候，对于每一个长度大于1的区间，就需要额外添加一个数进去来确保正确度！即

for(ll i=1;i<=sz-1;i++){
        if(v[i]-v[i-1]>1){
            v.pb(v[i-1]+1);
        }
    }

注意这个题染的是点，和下面那个题不同，这点要区分开
然后就没啥好说的了，上代码吧，注意线段树离散化的操作

struct node{
    ll l,r;
    ll val;
}tree[maxn<<4];
struct IUPUT{
    ll l,r;
}input[maxn];
ll vis[maxn<<4];
vector<ll>v;
ll ans=0;
void build(ll rt,ll l,ll r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].val=-1;
    if(l==r){
        return ;
    }
    build(lson);
    build(rson);
}
inline void push_down(ll rt){
    ll l=tree[rt].l,r=tree[rt].r;
    if(tree[rt].val!=-1&&l!=r){
        tree[ls].val=tree[rt].val;
        tree[rs].val=tree[rt].val;
        tree[rt].val=-1;
    }
}
void updata(ll rt,ll a,ll b,ll c){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        tree[rt].val=c;
        return ;
    }
    push_down(rt);
    if(b<=md){
        updata(ls,a,b,c);
    }else if(a>=md+1){
        updata(rs,a,b,c);
    }else{
        updata(ls,a,md,c);
        updata(rs,md+1,b,c);
    }
}
void query(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    //de(tree[rt].val),de(l),de(r),de(a),de(b);
    if(l==a&&r==b&&tree[rt].val!=-1){
        ll tmp=tree[rt].val;
        if(!vis[tmp]){
            vis[tmp]=1;
            ans++;
        }
        return ;
    }
    if(tree[rt].val==-1&&l==r){
        return ;
    }
    push_down(rt);
    if(b<=md){
        query(ls,a,b);
    }else if(a>=md+1){
        query(rs,a,b);
    }else{
        query(ls,a,md);
        query(rs,md+1,b);
    }
}
void solve(){
    v.clear();
    ans=0;
    ll n=read();
    rep(i,1,n){
        input[i].l=read();
        input[i].r=read();
        v.pb(input[i].l);
        v.pb(input[i].r);
    }
    ll sz=v.size();
    sort(v.begin(),v.end());
    for(ll i=1;i<=sz-1;i++){
        if(v[i]-v[i-1]>1){
            v.pb(v[i-1]+1);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    sz=v.size();
    build(1,1,sz);
    rep(i,1,n){
        ll a=lower_bound(v.begin(),v.end(),input[i].l)-v.begin()+1;
        ll b=lower_bound(v.begin(),v.end(),input[i].r)-v.begin()+1;
        updata(1,a,b,i);
    }
    ms(vis,0);
    query(1,1,sz);
    cout<<ans<<endl;
}

E - Just a Hook HDU - 1698


就是个区间更新，区间查询的题目
题意：一个拐杖原本单位长度价值为1，然后每次选定一个$L$L,$R$R区间，把这个区间单位价值修改为$val$val 最后求区间之和。。
就是lazy的应用吧

struct node{
    int l,r;
    int val,tag;
}tree[maxn<<2];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].tag=0;
    if(l==r){
        tree[rt].val=1;
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].val=tree[ls].val+tree[rs].val;
}
inline void push_down(int rt){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==r||tree[rt].tag==0){
        tree[rt].tag=0;
        return ;
    }
    tree[ls].tag=tree[rs].tag=tree[rt].tag;
    tree[ls].val=(md-l+1)*tree[ls].tag;
    tree[rs].val=(r-md)*tree[rs].tag;
    tree[rt].tag=0;
}
void updata(int rt,int a,int b,int c){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        tree[rt].tag=c;
        tree[rt].val=(r-l+1)*c;
        return ;
    }
    push_down(rt);
    if(b<=md){
        updata(ls,a,b,c);
    }else if(a>=md+1){
        updata(rs,a,b,c);
    }else{
        updata(ls,a,md,c);
        updata(rs,md+1,b,c);
    }
    tree[rt].val=tree[ls].val+tree[rs].val;
}
int query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    }
    push_down(rt);
    if(b<=md){
        return query(ls,a,b);
    }else if(a>=md+1){
        return query(rs,a,b);
    }else{
        return query(ls,a,md)+query(rs,md+1,b);
    }
}
int cas=0;
void solve(){
    int n=read();build(1,1,n);
    int q=read();while(q--){
        int a=read(),b=read(),c=read();
        updata(1,a,b,c);
    }
    printf("Case %d: The total value of the hook is %d.\n",++cas,query(1,1,n));
}

F - Count the Colors ZOJ - 1610


也是线段树染色问题，每次把一个区域染成颜色$i$i，最后求出每种颜色有多少段，输出段数，为0（或者被覆盖完）则不用输出
因为这个染色的是线段，不是点，也即是说【1，2】 和【3，4】是不相邻的
这时候我们可以用$L$L来代替$L$L到$L+1$L+1这个区间，更新数值的时候更新
L+1，R的点就可以了，最后暴力找出每个颜色的段数

struct segtree{
    int l,r;
    int val;
}tree[maxn<<2];
int vis[maxn],ans,cup[maxn];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].val=-1;
    if(l==r){
        return ;
    }
    build(lson);
    build(rson);
}
inline void push_down(int rt){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==r||tree[rt].val==-1){
        return ;
    }
    tree[ls].val=tree[rs].val=tree[rt].val;
    tree[rt].val=-1;
}
void updata(int rt,int a,int b,int c){
    //de(l),de(r);
    //de(rt);
    int l=tree[rt].l,r=tree[rt].r;
    //de(a),de(b),de(l),de(r);
    if(l==a&&r==b){
        tree[rt].val=c;
        return ;
    }
    push_down(rt);
    if(b<=md){
        updata(ls,a,b,c);
    }else if(a>=md+1){
        updata(rs,a,b,c);
    }else{
        updata(ls,a,md,c);
        updata(rs,md+1,b,c);
    }
    
}
void query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b&&tree[rt].val!=-1){
        for(int i=l;i<=r;i++){
            cup[i]=tree[rt].val;
        }
        return ;
    }
    if(l==r&&tree[rt].val!=-1){
        return ;
    }
    push_down(rt);
    if(b<=md){
        query(ls,a,b);
    }else if(a>=md+1){
        query(rs,a,b);
    }else{
        query(ls,a,md);
        query(rs,md+1,b);
    }
    
}
void solve(){
    int n;while(~scanf("%d",&n)){
        int N=8001;
        build(1,1,N-1);
        ms(vis,0),ms(cup,-1);
        rep(i,1,n){
            int x1,x2,c;
            scanf("%d %d %d",&x1,&x2,&c);
            x1++;
            updata(1,x1,x2,c);
        }
        query(1,1,N-1);
        for(int i=1;i<=N;i++){
            if(cup[i-1]!=-1&&(i==1||cup[i-1]!=cup[i-2])){
                vis[cup[i-1]]++;
            }
        }
        for(int i=0;i<=N;i++){
            if(vis[i]){
                printf("%d %d\n",i,vis[i]);
            }
        }
        printf("\n");
    }
}

G - Balanced Lineup POJ - 3264

呃，区间最值查询，每次输出一个区间最大值与最小值的差值
简单题》。

struct segtree{
    int l,r;
    int mx,mn;
}tree[maxn<<2];
int ans1,ans2;
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        int tmp=read();
        tree[rt].mx=tree[rt].mn=tmp;
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].mx=max(tree[ls].mx,tree[rs].mx);
    tree[rt].mn=min(tree[ls].mn,tree[rs].mn);
}
void query(int rt,int a,int b){
    int l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        ans1=max(ans1,tree[rt].mx);
        ans2=min(ans2,tree[rt].mn);
        return ;
    }
    if(b<=md){
        query(ls,a,b);
    }else if(a>=md+1){
        query(rs,a,b);
    }else{
        query(ls,a,md);
        query(rs,md+1,b);
    }
}
void solve(){
    int n=read(),q=read();
    build(1,1,n);
    while(q--){
        int a=read(),b=read();
        ans1=-1*INF;
        ans2=INF;
        query(1,a,b);
        printf("%d\n",ans1-ans2);
    }
}

H - Can you answer these queries? HDU - 4027

区间更新，区间求和
由于这个区间更新是开方操作。。。所以必然不能用lazy标记了。。
但是暴力会超时？那怎么办
仔细想想，开方操作对于一个整数来说，最多操作6，7次就变成1了，变成1之后的开方就不会再变化了，所以我们还是暴力更新。只不过需要维护一下每个区间是否全为1了，是的话就不需要更新了，区间求和就是常规套路了

struct segtree{
    ll l,r;
    ll val,be;
}tree[maxn<<2];
void build(int rt,int l,int r){
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].be=0;
    if(l==r){
        scanf("%lld",&tree[rt].val);
        if(tree[rt].val==1){
            tree[rt].be=1;
        }
        return ;
    }
    build(lson);
    build(rson);
    tree[rt].val=tree[ls].val+tree[rs].val;
    tree[rt].be= tree[rt].val==(r-l+1);
}
void updata(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b&&tree[rt].be==1){
        return ;
    }
    if(l==a&&l==r){
        tree[rt].val=sqrt(tree[rt].val);
    }else if(b<=md){
        updata(ls,a,b);
    }else if(a>=md+1){
        updata(rs,a,b);
    }else{
        updata(ls,a,md);
        updata(rs,md+1,b);
    }
    if(l != r){
        tree[rt].val=tree[ls].val+tree[rs].val;
    }
    tree[rt].be = tree[rt].val==(r-l+1);
}
ll query(ll rt,ll a,ll b){
    ll l=tree[rt].l,r=tree[rt].r;
    if(l==a&&r==b){
        return tree[rt].val;
    } else {
        if (b <= md) {
            return query(ls,a,b);
        } else if (a >= md+1){
            return query(rs,a,b);
        } else {
            return query(ls,a,md) + query(rs,md+1,b);
        }
    }
}
void solve(){
    ll cas=0;
    ll n;while(~scanf("%lld",&n)){
        build(1,1,n);
        ll m;scanf("%lld",&m);
        printf("Case #%lld:\n",++cas);
        while(m--){
            ll a,b,c;scanf("%lld %lld %lld",&a,&b,&c);
            if(b>c){
                swap(b,c);
            }
            if (a==0) {
                updata(1,b,c);
            } else {
                printf("%lld\n",query(1,b,c));
            }
        }
        puts("");
    }
}

先鸽了…明后天再继续补