题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4614
题意：给定一个区间[0,N-1],初始时每个位置上的数字都是0，可以对其进行以下两种操作：
1、在位置A开始寻找F(如果没有这么多，则有多少个就找多少个)个数值为0的位置，把位置上的数修改为1,并返回第一个和最后一个修改的位置
2、查询区间[a,b]内1的个数，并把区间[a,b]每个位置上的数修改为0
线段树功能：区间更替，区间求和。
分析：sum[rt]表示区间0的个数，二分找出0~L的num个0，再找出0~R的num+y个0，则区间里刚好有y个0种植，将L~R更替为1；
查询含有1的个数：区间长度len（r-l+1）-query(l,r)（0的个数），更替区间（l，r）为0.
#pragma comment(linker,"/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 10007 #define inf 0x3f3f3f3f #define N 50010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; int sum[N<<2],col[N<<2]; void Pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { col[rt]=-1; if(l==r) { sum[rt]=1; return; } int m=(l+r)>>1; build(lson); build(rson); Pushup(rt); } void Pushdown(int rt,int len) { if(col[rt]!=-1) { col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1]=(len-(len>>1))*col[rt]; sum[rt<<1|1]=(len>>1)*col[rt]; col[rt]=-1; } } void update(int L,int R,int c,int l,int r,int rt) { if(L<=l&&r<=R) { col[rt]=c; sum[rt]=(r-l+1)*c; return; } Pushdown(rt,r-l+1); int m=(l+r)>>1; if(L<=m)update(L,R,c,lson); if(m<R)update(L,R,c,rson); Pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return sum[rt]; } Pushdown(rt,r-l+1); int m=(l+r)>>1; int res=0; if(L<=m)res+=query(L,R,lson); if(m<R)res+=query(L,R,rson); return res; } int bin(int x,int y,int num,int cnt) { int l=x,r=y,ans; while(l<=r) { int mid=(l+r)>>1; if(query(0,mid,0,y,1)-num>=cnt) r=mid-1,ans=mid; else l=mid+1; } return ans; } int main() { int t,n,m,num; int op,x,y; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); build(0,n-1,1); while(m--) { scanf("%d%d%d",&op,&x,&y); if(op==1) { int sum=query(x,n-1,0,n-1,1); if(sum==0) { puts("Can not put any one."); continue; } if(sum<y)y=sum; if(x-1>=0)num=query(0,x-1,0,n-1,1); else num=0; int left,right; left=bin(x,n-1,num,1); right=bin(x,n-1,num,y); printf("%d %d ",left,right); update(left,right,0,0,n-1,1); } else { printf("%d ",y-x+1-query(x,y,0,n-1,1)); update(x,y,1,0,n-1,1); } } puts(""); } }