題目：給出1-n個停車場，陸續有車子進來 ，每次選擇一個位置，要求這個位置距離兩邊最近的車子的距離要最遠，如果有相同的位置，取標號最小的。
和POJ 的hotel類似，記錄區間的最大間隔，以及左端點的最大間隔，右端點的最大間隔。以及最大間隔的起始點
其中更新部分較為復雜，這裡Debug了我兩個小時，淚奔。。。
由於 題目要求取標號最小的，所以這裡的判斷順序不可以亂，嚴格從左到右的順序。
對於區間的最大間隔，可能是從左端點開始，這樣的起始是最小的，所以要最早判斷
接下來可能是左區間的最大間隔
然後是左區間的右間隔與右區間的左間隔的並
然後是右區間的最大間隔
最後是右端點。
開始憑感覺，隨便YY了，然後Debug了兩個小時，如果出現間隔相同的，按以上順序才能保證標號最小。
[cpp]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define eps 1e-10
#define N 200005
#define inf 1<<20
#define zero(a) (fabs(a)<eps)
#define lson (step<<1)
#define rson (step<<1|1)
using namespace std;
struct Node{
int left,right,mid;
int mx,lx,rx,val;
int dist(){return right-left+1;}
}L[N*4];
int pos[1000005];
void Bulid(int step,int l,int r){
L[step].left=l;
L[step].right=r;
L[step].mid=(l+r)/2;
L[step].mx=L[step].rx=L[step].lx=L[step].dist();
L[step].val=l;
if(l==r)
return ;
Bulid(lson,l,L[step].mid);
Bulid(rson,L[step].mid+1,r);
}
void Push_Up(int step){
L[step].lx=L[lson].lx+(L[lson].lx==L[lson].dist()?L[rson].lx:0);
L[step].rx=L[rson].rx+(L[rson].rx==L[rson].dist()?L[lson].rx:0);
//初始化為最左區間
L[step].mx=L[step].lx;L[step].val=L[step].left;
//左區間的最大間隔
if(L[lson].mx>L[step].mx+1||(L[lson].mx>L[step].mx&&L[step].mx%2==0)){
L[step].mx=L[lson].mx;
L[step].val=L[lson].val;
}
//左區間的右端與右區間左端的並
if(L[lson].rx+L[rson].lx>L[step].mx+1||(L[lson].rx+L[rson].lx>L[step].mx&&L[step].mx%2==0)){
L[step].mx=L[lson].rx+L[rson].lx;
L[step].val=L[lson].right-L[lson].rx+1;
}
//右區間的最大間隔
if(L[rson].mx>L[step].mx+1||(L[rson].mx>L[step].mx&&L[step].mx%2==0)){
L[step].mx=L[rson].mx;
L[step].val=L[rson].val;
}
//右端點
if(L[step].rx>L[step].mx+1||(L[step].rx>L[step].mx&&L[step].mx%2==0)){
L[step].mx=L[step].rx;
L[step].val=L[step].right-L[step].rx+1;
}
}
void update(int step,int p,int k){
if(L[step].left==L[step].right){
//K為1表示停入一輛車
if(k){
L[step].mx=L[step].rx=L[step].lx=0;
L[step].val=N;
}
else{
L[step].mx=L[step].rx=L[step].lx=1;
L[step].val=L[step].left;
}
return ;
}
if(p<=L[step].mid) update(lson,p,k);
else update(rson,p,k);
Push_Up(step);
}
int main(){
int n,q;
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
while(scanf("%d%d",&n,&q)!=EOF){
Bulid(1,1,n);
int cnt=1;
while(q--){
int ope,id;
scanf("%d%d",&ope,&id);
if(ope==2) update(1,pos[id],0);
else{
int len=L[1].mx,val=L[1].val,ret;
//如果最長的區間是連著右端點，需要特殊考慮
if(val+len-1==n){
if(val==1) ret=1;
else ret=n;
}
else{
ret=1; //特殊考慮左端點
int mmax=L[1].lx-1; //如果放在左端點時的間隔
//考慮最長的區間
if((len-1)/2>mmax){
mmax=(len-1)/2;
ret=val+(len-1)/2;
}
//考慮右端點
if(L[1].rx-1>mmax){
mmax=L[1].rx-1;
ret=n;
}
}
printf("%d\n",ret);
pos[id]=ret;
update(1,ret,1);
}
}
}
return 0;
}
