【NOIP2013模拟联考9】阿Q的停车场

Description

刚拿到驾照的KJ 总喜欢开着车到处兜风,玩完了再把车停到阿Q的停车场里,虽然她对自己停车的水平很有信心,但她还是不放心其他人的停车水平,尤其是Kelukin。于是,她每次都把自己的爱车停在距离其它车最远的一个车位。KJ 觉得自己这样的策略非常科学,于是她开始想:在一个停车场中有一排车位,从左到右编号为 1 到 n,初始时全部是空的。有若干汽车,进出停车场共 m 次。对于每辆进入停车场的汽车,会选择与其它车距离最小值最大的一个车位,若有多个符合条件,选择最左边一个。KJ 想着想着就睡着了,在她一旁的Kelukin想帮她完成这个心愿,但是他又非常的懒,不愿意自己动手,于是就把这个问题就留给了你:在KJ 理想的阿 Q 的停车场中,给你车辆进出的操作序列,依次输出每辆车的车位编号。

Input

第一行,两个整数 n 和 m,表示停车场大小和操作数;

接下来 m 行,每行两个整数,F 和 x

F 是 1 表示编号为 x 的车进停车场;

F 是 2 表示编号为 x 的车出停车场;

保证操作合法,即:

出停车场的车一定目前仍在停车场里;

停车场内的车不会超过 n;

Output

对于所有操作 1,输出一个整数,表示该车车位的编号。

Sample Input

7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8

Sample Output

1
7
4
2
7
4
1
3

Data Constraint

对30%的数据 n<=1000 ,m<=1000
对60%的数据 n<=200000,m<=2000
对100%的数据n,m<=200000,车的编号小于等于 10^6

Analysis

我当时一看此题,就觉得第一第二个插入操作的输出很奇怪。实际上,我们们不能认为在[1..n]个停车位中,第0个与第n+1个停有车。所以说处理此类情况要特判。对于其他情况就是找出一段最长未停车线段,然后它的答案除以二就是距离最远车的距离,再根据前面第1个位置与第n个位置的特判得出答案。

对于30%数据

通过暴力的O(n*m)就可以得出答案。
先建立一个长度为n的bool数组,标示每个位置是否被车占用。
用一个car[1e6]数组表示每一辆车对应的编号。
再用一个a[N]数组表示各个位置距离两旁(或一旁)的车(0与n-1不能算做有车)的最近距离.
对于 1 询问:通过前后各扫描一次,更新a数组,再从a数组中找出一个最大的位置,将车停在那里。O(N)
对于 2 询问:只需从car数组中找到该车的位置将其删除即可,O(1)

对于60%数据
嘿嘿,我也不知道了!

对于100%数据
我是用线段树来实现的。(据某位大神说,可以用堆来做。然而我并不会)用线段树还是相对简单的。首先我们对区间[1..n]开一课线段树。对于每一个节点,维护4个值。分别是l,r,mid,p。l表示在当前结点线段树所在区间,最左边的车停的位置。同理,r表示做右边的车所停的位置。mid表示在这个小区间[l,r]中的紧邻的两辆车的最长距离除以2后的值。p表示取得mid值是所在的紧邻的两辆车的中间位置,也就是在[l,r]中的答案值。

对于 1 询问:访问线段树的第一个节点,我们比较l-1,n-r,mid的值哪个更大,就选哪个,它们的答案依次是1,n,mid。假设我们求得的位置是car[x]。然后访问[car[x],car[x]]所在的线段树的叶子节点,初始化它的值,然后回溯,进行合并。对于h[x].l与h[x].r可以通过两个儿子的l,r信息得出。对于h[x].mid值,首先在左右儿子的mid值中去一个最大的值。其次考虑一种情况,就是夹在两个线段之间的距离,可以通过(h[x+x+1].l-h[x+x].r) div 2 的值得出在于mid进行比较,然后p就随着mid的值的更新而更新。
对于2询问:访问询问车所在的位置,直接将它的叶子节点[car[x],car[x]]删除,然后回溯时,再做一次合并操作。即可

Code

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
const	maxc=1000005;maxn=200005;
type node=record
l,r,mid,p:longint;
end;
var i,j,k,m,n,ch,num,sum:longint;
car:array[1..maxc] of longint;
h:array[1..4*maxn] of node;
procedure merger(x:longint);
var t:longint;
begin
if h[x+x].l>0 then h[x].l:=h[x+x].l else h[x].l:=h[x+x+1].l;
if h[x+x+1].r>0 then h[x].r:=h[x+x+1].r else h[x].r:=h[x+x].r;
h[x].mid:=h[x+x].mid;
h[x].p:=h[x+x].p;
if (h[x+x+1].l>0) and (h[x+x].r>0) then begin
t:=(h[x+x+1].l-h[x+x].r) div 2;
if t>h[x].mid then begin
h[x].mid:=t;
h[x].p:=(h[x+x+1].l+h[x+x].r) div 2;
end;
if h[x+x+1].mid>h[x].mid then begin
h[x].mid:=h[x+x+1].mid;
h[x].p:=h[x+x+1].p;
end;
end;
end;
procedure work(x,l,r,num,kind:longint);
var mid:longint;
begin
if l=r then begin
if kind=2 then begin
h[x].l:=0;h[x].r:=0;
h[x].mid:=0;h[x].p:=0;
end else begin
h[x].l:=l;h[x].r:=r;
h[x].mid:=0;h[x].p:=0;
end;
exit;
end;
mid:=(l+r)>>1;
if num<=mid then work(x+x,l,mid,num,kind) else work(x+x+1,mid+1,r,num,kind);
merger(x);
end;
begin
readln(n,m);
for i:=1 to m do begin
readln(ch,num);
if ch=1 then begin
if h[1].l=0 then begin
car[num]:=1;
end else begin
sum:=-maxlongint;
if h[1].l-1>sum then begin
sum:=h[1].l-1;
car[num]:=1;
end;
if h[1].mid>sum then begin
sum:=h[1].mid;
car[num]:=h[1].p;
end;
if n-h[1].r>sum then begin
sum:=n-h[1].r;
car[num]:=n;
end;
end;
writeln(car[num]);
work(1,1,n,car[num],1);
end else begin
work(1,1,n,car[num],2);
end;
end;
end.