线段树 二分

线段树 二分 - HDU - 4614 - Vases and Flowers

二分查找求解区间左右端点的解法相对较简单.

我的代码里的注释应该写的比较清楚了.

刚刚提交过发现998ms,一个人提交只用了200ms.震惊(以后可能会回头做做这题)

#include <cstdio>
#include <cstdlib>
using namespace std;
#define N 50000+5
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
struct status{
    int begin;
    int end;
};
int T,n,m,k,a,b;
int tree[N<<2]; // 记录区间[l,r]已经占用的花瓶的数量.最大值为r-l+1
int lazy[N<<2]; // lazy[rt] = 1,则会使得结点tree[rt] = r-l+1; lazy[rt] = -1,则会使结点tree[rt] = 0; 它分别表示全部占用和全部清空.
void push_up(int rt){
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
};
void push_down(int rt,int left,int right){
    if(lazy[rt] == 0){
        return;
    }
    int mid = left+right>>1;
    int ls = rt<<1,rs = rt<<1|1;
    if(lazy[rt] == 1){
        lazy[ls] = lazy[rs] = 1;
        tree[ls] = mid-left+1;
        tree[rs] = right-mid;
    }else{
        lazy[ls] = lazy[rs] = -1;
        tree[ls] = tree[rs] = 0;
    }
    lazy[rt] = 0;
};
int query(int l,int r,int rt,int ql,int qr){ // 查询[ql,qr]区间的已经占用的花瓶数量
    if(ql <= l && qr >= r){
        return tree[rt];
    }else{
        int mid = l+r>>1;
        int ls = rt<<1;
        int rs = rt<<1|1;
        int ans = 0;
        push_down(rt,l,r);
        if(ql <= mid){
            ans += query(l,mid,ls,ql,qr);
        }
        if(qr > mid){
            ans += query(mid+1,r,rs,ql,qr);
        }
        return ans;
    }
}

int binSearch(int begin,int num){
    int l = begin,r = n;
    while(l < r){
        int mid = l+r>>1;
        if(mid-begin+1-query(1,n,1,begin,mid) < num){
            l = mid+1;
        }else{
            if(r == mid){
                break;
            }
            r = mid;
        }
    }

    if(l!=r && l-begin+1-query(1,n,1,begin,l) == num){
        return l;
    }else return r;
}
status tryAdd(int begin,int flowers){ // 找到从begin开始加flowers朵花,返回开始点,结束点
    int emptyVase = n-begin+1 - query(1,n,1,begin,n);
    if(emptyVase == 0){
        status error;
        error.begin = error.end = -1;
        return error;
    }

    int addnum = MIN(flowers,emptyVase);

    status correct;
    correct.begin = binSearch(begin,1);
    correct.end = binSearch(begin,addnum);
    return correct;
}

void set(int l,int r,int rt,int sl,int sr){
    if(sl <= l && sr >= r){
        tree[rt] = r-l+1;
        lazy[rt] = 1;
    }else{
        int mid = l+r>>1;
        int ls = rt<<1,rs = rt<<1|1;
        push_down(rt,l,r);
        if(sl <= mid){
            set(l,mid,ls,sl,sr);
        }   
        if(sr > mid){
            set(mid+1,r,rs,sl,sr);
        } 
        push_up(rt);
    }
}

void reset(int l,int r,int rt,int rsl,int rsr){
    if(rsl <= l && rsr >= r){
        tree[rt] = 0;
        lazy[rt] = -1;
    }else{
        int mid = l+r>>1;
        int ls = rt<<1,rs = rt<<1|1;
        push_down(rt,l,r);
        if(rsl <= mid){
            reset(l,mid,ls,rsl,rsr);
        }
        if(rsr > mid){
            reset(mid+1,r,rs,rsl,rsr);
        }
        push_up(rt);
    }
}

int main(){
    scanf("%d",&T);
    for(int i = 1; i <= T; i++){
        scanf("%d%d",&n,&m);
        reset(1,n,1,1,n); // 全部重置为0
        while(m--){
            scanf("%d%d%d",&k,&a,&b);
            if(k == 1){
                status x = tryAdd(a+1,b);
                if(x.begin == -1 && x.end == -1 || b == 0){
                    puts("Can not put any one.");
                }else{
                    set(1,n,1,x.begin,x.end);
                    printf("%d %d
",x.begin-1,x.end-1);
                }
            }else{
                int x = query(1,n,1,a+1,b+1);
                reset(1,n,1,a+1,b+1);
                printf("%d
",x);
            }
        }
        putchar('
');
    }
    return 0;
}