Input The first line contains an integer T, indicating the number of test cases.
For each test case, the first line contains two integers N(1 < N < 50001) and M(1 < M < 50001). N is the number of vases, and M is the operations of Alice. Each of the next M lines contains three integers. The first integer of one line is K(1 or 2). If K is 1, then two integers A and F follow. It means Alice receive F flowers and try to put a flower in the vase A first. If K is 2, then two integers A and B follow. It means the owner would like to clean the vases numbered from A to B(A <= B).Output For each operation of which K is 1, output the position of the vase in which Alice put the first flower and last one, separated by a blank. If she can not put any one, then output ‘Can not put any one.‘. For each operation of which K is 2, output the number of discarded flowers.
Output one blank line after each test case.Sample Input
2 10 5 1 3 5 2 4 5 1 1 8 2 3 6 1 8 8 10 6 1 2 5 2 3 4 1 0 8 2 2 5 1 4 4 1 2 3
Sample Output
[pre]3 7 2 1 9 4 Can not put any one. 2 6 2 0 9 4 4 5 2 3
现在要你插花，有n个花瓶，m次操作，初始花瓶中无花，操作有两种方式
操作1：1 a b，从编号为a的花瓶开始插花，共插b朵花，花只能插到无花的花瓶中，如果最后插不完b朵花，剩下的花舍弃掉
操作2：1 a b，把从编号a到编号b的所有花瓶里的花全部清理掉
对于操作1，需要输出开始插花的瓶子编号，和最后插花的瓶子编号
对于操作2，需要输出在a~b中总共清理了多少个花瓶中的花
题解：线段树+二分，分析一下这道题，如果是情理，那是十分容易的，只需要lazy，tag就可以了，但是如何去找区间第一个可以插的位置呢，
线段树可以记录该位置里的有多少个空位置，那么我们可以二分，来查找判断是多了，还是少了，这样就可以了，时间复杂度就控制了
下来，然后整个区间填满，什么区间？就是第一支花和最后一枝花那个区间，hh。
1 #include<iostream> 2 #include<stdio.h> 3 #include<map> 4 #include<algorithm> 5 #include<math.h> 6 #include<queue> 7 #include<stack> 8 #include<string> 9 #include<cstring> 10 using namespace std; 11 struct node 12 { 13 int l,r; 14 int tag;//如果为-1则为初始状态，如果为0意思将子区间内的花清空，为1为插满花 15 int v;//记录区间内插了多少花 16 }t[50005*4]; 17 int n; 18 void Build(int l,int r,int k) 19 { 20 t[k].l=l; 21 t[k].r=r; 22 t[k].v=0; 23 t[k].tag=-1; 24 if(l==r) 25 return; 26 int mid=(l+r)/2; 27 Build(l,mid,k*2); 28 Build(mid+1,r,k*2+1); 29 } 30 void pushdown(int k)//向下传递状态 31 { 32 t[k*2].tag=t[k*2+1].tag=t[k].tag; 33 t[k*2].v=t[k].tag*(t[k*2].r-t[k*2].l+1); 34 t[k*2+1].v=t[k].tag*(t[k*2+1].r-t[k*2+1].l+1); 35 t[k].tag=-1; 36 } 37 void update(int l,int r,int v,int k) 38 { 39 if(t[k].l==l&&t[k].r==r) 40 { 41 t[k].tag=v; 42 t[k].v=v*(r-l+1);//插满或者清空 43 return; 44 } 45 if(t[k].tag!=-1)//要传递状态 46 pushdown(k); 47 int mid=(t[k].l+t[k].r)/2; 48 if(r<=mid) 49 update(l,r,v,k*2); 50 else if(l>mid) 51 update(l,r,v,k*2+1); 52 else 53 { 54 update(l,mid,v,k*2); 55 update(mid+1,r,v,k*2+1); 56 } 57 t[k].v=t[k*2].v+t[k*2+1].v;//向上传递区间信息 58 } 59 int query(int l,int r,int k)//查询区间内插花的数目 60 { 61 if(t[k].l==l&&t[k].r==r) 62 { 63 return t[k].v; 64 } 65 if(t[k].tag!=-1)//同样lazy tag 66 pushdown(k); 67 int mid=(t[k].l+t[k].r)/2; 68 if(r<=mid) 69 return query(l,r,k*2); 70 else if(l>mid) 71 return query(l,r,k*2+1); 72 else 73 { 74 return query(l,mid,k*2)+query(mid+1,r,k*2+1); 75 } 76 t[k].v=t[k*2].v+t[k*2+1].v; 77 } 78 int dive(int s,int num)//二分查找，第一个为开始的位置，第二个参数为要插多少个 79 { 80 int temp=query(s,n,1); 81 if(temp==n-s+1)//如果一个都不能插 82 return -1; 83 if(n-s+1-temp<num)//如果空位小于要插的数目，改下要插的数目 84 num=n-s+1-temp; 85 int l=s; 86 int r=n; 87 int mid,d; 88 int f=-1; 89 while(r>=l)//二分 90 { 91 mid=(l+r)/2; 92 d=mid-s+1-query(s,mid,1);//d为从s到mid的空位数目 93 if(d>num) 94 { 95 r=mid-1; 96 } 97 else if(d<num) 98 l=mid+1; 99 else//如果空位的数目正好要一个个减 100 { 101 f=mid;//为了保存第一个能够满足该数目空位的位置 102 r=mid-1; 103 } 104 } 105 return f; 106 } 107 int main() 108 { 109 int i,j,test,x,y,d,m; 110 scanf("%d",&test); 111 while(test--) 112 { 113 scanf("%d%d",&n,&m); 114 n--; 115 Build(0,n,1); 116 for(i=0;i<m;i++) 117 { 118 scanf("%d%d%d",&d,&x,&y); 119 if(d==1) 120 { 121 int temp=dive(x,1);//查找插的第一个位置 122 if(temp==-1) 123 { 124 printf("Can not put any one.\n"); 125 } 126 else 127 { 128 int en=dive(x,y);//查找插的第二个位置 129 printf("%d %d\n",temp,en); 130 update(temp,en,1,1);//更新插满区间 131 } 132 } 133 else 134 { 135 printf("%d\n",query(x,y,1)); 136 update(x,y,0,1);//清空区间 137 } 138 } 139 printf("\n"); 140 } 141 return 0; 142 }
原文：http://www.cnblogs.com/fengzhiyuan/p/7536031.html