codeforces Parking Lot

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

http://codeforces.com/problemset/problem/46/D

线段树

题意:给出n长度的单元(0到n-1编号)和B,F

1 len:给出一个车的长度为len,靠最左边停,离他前面的车要有B距离,离后面的车要F距离(如果停在最前面或者最后面,则不需要考虑B和F),另外如果后面没车,只需要考虑B即可,不懂的话可以看sample 1和sample 2

2 id:将第id次操作停进去的车开出来。注意这里的操作时这样算的,无论是“1”还是“2”操作都算作一次

为了解决最左端不用考虑B最右端不用考虑F的问题,只需要把总区间变为[-B,n-1+F]即可

另外每次停车,要找的长度都是B+len+F,找到了位置pos后,实际停车的位置应该是pos-B。另外停了车就要更新,更新的区间是[pos-B,pos-B+len-1]

即更新长度为len而不是len+B+F,这个想想就懂了

查询最左的区间,记录Max,pre,suf,一个区间内最长可用长度,前缀可用长度,后缀可用长度

要找len,如果当前区间的Max < len,那么肯定找不到

如果L.Max > len,一定在左边可以找到

如果L.suf + R.pre > len,一定能在中间找到

否则只能在R这部分找到了

整个题还是比较简单的

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
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100510
#define INF 0x3f3f3f3f
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

struct Car{
int len,pos;
Car(){}
Car(int __len){
len = __len; pos = -1;
}
}car[N];
struct SegTree{
int l,r,mid,len;
int Max,pre,suf;
SegTree(){}
SegTree(int __l,int __r){
l = __l; r = __r; mid = (l+r)>>1; len = r-l+1;
Max = pre = suf = 0;
}
}t[N<<2];

void PushUp(int rt){
t[rt].pre = t[lson(rt)].pre;
t[rt].suf = t[rson(rt)].suf;
if(t[lson(rt)].pre == t[lson(rt)].len){
t[rt].pre = t[lson(rt)].len + t[rson(rt)].pre;
}
if(t[rson(rt)].suf == t[rson(rt)].len){
t[rt].suf = t[lson(rt)].suf + t[rson(rt)].len;
}
t[rt].Max = max(t[lson(rt)].Max , t[rson(rt)].Max);
t[rt].Max = max(t[rt].Max , t[lson(rt)].suf + t[rson(rt)].pre);
}

void PushDown(int rt){
if(t[rt].Max == 0){
t[lson(rt)].Max = t[lson(rt)].pre = t[lson(rt)].suf = 0;
t[rson(rt)].Max = t[rson(rt)].pre = t[rson(rt)].suf = 0;
}
if(t[rt].Max == t[rt].len){
t[lson(rt)].Max = t[lson(rt)].pre = t[lson(rt)].suf = t[lson(rt)].len;
t[rson(rt)].Max = t[rson(rt)].pre = t[rson(rt)].suf = t[rson(rt)].len;
}
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b){
t[rt].Max = t[rt].pre = t[rt].suf = 1;
return ;
}
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
PushUp(rt);
}

void Del(int rt,int val){
if(val == 0){
t[rt].Max = t[rt].pre = t[rt].suf = 0;
}
else{
t[rt].Max = t[rt].pre = t[rt].suf = t[rt].len;
}
}

int query(int rt,int x){
if(t[rt].Max < x) return -INF;
if(t[rt].pre >= x) return t[rt].l;
PushDown(rt);
int LMax = t[lson(rt)].Max;
int RMax = t[rson(rt)].Max;
int MMax = t[lson(rt)].suf + t[rson(rt)].pre;
if(LMax >= x){
return query(lson(rt),x);
}
else if(MMax >= x){
return t[lson(rt)].r - t[lson(rt)].suf + 1;
}
else{
return query(rson(rt),x);
}
}

void updata(int rt,int a,int b,int val){
if(t[rt].l == a && t[rt].r == b){
Del(rt,val);
return ;
}
PushDown(rt);
int mid = t[rt].mid;
if(b <= mid)
updata(lson(rt),a,b,val);
else if(a > mid)
updata(rson(rt),a,b,val);
else{
updata(lson(rt),a,mid,val);
updata(rson(rt),mid+1,b,val);
}
PushUp(rt);
}

int main(){
int n,q,cnt,B,F;
while(scanf("%d%d%d",&n,&B,&F)!=EOF){
build(1,-B,n+F-1);
scanf("%d",&q); cnt = 0;
while(q--){
int op;
scanf("%d",&op);
if(op == 1){
int len;
scanf("%d",&len);
car[++cnt] = Car(len);
car[cnt].pos = query(1,len+B+F) + B;
if(car[cnt].pos >= 0){
printf("%d\n",car[cnt].pos);
updata(1,car[cnt].pos,car[cnt].pos+len-1,0);
}
else{
puts("-1");
}
}
else{
int index;
scanf("%d",&index);
if(car[index].pos >= 0)
updata(1,car[index].pos , car[index].pos+car[index].len-1 , 1);
cnt++;
}
}
}
return 0;
}