阿 Q 的停車場

問題描述
剛拿到駕照的 KJ 總喜歡開著車到處兜風，玩完了再把車停到阿 Q 的停車場里，雖然 她對自己停車的水平很有信心，但她還是不放心其他人的停車水平，尤其是 Kelukin。于是， 她每次都把自己的愛車停在距離其它車最遠的一個車位。KJ 覺得自己這樣的策略非常科 學，于是她開始想：在一個停車場中有一排車位，從左到右編號為 1 到 n，初始時全部是 空的。有若干汽車，進出停車場共 m 次。對于每輛進入停車場的汽車，會選擇與其它車距 離最小值最大的一個車位，若有多個符合條件，選擇最左邊一個。KJ 想著想著就睡著了， 在她一旁的 Kelukin 想幫她完成這個心愿，但是他又非常的懶，不愿意自己動手，于是就把 這個問題就留給了你：在 KJ 理想的阿 Q 的停車場中，給你車輛進出的操作序列，依次輸 出每輛車的車位編號。

輸入格式
第一行，兩個整數 n 和 m，表示停車場大小和操作數；
接下來 m 行，每行兩個整數 F 和 x F 是 1 表示編號為 x 的車進停車場； F 是 2 表示編號為 x 的車出停車場；
保證操作合法，即： 出停車場的車一定目前仍在停車場里； 停車場內的車不會超過 n；

輸出格式
對于所有操作 1，輸出一個整數，表示該車車位的編號

樣例輸入
7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8

樣例輸出
1
7
4
2
7
4
1
3

提示
【數據范圍】
對 30%的數據 n<=1000 ，m<=1000 對
60%的數據 n<=200000，m<=2000
對 100%的數據 n，m<=200000，
車的編號小于等于 10^6

分析：
考場上我這個zz想了一種堆的做法，
然而實現起來有缺陷，
后來聽他們說這是一道蠻簡單的線段樹，
感覺自己退役算了。。。

根據題目的要求，
0號和n+1位是不能視為有車的，
所以這兩個位置需要特判，
一般情況下，只要找出該區間內沒有停車的最遠的區間，
區間長度>>1就是下一輛要停的車與其他車相距的最遠距離
（不知道自己在說什么）

要維護四個量
分別是x,y,mid,p
x表示在當前結點線段樹所在區間，最左邊的車停的位置
同理，y表示做右邊的車所停的位置
mid表示在這個小區間[x,y]中的緊鄰的兩輛車的最長距離除以2后的值
p表示取得mid值是所在的緊鄰的兩輛車的中間位置，也就是在[x,y]中的答案值

網上的代碼都超級**
實在是看不懂，廢了洪荒之力碼完代碼。。。

最復雜的過程就是停車（其實也很好理解）：
每一次在新停車的時候，
都查看一下第一個節點的信息（線段樹的根節點記錄的是整個區間的信息）
每輛車都有三個可能停的位置
tree[1].p,1,n
這三個點的停車相聚最遠距離分別是
tree[1].mid,
tree[1].x-1(假使第一個位置沒有停車)
n-tree[1].y(假使最后一個位置沒有停車)

從三個位置中選擇一個最優的添加

update的時候分別維護就好了
tree[bh].x=tree[lc].x;
tree[bh].y=tree[rc].y;
tree[bh].mid和tree[bh].p需要從三個值中擇優：
tree[lc]
tree[rc].mid
tree[rc].y-tree[lc].x+1; //兩個區間之間的空位

這里寫代碼片
#include<cstdio>
#include<iostream>
#include<cstring>using namespace std;const int N=200002;
struct node{int x,y,mid,p;
};
node tree[N<<4];
int n,m;
int car[1000001];  //車的位置，如果你6可以加離散化啊 void update(int bh)
{int lc=bh<<1;int rc=(bh<<1)+1;if (bh){tree[bh].x=tree[lc].x;tree[bh].y=tree[rc].y;tree[bh].mid=tree[lc].mid;tree[bh].p=tree[lc].p;if (tree[rc].mid>tree[bh].mid){tree[bh].mid=tree[rc].mid;  tree[bh].p=tree[rc].p;}int l=tree[rc].y-tree[lc].x+1;  //兩個區間之間的空位if (l>tree[bh].mid){tree[bh].mid=l;tree[bh].p=(tree[lc].y+tree[rc].x)>>1;} }return;
}void add(int bh,int l,int r,int wz,int z)
{if (l==wz&&l==r){if (z==1){tree[bh].x=l;tree[bh].y=r;tree[bh].mid=0;   //節點上有車了,當然就沒有mid和p值了 tree[bh].p=0;return;}else{tree[bh].x=0;tree[bh].y=0;tree[bh].mid=0;tree[bh].p=0;return;}}int mid=(l+r)>>1;if (wz<=mid) add(bh<<1,l,mid,wz,z);if (wz>mid) add((bh<<1)+1,mid+1,r,wz,z);update(bh);
}int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){int opt,u;scanf("%d%d",&opt,&u);if (opt==1){if (tree[1].x==0)  //整顆線段樹的信息都集中在根節點 {car[u]=1;  //整個停車場都是空的 }else{int mx=-1;if (tree[1].x-1>mx){mx=tree[1].x-1;car[u]=1;  //第一個車位沒人停 }if (tree[1].mid>mx)   {mx=tree[1].mid;car[u]=tree[1].p;}if (n-tree[1].y>mx){   //最后的車位沒人停 mx=n-tree[1].y;car[u]=n;}}printf("%d\n",car[u]);add(1,1,n,1,1); }else{add(1,1,n,car[u],-1);  //出停車場 }}return 0;
}