HDU 4614 Vases and Flowers 【线段树】+【二分】

题目大意：

有n个花瓶，每个花瓶中只能放一朵花。两种操作，一种是从A开始放F朵花，如果有的花瓶中已经有花则跳过这个花瓶，往下一个花瓶放；第二种是将区间[A,B]之间花瓶中的花清空。如果是第一种操作，输出这次放的花的左右端点；如果是第二种操作，输出这次总共清理出了多少支花。

解题分析：

本题可以很巧妙的将这两种操作全部转化为区间修改，毫无疑问，第二种操作肯定是区间修改；对于第一种操作，可以用二分答案将x后的第num个空瓶的坐标查找出来，因为二分答案时需要直接查询指定区间内空瓶的数量，所以线段树叶子节点维护一个值，代表该区间空瓶的数量，得到第一个和最后一个空瓶的数量后，直接对该区间进行区间修改，将空瓶数量全部置0即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 #define Lson rt<<1,l,mid
 7 #define Rson rt<<1|1,mid+1,r
 8 const int M =5e4+5;
 9 int n,m;
10 int tr[M<<2],lazy[M<<2];
11 //lazy[rt]初始化为-1，lazy[rt]==0,代表这个区间瓶子全满,lazy[rt]==1,代表这个区间瓶子全空
12 void Pushup(int rt){ tr[rt]=tr[rt<<1]+tr[rt<<1|1]; }
13 void Pushdown(int rt,int len){
14     if(lazy[rt]!=-1){
15         int tmp=lazy[rt];
16         lazy[rt<<1]=tmp;
17         lazy[rt<<1|1]=tmp;
18         tr[rt<<1]=(len-(len>>1))*tmp;
19         tr[rt<<1|1]=(len>>1)*tmp;
20         lazy[rt]=-1;
21     }
22 }
23 void build(int rt,int l,int r){
24     lazy[rt]=-1;
25     if(l==r){
26         tr[rt]=1;
27         return;
28     }
29     int mid=(l+r)>>1;
30     build(Lson);
31     build(Rson);
32     Pushup(rt);
33 }
34 void update(int rt,int l,int r,int L,int R,int c){
35     if(L<=l&&r<=R){
36         lazy[rt]=c;
37         tr[rt]=(r-l+1)*c;
38         return;
39     }
40     Pushdown(rt,r-l+1);
41     int mid=(l+r)>>1;
42     if(L<=mid)update(Lson,L,R,c);
43     if(R>mid)update(Rson,L,R,c);
44     Pushup(rt);
45 }
46 int query(int rt,int l,int r,int L,int R){    //查询指定区间的空瓶数量
47     if(L<=l&&r<=R)return tr[rt];
48     Pushdown(rt,r-l+1);
49     int mid=(l+r)>>1;
50     int ans=0;
51     if(L<=mid)ans+=query(Lson,L,R);
52     if(R>mid)ans+=query(Rson,L,R);
53     return ans;
54 }
55 int bin_search(int x,int num){     //二分答案，查找从x开始的第num个空瓶子的下标
56     int l=x,r=n,ans;
57     while(l<=r){
58         int mid=(l+r)>>1;
59         if(query(1,1,n,x,mid)>=num)ans=mid,r=mid-1;
60         else l=mid+1;
61     }
62     return ans;
63 }
64 int main(){
65     int T;scanf("%d",&T);
66     while(T--){
67         scanf("%d%d",&n,&m);
68         build(1,1,n);
69         while(m--){
70             int op,x,y;
71             scanf("%d%d%d",&op,&x,&y);
72             if(op==1){   
73                 x++;  //由于线段树叶子节点习惯从1~n开始存储，所以a++
74                 int cnt=query(1,1,n,x,n);  //查询这个区间的空瓶子数量
75                 if(cnt==0)printf("Can not put any one.
");
76                 else{  //二分查找第一个空瓶子和最后一个空瓶子的下标
77                     int le=bin_search(x,1);
78                     int ri=bin_search(x,min(cnt,y));
79                     update(1,1,n,le,ri,0);
80                     printf("%d %d
",le-1,ri-1);
81                 }
82             }
83             else{
84                 x++,y++;
85                 printf("%d
",y-x+1-query(1,1,n,x,y));
86                 update(1,1,n,x,y,1);
87             }
88         }
89         printf("
");
90     }
91     return 0;
92 }

2018-09-29

HDU 4614 Vases and Flowers 【线段树】+【二分】

相关推荐