专题题解 - 积木游戏

$O(n\log n)$ 题解。

加入一个横坐标范围 $[x,y]$，高度为 $h$ 的矩形 $R$ 后形成的新的洞的轮廓上至少要有一条 $R$ 的边，事实上只有如下五种情况：

1. 洞的轮廓只包含 $R$ 的下边；
2. 洞的轮廓只包含 $R$ 的左边；
3. 洞的轮廓只包含 $R$ 的右边；
4. 洞的轮廓同时包含 $R$ 的左边和下边；
5. 洞的轮廓同时包含 $R$ 的右边和下边。

这是因为轮廓显然不可能包含 $R$ 的上边（否则 $R$ 正上方还有别的矩形），也不可能同时包含 $R$ 的左边和右边（否则 $R$ 浮空）。

下面分别讨论这些情况。

1. 洞的轮廓只包含 $R$ 的下边：

   其一般情况如下图，一个洞 ① 从上面被 $R$ 堵住，两边也各被堵住。

   我们求出 $R$ 的横坐标范围 $[x,y]$ 的区间最大值的同时，也求出有多少段由区间最大值组成的连续段，那么两个连续段之间的部分就是一个这样的洞，而连续段数量容易在线段树上顺便维护。

   

2. 洞的轮廓只包含 $R$ 的左边（右边）：

   其一般情况如下图，一个洞从右边被 $R$ 堵住，上下也各被堵住。

   我们称上下被堵住，左右有一边被堵住的结构叫做“半洞”，我们发现只要考虑横坐标 $x-1$ 处的半洞即可。

   具体地，用 set 维护每个横坐标处的半洞（这个洞在对应横坐标处的上下边界），加入 $R$ 后只会在 $x,y$ 处各增加至多一个半洞（即原本的上边界到 $R$ 的下边界之间的空洞），要查询包含 $R$ 左边（右边）的新洞时只需要在 $x-1$（$y+1$）的 set 中找到 $R$ 这一段纵坐标上的半洞数量即可。

   （利用单调性，用 queue 或 vector 也可）

   

3. 洞的轮廓同时包含 $R$ 的左边（右边）和下边：

   这只是边界情况，处理 2 中的半洞和 1 中的最大值连续段的时候进行一些特判即可。

时间复杂度为 $O(n\log n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010,RANGE=100002;
struct State {
	int mx,seg,sl,sr;
	State (int a=0,int b=0,int c=0,int d=0) {mx=a,seg=b,sl=c,sr=d;}
}s[MAXN<<2];
int n,x,y,z,tg[MAXN<<2];
set < pair<int,int> > st[MAXN];
State merge (State a,State b) {
	State c;
	c.mx=max(a.mx,b.mx);
	if (a.mx>b.mx) {c.sl=a.sl,c.sr=0,c.seg=a.seg;}
	else if (b.mx>a.mx) {c.sl=0,c.sr=b.sr,c.seg=b.seg;}
	else {c.sl=a.sl,c.sr=b.sr,c.seg=a.seg+b.seg-min(a.sr,b.sl);}
	return c;
}
void pd (int p) {
	if (tg[p]==-1) {return;}
	tg[p<<1]=tg[(p<<1)|1]=tg[p];
	s[p<<1]=s[(p<<1)|1]=State(tg[p],1,1,1);
	tg[p]=-1;
	return;
}
void buildt (int p,int l,int r) {
	tg[p]=-1;
	if (l==r) {s[p]=State(0,1,1,1);return;}
	int mid=(l+r)>>1;
	buildt(p<<1,l,mid);
	buildt((p<<1)|1,mid+1,r);
	s[p]=merge(s[p<<1],s[(p<<1)|1]);
	return;
}
State query (int p,int l,int r,int xl,int xr) {
	if (xl<=l&&r<=xr) {return s[p];}
	pd(p);
	int mid=(l+r)>>1;
	if (xr<=mid) {return query(p<<1,l,mid,xl,xr);}
	else if (xl>mid) {return query((p<<1)|1,mid+1,r,xl,xr);}
	else {return merge(query(p<<1,l,mid,xl,xr),query((p<<1)|1,mid+1,r,xl,xr));}
}
void modify (int p,int l,int r,int xl,int xr,int v) {
	if (xr<l||r<xl) {return;}
	if (xl<=l&&r<=xr) {
		tg[p]=v;
		s[p]=State(v,1,1,1);
		return;
	}
	pd(p);
	int mid=(l+r)>>1;
	modify(p<<1,l,mid,xl,xr,v);
	modify((p<<1)|1,mid+1,r,xl,xr,v);
	s[p]=merge(s[p<<1],s[(p<<1)|1]);
	return;
}
int main () {
	buildt(1,1,RANGE);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d%d%d",&x,&y,&z);
		int ans=0;x+=2,y++;
		State nw=query(1,1,RANGE,x,y);
		ans=nw.seg-1;
		int tmp=query(1,1,RANGE,x,x).mx,tmp1=query(1,1,RANGE,x-1,x-1).mx,flg=0;
		set < pair<int,int> >::iterator it=st[x-1].lower_bound(make_pair(nw.mx,1e9));
		while (it!=st[x-1].end()&&(*it).first<=nw.mx+z) {
			ans++;
			if ((*it).second<=nw.mx) {flg=1;}
			st[x-1].erase(it);
			it=st[x-1].lower_bound(make_pair(nw.mx,1e9));
		}
		if (it!=st[x-1].end()&&(*it).second<=nw.mx) {flg=1;}
		if (flg==0&&tmp1>=nw.mx&&nw.sl==0) {ans++;}
		if (nw.sl==0) {st[x].insert(make_pair(nw.mx,tmp+1));}
		tmp=query(1,1,RANGE,y,y).mx,tmp1=query(1,1,RANGE,y+1,y+1).mx,flg=0;
		it=st[y+1].lower_bound(make_pair(nw.mx,1e9));
		while (it!=st[y+1].end()&&(*it).first<=nw.mx+z) {
			ans++;
			if ((*it).second<=nw.mx) {flg=1;}
			st[y+1].erase(it);
			it=st[y+1].lower_bound(make_pair(nw.mx,1e9));
		}
		if (it!=st[y+1].end()&&(*it).second<=nw.mx) {flg=1;}
		if (flg==0&&tmp1>=nw.mx&&nw.sr==0) {ans++;}
		if (nw.sr==0) {st[y].insert(make_pair(nw.mx,tmp+1));}
		modify(1,1,RANGE,x,y,nw.mx+z);
		printf("%d\n",ans);
	}
	return 0;
}