hdu4614Vases and Flowers(线段树，段设置，更新时范围的右边值为变量)
Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>#define N 50010struct node{int sum,b;//sum为在范围内的花数，b为判断是否全为空或全为满则为1，否则为0}tree[4*N];void biulde(int l,int r,int k){int m=(l+r)/2;tree[k].sum=0; tree[k].b=1;if(l==r) return ;biulde(l,m,k*2); biulde(m+1,r,k*2+1);}void set_child(int l,int r,int k){int m=(l+r)/2;tree[k*2].b=tree[k*2+1].b=1;if(tree[k].sum==r-l+1){tree[k*2].sum=m-l+1; tree[k*2+1].sum=r-m;}else{tree[k*2].sum=0; tree[k*2+1].sum=0;}}int QL,QR,L,R,ans,n;void putInFlower(int l,int r,int k){if(ans<=0) return ;int m=(l+r)/2;if(L<=l&&r<=R&&tree[k].b){if(!tree[k].sum) {int tans=ans;ans-=(r-l+1); tree[k].sum=r-l+1;if(QL<0) QL=l-1; QR=r-1;}else{//跳动插花范围的右边值，R刚好是插完花的右边范围的最小值，除非超出花瓶数量，则为nR+=(r-l+1); if(R>n) R=n;}return ;}if(tree[k].b) set_child(l,r,k); tree[k].b=0;if(L<=m) putInFlower(l,m,k*2);if(R>m) putInFlower(m+1,r,k*2+1);tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;if(tree[k].sum==r-l+1||!tree[k].sum)tree[k].b=1;}void clear(int l,int r,int k){int m=(l+r)/2;if(L<=l&&r<=R){ans+=tree[k].sum; tree[k].b=1; tree[k].sum=0;return ;}if(tree[k].b)set_child(l,r,k);tree[k].b=0;if(L<=m) clear(l,m,k*2);if(R>m) clear(m+1,r,k*2+1);tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;if(tree[k].sum==r-l+1||!tree[k].sum)tree[k].b=1;}int main(){int t,m,x;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);biulde(1,n,1);while(m--){scanf("%d%d",&x,&L); L++;if(x==1){scanf("%d",&ans);R=L+ans-1; QL=QR=-1; putInFlower(1,n,1);if(QR>=0) printf("%d %d\n",QL,QR);elseprintf("Can not put any one.\n");}else{scanf("%d",&R); R++; ans=0;clear(1,n,1);printf("%d\n",ans);}}printf("\n");}return 0;}
