题意：
给你N个花瓶，编号是0 到 N - 1 ，一开始每个花瓶都是空的，你有两个操作：
第一个操作：
从第x个花瓶起开始插花，总共插y束，如果遇到花瓶中有花就跳过这个花瓶，直到花插完或者
插到第N-1个花瓶为止，输出插第一朵花的位置和最后一朵花的位置
第二个操作
将第x个花瓶到第y个花瓶之间的花扔掉，输出扔掉的花的数目
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614
思路
我们通过线段树来记录每个区间中花的数目，区间长度减去该区间中花的数目即为该区间
中空花瓶的数目，我们通过二分位置来确定插花的起始位置和终止位置
代码：
#include <bits/stdc++.h> int n,m; using namespace std; const int MAXN=5e4+4; typedef long long ll; int lazy[MAXN<<4],tree[MAXN<<4]; void push_up(int node) { tree[node]=tree[node<<1]+tree[node<<1|1]; } void build(int node,int l,int r) { lazy[node]=-1,tree[node]=0; if(l==r) return; int mid=(l+r)>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); } void push_down(int node,int l,int r,int mid) { if(lazy[node]!=-1) { lazy[node<<1]=lazy[node<<1|1]=lazy[node]; tree[node<<1]=(mid-l+1)*lazy[node]; tree[node<<1|1]=(r-mid)*lazy[node]; lazy[node]=-1; } } void update(int node,int l,int r,int x,int y,int k) { if(x<=l&&y>=r) { lazy[node]=k; tree[node]=(r-l+1)*k; return; } int mid=(l+r)>>1; push_down(node,l,r,mid); if(x<=mid) update(node<<1,l,mid,x,y,k); if(y>mid) update(node<<1|1,mid+1,r,x,y,k); push_up(node); } int query(int node,int l,int r,int x,int y) { if(x<=l&&y>=r) { return tree[node]; } int mid=(l+r)>>1; push_down(node,l,r,mid); int ans=0; if(x<=mid) ans+=query(node<<1,l,mid,x,y); if(y>mid) ans+=query(node<<1|1,mid+1,r,x,y); return ans; } int search_(int x,int num) //二分查找位置 { int temp=query(1,0,n,x,n);//x到n的空位数 if(temp==n-x+1)//没有空位的情况下 return -1; //如果从x到n的空位数比要插的数少，那么要插的数就是x到n的空位数 if(n-x+1-temp<num) num=n-x+1-temp; int down=x,up=n,index=0; while(down<=up) { int mid=(down+up)>>1; if(mid-x+1-query(1,0,n,x,mid)<num) down=mid+1; else if(mid-x+1-query(1,0,n,x,mid)>num) up=mid-1; else { index=mid;up=mid-1; } } return index; } int main() { int t;scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m);n--; build(1,0,n); while(m--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==1) { int fir=search_(x,1);//寻找第一个位置 if(fir==-1) printf("Can not put any one. "); else { int sec=search_(x,y);//寻找第二个位置 printf("%d %d ",fir,sec); update(1,0,n,fir,sec,1);//修改区间值 } } else { printf("%d ",query(1,0,n,x,y)); update(1,0,n,x,y,0);//修改区间值 } } printf(" "); } return 0; }