hdu 4614 Vases and Flowers

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

【2013多校联合第二场】

题意:总区间[0,n-1],有两种操作

1 a b ,表示从a花瓶开始,插b朵花,每个瓶子只能插一朵花,如果有些瓶子已经插了花就越过,如果插到最后一个瓶子花没插完就丢掉。输出插花的首位置和末位置。如果1朵花都插不进去就输出那串英文

2 a b ,先输出[a,b]内已经插了多少花,然后将区间内的花清空

线段树结点内只记录了一个信息,该区间内有多少单元可以使用。这个信息比较简陋但是够用了。在操作1找首位置和末位置,需要两次二分找到首位置和末位置。不能插花的情况就是,该段区间内一个可用单元都没有。只要区间内还有可能单元哪怕一个,都一定能找到首位置和末位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 50010
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n;
struct tree{
int l,r,cnt; //cnt记录这个区间有多少单元可用
tree(){}
tree(int _l,int _r,int _cnt){ //构造函数
l = _l; r = _r; cnt = _cnt;
}
int mid(){ //计算区间的中点
return (l+r)>>1;
}
int callen(){ //计算这个区间的长度
return r-l+1;
}
}t[4*N];

void build(int rt,int a,int b){ //建树
t[rt] = tree(a,b,b-a+1);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void PushUp(int rt){ //自底向上的更新
t[rt].cnt = t[lson(rt)].cnt + t[rson(rt)].cnt;
}

void PushDown(int rt){
//自顶向下的更新,即lazy,这里我不另外设置一个变量来判断lazy,因为cnt这个变量就可以判断
if(t[rt].cnt == 0)
t[lson(rt)].cnt = t[rson(rt)].cnt = 0;
if(t[rt].cnt == t[rt].callen()){
t[lson(rt)].cnt = t[lson(rt)].callen();
t[rson(rt)].cnt = t[rson(rt)].callen();
}
//只有cnt = 0 || cnt = len 的情况下,才能lazy,才能将信息传递给左右儿子区间
}

int query(int rt,int a,int b){ //查询[a,b]区间内有多少可用的空间
if(t[rt].l == a && t[rt].r == b)
return t[rt].cnt;
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
return query(lson(rt),a,b);
else if(a > mid)
return query(rson(rt),a,b);
else{
return query(lson(rt),a,mid) + query(rson(rt),mid+1,b);
}
}

void updata(int rt,int a,int b,int v){ //v是个参数,1时将[a,b]全部插满花,-1时将[a,b]的花清空
if(t[rt].l == a && t[rt].r == b){
if(v == -1) t[rt].cnt = t[rt].callen();
else t[rt].cnt = 0;
return ;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
updata(lson(rt),a,b,v);
else if(a > mid)
updata(rson(rt),a,b,v);
else{
updata(lson(rt),a,mid,v);
updata(rson(rt),mid+1,b,v);
}
PushUp(rt);
}

int main(){
int q,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&q);
build(1,0,n-1);
while(q--){
int op,l,r,cnt;
int low,high,firstpos,lastpos;
scanf("%d",&op);
if(op == 1){
scanf("%d%d",&l,&cnt);
low = l; high = n-1;
firstpos = lastpos = -1;
while(low <= high){ //第一个二分,得到插花的首位置,firstpos
int mid = (low + high) >> 1;
int res = query(1,l,mid);
if(res > 0){
firstpos = mid; high = mid - 1;
}
else low = mid + 1;
}
if(firstpos == -1){
puts("Can not put any one.");
continue;
}
low = firstpos; high = n-1;
cnt = min(cnt,query(1,firstpos,n-1));
while(low <= high){ //第二个二分,得到插花的末位置
int mid = (low + high) >> 1;
int res = query(1,firstpos,mid);
if(res >= cnt){
lastpos = mid; high = mid - 1;
}
else low = mid + 1;
}
printf("%d %d\n",firstpos,lastpos);
updata(1,firstpos,lastpos,1); //那么区间[firstpos,lastpos]都插完了花,要更新区间
}
else{
scanf("%d%d",&l,&r);
cnt = query(1,l,r); //先查询区间有多少可用的位置
printf("%d\n",r-l+1-cnt); //区间长度-可用位置 = 插了多少花
updata(1,l,r,-1); //把这个区间里面的花全部清空
}
}
puts("");
}
return 0;
}