HDU 4614 Vases and Flowers (2013多校第二场线段树) (一)

题意：给你N个花瓶，编号是0 到 N - 1 ，初始状态花瓶是空的，每个花瓶最多插一朵花。

然后有2个操作。
操作1，a b c ，往在a位置后面(包括a)插b朵花，输出插入的首位置和末位置。
操作2,a b ,输出区间[a , b ]范围内的花的数量，然后全部清空。

很显然这是一道线段树。区间更新，区间求和，这些基本的操作线段树都可以logN的时间范围内完成。
操作2，很显然就是线段树的区间求和，求出[a , b]范围内的花朵的数量，区间更新，将整个区间全部变成0。
操作1，这里我们首先需要找出他的首位置和末位置，所以需要二分他的位置。
首先我们二分他的首位置, l = a , r = n ，在这个区间内二分，找出第一个0的位置，那就是该操作的首位置pos1。

然后再二分他的末位置，l = pos1 , r = n ，找到第c个0，就是该操作的末位置pos2，然后区间更新[pos1 ,pos2]全部置为1。

tmp = n - minn + 1 - query(minn,n,1) ; 表示【minn,n】区间内空花瓶的个数，如果需要插的花束多余tmp，则只能插tmp束花。

这题重点在于二分找位置，找了半天终于在别人的帮助下调试出来了............

#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#include //形如INT_MAX一类的   
#define MAX 100050   
#define INF 0x7FFFFFFF   
#define REP(i,s,t) for(int i=(s);i<=(t);++i)   
#define ll long long   
#define mem(a,b) memset(a,b,sizeof(a))   
#define mp(a,b) make_pair(a,b)   
#define L(x) x<<1   
#define R(x) x<<1|1   
# define eps 1e-5   
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂   
using namespace std;  
  
struct node {  
    int r,l,mid;  
    int lazy,sum;  
} edge[4*MAX];  
  
void up(int num) {  
    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;  
}  
  
void build(int l,int r,int num) {  
    edge[num].l = l;  
    edge[num].r = r;  
    edge[num].mid = (l+r) >> 1;  
    edge[num].lazy = -1;  
    if(l == r) {  
        edge[num].sum = 0;  
        return ;  
    }  
    build(l,edge[num].mid,L(num));  
    build(edge[num].mid+1,r,R(num));  
    //   
    up(num);  
}  
  
void down(int num) {  
    //if(edge[num].l == edge[num].r) return ;   
    if(edge[num].lazy != -1) {  
        edge[L(num)].lazy = edge[num].lazy;  
        edge[R(num)].lazy = edge[num].lazy;  
        edge[L(num)].sum = (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;  
        edge[R(num)].sum = (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;  
        edge[num].lazy = -1;  
    }  
  
}  
  
void update(int l,int r,int num,int k) {  
    if(l == edge[num].l && r == edge[num].r) {  
        edge[num].lazy = k;  
        edge[num].sum = (edge[num].r - edge[num].l + 1) * k;  
        return ;  
    }  
    down(num);  
    if(r <= edge[num].mid) {  
        update(l,r,L(num),k);  
    } else if(l > edge[num].mid) {  
        update(l,r,R(num),k);  
    } else {  
        update(l,edge[num].mid,L(num),k);  
        update(edge[num].mid + 1,r,R(num),k);  
    }  
    up(num);  
}  
  
int query(int l,int r,int num) {  
    if(l == edge[num].l && r == edge[num].r) {  
        return edge[num].sum;  
    }  
    down(num);  
    if(r <= edge[num].mid) {  
        return query(l,r,L(num));  
    } else if(l > edge[num].mid) {  
        return query(l,r,R(num));  
    } else {  
        return query(l,edge[num].mid,L(num)) + query(edge[num].mid + 1,r,R(num));  
    }  
}  
  
void test(int n) {  
    for(int i=1; i<=3*n; i++) {  
        printf("l:%d r:%d sum:%d lazy:%d\n",edge[i].l,edge[i].r,edge[i].sum,edge[i].lazy);  
    }  
}  
int main() {  
  
    int n,m,i,t;  
    cin >> t;  
    while(t --) {  
        scanf("%d%d",&n,&m);  
        int a,b,c;  
        build(1,n,1);  
        for(i=0; i> 1;  
                    if(mid - (b + 1) + 1- query(b+1,mid,1) >= 1) {  
                        minn = min(minn,mid);  
                        high = mid - 1;  
                    } else {  
                        low = mid + 1;  
                    }  
                }  
                int tmp = n - minn + 1 - query(minn,n,1) ;  
                if(c >= tmp) c = tmp;   ·  
                low = minn,high = n;  
                int maxx  = INF;  
                while(low <= high) {  
                    mid = (low + high) >> 1;  
                    tmp = mid - minn + 1 - query(minn,mid,1) ;  
                    if(tmp == c) {  
                        maxx = min(maxx,mid);   
                        high = mid - 1;  
                    } else if(tmp > c) {  
                        high = mid - 1;  
                    } else {  
                        low = mid + 1;  
                    }  
                }  
                printf("%d %d\n",minn-1,maxx-1);  
                update(minn,maxx,1,1);  
                  
            } else {  
                printf("%d\n",query(b+1,c+1,1));  
                update(b+1,c+1,1,0);  
            }  
        }  
        puts("");  
    }  
    return 0;  
}  

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include //形如INT_MAX一类的
#define MAX 100050
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;

struct node {
    int r,l,mid;
    int lazy,sum;
} edge[4*MAX];

void up(int num) {
    edge[num].sum = edge[L(num)].sum + edge[R(num)].sum;
}

void build(int l,int r,int num) {
    edge[num].l = l;
    edge[num].r = r;
    edge[num].mid = (l+r) >> 1;
    edge[num].lazy = -1;
    if(l == r) {
        edge[num].sum = 0;
        return ;
    }
    build(l,edge[num].mid,L(num));
    build(edge[num].mid+1,r,R(num));
    //
    up(num);
}

void down(int num) {
    //if(edge[num].l == edge[num].r) return ;
    if(edge[num].lazy != -1) {
        edge[L(num)].lazy = edge[num].lazy;
        edge[R(num)].lazy = edge[num].lazy;
        edge[L(num)].sum = (edge[L(num)].r - edge[L(num)].l + 1) * edge[num].lazy;
        edge[R(num)].sum = (edge[R(num)].r - edge[R(num)].l + 1) * edge[num].lazy;
        edge[num].lazy = -1;
    }

}

void updat