发布时间: 2017年3月19日 16:00 最后更新: 2017年3月19日 16:01 时间限制: 1000ms 内存限制: 128M
描述喵哈哈村的冒菜店开张了，这里的冒菜特别好吃。
星星同学听闻后，就准备去吃冒菜。
星星同学开着自己才花了几十万买的宝马X5，就开进了冒菜店的停车场。
就在她停车的过程中，她发现一个有趣的现象，喵哈哈村的人们总是喜欢停车停在离别人车最远的地方，具体来说就是停在离所有车的距离最小值最大的位置，如果有多个，他们就喜欢停在编号小的位置上。
现在星星同学有一个疑问了：
这个停车场可以看做是拥有一排的停车位，这些停车位编号为1~n，初始都是空的。
如果有若干个汽车进进出出这停车场，那么这些汽车会停在哪些位置呢？
输入第一行两个整数n,m，表示停车场大小和操作数。 接下来m行，每行两个整数F和x。 F是1表示编号为x的车进停车场。 F是2表示编号为x的车出停车场。 保证操作合法。 满足n,m<=200000，x<=1000000
输出对于所有操作1，输出一个整数，表示该车车位的编号。
样例输入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 1 7 4 2 7 4 1 3 查看隐藏信息 选择语言 C (GCC 4.8) C++ (G++ 4.3) Java (Oracle JDK 1.7) 题解：http://www.cnblogs.com/qscqesze/p/6580390.html #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; #define maxn 5000005 #define Mod 1000000007 int b[maxn],n,m; struct node { int l,r,mid,ans; }a[maxn]; void merge(int id) { if(a[id*2].l>0) a[id].l=a[id*2].l; else a[id].l=a[id*2+1].l; if(a[id*2+1].r>0) a[id].r=a[id*2+1].r; else a[id].r=a[id*2].r; a[id].mid=a[id*2].mid; a[id].ans=a[id*2].ans; if(a[id*2+1].l>0 && a[id*2].r>0) { int tmp=(a[id*2+1].l-a[id*2].r)/2; if(tmp>a[id].mid) { a[id].mid=tmp; a[id].ans=(a[id*2+1].l+a[id*2].r)/2; } if(a[id*2+1].mid>a[id].mid) { a[id].mid=a[id*2+1].mid; a[id].ans=a[id*2+1].ans; } } } void work(int id,int l,int r,int num,int mark) { if(l==r) { if(mark==1) { a[id].l=l; a[id].r=r; a[id].mid=a[id].ans=0; } else { a[id].l=a[id].r=0; a[id].mid=a[id].ans=0; } return; } int mid=(l+r)/2; if(num<=mid) work(id*2,l,mid,num,mark); else work(id*2+1,mid+1,r,num,mark); merge(id); } int main(void) { int i,x,y,sum; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(x==1) { if(a[1].l==0) b[y]=1; else { sum=-1000000001; if(a[1].l-1>sum) { b[y]=1; sum=a[1].l-1; } if(a[1].mid>sum) { b[y]=a[1].ans; sum=a[1].mid; } if(n-a[1].r>sum) { b[y]=n; sum=n-a[1].r; } } printf("%d\n",b[y]); work(1,1,n,b[y],1); } else work(1,1,n,b[y],2); } return 0; }