寒假专题训练--线段树

线段树

地址

A - 敌兵布阵

[HDU - 1166]

• 题意
  多个营地，实时地有人员进入和离开。要求实时求出第i到第j个营地总共有多少人。
• 思路
  O(n^2)肯定会超时。考虑构建线段树，对点更新，区间查询即可。
  注意数组开四倍。我之前数组开小了，结果运行时把原代码的空间覆盖了，得的超时的反馈（死循环）。
• 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;
int test;
int n,kase;
char order[10];
struct tr{
    int l,r,v;
}t[200005];
void build(int k,int l,int r){
    t[k].l=l;
    t[k].r=r;
    t[k].v=0;
    if (l==r)
    {
        return;
    }
    int mid=l+(r-l)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
}
void add(int k,int now,int num){
    if (t[k].l==t[k].r)
    {
        t[k].v+=num;
        return;
    }
    int mid=t[k].l+(t[k].r-t[k].l)/2;
    if (now<=mid)
    {
        add(2*k,now,num);
    }else{
        add(2*k+1,now,num);
    }
    t[k].v=t[k*2].v+t[k*2+1].v;
}
int query(int k,int a,int b){
    if (t[k].l>=a&&t[k].r<=b)
    {
        return t[k].v;
    }
    if (a>t[k].r||b<t[k].l)
    {
        return 0;
    }
    int mid=t[k].l+(t[k].r-t[k].l)/2;
    if (a>mid)
    {
        return query(2*k+1,a,b);
    }else if(b<=mid){
        return query(2*k,a,b);
    }else{
        return query(2*k,a,mid)+query(2*k+1,mid+1,b);
    }
}
int main(){
    kase=0;
    scanf("%d",&test);
    while(test--){
        scanf("%d",&n);
        build(1,1,n);
        printf("Case %d:\n",++kase );
        for(int i=1;i<=n;i++){
            int num;
            scanf("%d",&num);
            add(1,i,num);
        }
        while(scanf("%s",order),order[0]!='E'){
            int a,b;
            scanf("%d%d",&a,&b);
            if(order[0]=='A'){
                add(1,a,b);
            }else if(order[0]=='S'){
                add(1,a,-b);
            }else{
                printf("%d\n",query(1,a,b));
            }
        }
    }
}

B - Color the ball

[HDU - 1556]

• 题意
  有一排气球，每次对一个区间内的所有气球刷一次漆。最后，求出每个气球刷过几次漆。
• 思路
  建立线段树，进行区间更新，注意lazy思想节约时间。
• 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;
int n;
struct tr{
    int l,r,v,lazy;
}t[400005];
void build(int k,int l,int r){
    t[k].l=l;
    t[k].r=r;
    t[k].v=0;
    t[k].lazy=0;
    if (l==r)
    {
        return;
    }
    int mid=l+(r-l)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
}
void add(int k,int now,int num){
    if (t[k].l==t[k].r)
    {
        t[k].v+=num;
        return;
    }
    int mid=t[k].l+(t[k].r-t[k].l)/2;
    if (now<=mid)
    {
        add(2*k,now,num);
    }else{
        add(2*k+1,now,num);
    }
    //t[k].v=t[k*2].v+t[k*2+1].v;
}
void pushdown(int k){
    if(t[k].lazy>0){
        t[2*k].v+=t[k].lazy;
        t[2*k+1].v+=t[k].lazy;
        t[2*k].lazy+=t[k].lazy;
        t[2*k+1].lazy+=t[k].lazy;
        t[k].lazy=0;
    }
}
void update(int k,int l,int r){
    if(l<=t[k].l&&r>=t[k].r){
        t[k].v++;
        t[k].lazy++;
        return;
    }
    pushdown(k);
    int mid=t[k].l+(t[k].r-t[k].l)/2;
    if (l>mid)
    {
        update(2*k+1,l,r);
    }else if(r<=mid){
        update(2*k,l,r);
    }else{
        update(2*k,l,mid);
        update(2*k+1,mid+1,r);
    }
}
int query(int k,int l,int r){
    if (t[k].l==t[k].r)
    {
        return t[k].v;
    }
    pushdown(k);
    int mid=t[k].l+(t[k].r-t[k].l)/2;
    if (l>mid)//thisproblem,l==r
    {
        return query(2*k+1,l,r);
    }else{
        return query(2*k,l,r);
    }
    /*
    else{
        return query(2*k,l,mid)+query(2*k+1,mid+1,r);
    }
    */
}
int main(){
    while(scanf("%d",&n),n!=0){
        build(1,1,n);
        for(int i=1;i<=n;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            update(1,l,r);
        }
        for(int i=1;i<=n;i++){
            if (i>1)
            {
                printf(" ");
            }
            printf("%d",query(1,i,i));
        }
        printf("\n");
    }
}