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

发表于 分类于 ， 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

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.