「2015四校联考-巴蜀中学」阿Q的停车场 - 线段树

题目大意

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

---

题目分析

题目简单的来说就是：带修改的找最多的编号最小的空位。
问题具有结合性，显然可以使用线段树维护。

我们用线段树维护以下属性：

• $lmax$（从左端点延伸的最长的空段）
• $rmax$（从右端点延伸的最长的空段）
• $max$（区间内最大的空段大小）
• $maxl$（区间内最大的空段的最小编号）

这和之前做的线段树维护最长子段和很像，标记更新/合并也很像，具体的可以看代码。

然后修改的时候向上合并即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=200005;
struct Tree {
	int left,right;
	int lmax,rmax,max,maxl;
	Tree(int l=0,int r=0,int lm=0,int rm=0,int m=0,int ml=0):left(l),right(r),lmax(lm),rmax(rm),max(m),maxl(ml) {}
};
int n,m,Hash[5*maxn];
int Length(int x) {
	if(!x)return 0;
	return (x-1)/2+1;
}
struct Segment_Tree {
	Tree tree[maxn*4];
	#define ls index<<1
	#define rs index<<1|1
	void build(int index,int Left,int Right) {
		tree[index]=Tree(Left,Right,Right-Left+1,Right-Left+1,Right-Left+1,Left);
		if(Left==Right)return;
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
	}
	void update(int index,int len,int pos) {
		if(!len)return;
		int last=Length(tree[index].max),Now=Length(len);
		if(last<Now)tree[index].max=len,tree[index].maxl=pos;
		else if(last==Now&&pos<tree[index].maxl)tree[index].maxl=pos;
	}
	void push_up(int index) {
		tree[index].lmax=tree[ls].lmax;
		if(tree[ls].lmax==tree[ls].right-tree[ls].left+1)tree[index].lmax+=tree[rs].lmax;
		tree[index].rmax=tree[rs].rmax;
		if(tree[rs].rmax==tree[rs].right-tree[rs].left+1)tree[index].rmax+=tree[ls].rmax;
		tree[index].maxl=0,tree[index].max=0;
		update(index,tree[ls].rmax+tree[rs].lmax,tree[ls].right-tree[ls].rmax+1);
		update(index,tree[ls].max,tree[ls].maxl);
		update(index,tree[rs].max,tree[rs].maxl);
	}
	void modify(int index,int target,int v) {
		if(tree[index].left>target||tree[index].right<target)return;
		if(tree[index].left==tree[index].right) {
			tree[index].lmax=tree[index].rmax=tree[index].max=v;
			if(v)tree[index].maxl=tree[index].left;
			else tree[index].maxl=0;
			return;
		}
		modify(ls,target,v);
		modify(rs,target,v);
		push_up(index);
	}
	int query() {
		int len=(tree[1].max-1)/2+1,ret=(tree[1].maxl*2+tree[1].max-1)/2;
		if(tree[1].lmax>=len)return 1;
		else if(tree[1].rmax>len)return n;
		return ret;
	}
} st;
int main() {
	n=Get_Int();
	m=Get_Int();
	st.build(1,1,n);
	for(int i=1; i<=m; i++) {
		int opt=Get_Int(),x=Get_Int();
		if(opt==1) {
			int ans=st.query();
			printf("%d\n",ans);
			Hash[x]=ans;
			st.modify(1,ans,0);
		} else {
			st.modify(1,Hash[x],1);
			Hash[x]=0;
		}
	}
	return 0;
}