题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614
题意：
给你N个花瓶，编号是0 到 N - 1 ，初始状态花瓶是空的，每个花瓶最多插一朵花。
然后有2个操作。
操作1，a b c ，往在a位置后面(包括a)插b朵花，输出插入的首位置和末位置。
操作2,a b ,输出区间[a , b ]范围内的花的数量，然后全部清空。
很显然这是一道线段树。区间更新，区间求和，
操作2，很显然就是线段树的区间求和，求出[a , b]范围内的花朵的数量，区间更新，将整个区间全部变成0。
操作1，这里我们首先需要找出他的首位置和末位置，所以需要二分他的位置。
首先我们二分他的首位置, l = a , r = n ，在这个区间内二分，找出第一个0的位置，那就是该操作的首位置pos1。
然后再二分他的末位置，l = pos1 , r = n ，找到第b个0，就是该操作的末位置pos2，然后区间更新[pos1 ,pos2]全部置为1
我最初主要是对二分不熟悉，做了几道二分的题目后再做这道题就很快了。。。。
很裸的一道线段树了，一定要用lazy思想设置flag标记位，不能更新到低，否则会超时的。。。。
代码：
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 50010
int n,m;
class node
{
public:
int l;
int r;
int sum;
int flag;
};
node segTree[maxn*];
void Build(int num, int l, int r)
{
segTree[num].l=l;
segTree[num].r=r;
segTree[num].sum=;
segTree[num].flag=;
if(l==r) return;
int mid=(l+r)/;
Build(num*,l,mid);
Build(num*+,mid+,r);
}
int query(int num, int l, int r)
{
if(segTree[num].l ==l && segTree[num].r==r)
{
return segTree[num].sum;
}
int mid=(segTree[num].l + segTree[num].r)/;
if(segTree[num].flag==)
{
segTree[num*].sum=(segTree[num*].r - segTree[num*].l +);
segTree[num*+].sum=(segTree[num*+].r- segTree[num*+].l +);
segTree[num*].flag=;
segTree[num*+].flag=;
segTree[num].flag=;
}
if(segTree[num].flag ==-)
{
segTree[num*].sum=segTree[num*+].sum=;
segTree[num*].flag=segTree[num*+].flag=-;
segTree[num].flag=;
}
if(r <=mid) return query(num*,l,r);
else if(l >mid ) return query(num*+,l,r);
else
{
return query(num*,l,mid)+query(num*+,mid+,r);
}
}
void Update1(int num,int l, int r)
{
if(segTree[num].flag==) return;
if(segTree[num].l ==l && segTree[num].r==r)
{
segTree[num].sum=r-l+;
segTree[num].flag=;
return ;
}
int mid=(segTree[num].l + segTree[num].r)/;
if(segTree[num].flag==-)
{
segTree[num*].sum=segTree[num*+].sum=;
segTree[num*].flag=segTree[num*+].flag=-;
segTree[num].flag=;
}
if(r<=mid) Update1(num*,l,r);
else if(l>mid) Update1(num*+,l,r);
else
{
Update1(num*,l,mid);
Update1(num*+,mid+,r);
}
segTree[num].sum=segTree[num*].sum+segTree[num*+].sum;
}
void Update2(int num,int l,int r)
{
if(segTree[num].flag == -) return ;
if(segTree[num].l == l && segTree[num].r ==r)
{
segTree[num].flag=-;
segTree[num].sum=;
return ;
}
int mid=(segTree[num].l +segTree[num].r)/;
if(segTree[num].flag==)
{
segTree[num*].sum=(segTree[num*].r -segTree[num*].l +);
segTree[num*+].sum=(segTree[num*+].r -segTree[num*+].l +);
segTree[num*].flag=;
segTree[num*+].flag=;
segTree[num].flag=;
}
if(r<=mid) Update2( num*,l,r);
else if(l>mid) Update2(num*+,l,r);
else
{
Update2(num*,l,mid);
Update2(num*+,mid+,r);
}
segTree[num].sum=segTree[num*].sum+segTree[num*+].sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int k;
int A,F,B;
scanf("%d%d",&n,&m);
Build(,,n);
while(m--)
{
scanf("%d",&k);
if(k==)
{
scanf("%d%d",&A,&F);
A++;
int tol=n-A+-query(,A,n);
if(tol==)
{
cout<<"Can not put any one."<<endl;
continue;
} if(tol<F) F=tol;
int l=A;
int r=n;
int mid;
int pos1=n+,pos2=n+;
while(l<=r)
{
mid=(l+r)/;
int tol=mid-A+-query(,A,mid);
if(tol>=) pos1=min(pos1,mid),r=mid-;
else l=mid+;
} l=pos1;
r=n;
while(l<=r)
{
mid=(l+r)/;
int tol=mid-pos1+-query(,pos1,mid);
if(tol>=F) pos2=min(pos2,mid),r=mid-;
else l=mid+;
}
cout<<pos1-<<" "<<pos2-<<endl;
Update1(,pos1,pos2);
}
else
{
scanf("%d%d",&A,&B);
A++;B++;
int tol=query(,A,B);
cout<<tol<<endl;
Update2(,A,B);
} }
cout<<endl;
}
return ;
}
。