题解：AT_dwango2015_prelims_5 電波局

题目大意：给出一个边长为

n

的正三角形平面，初始有

m

次覆盖操作，每次覆盖一个正三角形区域内的点，然后有

q

次查询操作，每次查询一个正三角形区域内未被覆盖的点数。

首先将下标对齐后将正三角形变为等腰直角三角形。

求一个三角形未覆盖的点数，可以转变为先求出初始下被覆盖的总点数，然后将查询的三角形当成一次覆盖，再求出被覆盖的总点数，两次答案相减即为所求。

那么先考虑如果求初始的答案，再进行

q

次即可回答所有询问。

难点在于对重合部分的处理，那么我们希望对每个覆盖操作进行一些删减，使得每个点恰好被覆盖一次，并且覆盖的总面积是好计算的。

考虑对行从大到小进行扫描线，按照三角形的底边（即

a_i+c_i-1

）从大到小加入每个三角形。

那么加入一个三角形

i

时，如果存在三角形

j

满足

a_i-b_i\le a_j-b_j

，那么我们可以删减三角形

j

的行

\le a_i+c_i-1

的部分，因为这些部分都被

i

覆盖了。

否则我们可以删减三角形

i

的列

\ge b_j

的部分，因为这些部分都被

j

覆盖了。

考虑扫描线时用链表维护三角形

s_1,s_2,\cdots s_k

满足

b_{s_i}\lt b_{s_{i+1}},a_{s_i}-b_{s_i}\gt a_{s_{i+1}}-b_{s_{i+1}}

。

那么每次加入新的三角形

i

时，找到对应的前驱后继，如果前驱包含

i

就直接跳过。

否则对前驱进行一次删减，然后考虑后继，如果被

i

包含就对后继进行删减，并且后继已经没有扫描线上方的部分了，将后继移除链表，接着考虑下一个后继，直到后继不被包含，对

i

进行删减。

注意到每个三角形只会被移除链表

1

次，所以对后继的删减次数是

O(m)

的，同时加入一个三角形最多只会对本身和前驱进行删减，因此总共的删减次数是

O(m)

的。

在每次对三角形删减时，统计上一次删减到这一次删减之间的行区域的面积，简单分讨后可以

O(1)

计算。

时间复杂度

O(m^2)

，瓶颈在于找前驱后继，用数据结构维护可以做到

O(m\log m)

，总复杂度

O(qm\log m)

。

注意到询问时只会新加入一个三角形，我们却要对所有三角形重新求一遍前驱后继，是没有必要的。

首先因为是用链表维护，我们只要找到前驱即可。

考虑求出初始状态每个三角形的前驱，加入新的三角形后，我们暴力求出新加入的三角形的前驱。

而对于原先就有的三角形，前驱只有可能是原先的前驱或者是新加入的三角形，这是容易判断的。

这样我们就做到了

O(m^2)

预处理，

O(m)

回答询问。

总时间复杂度

O(m(m+q))

。

参考代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
typedef long long ll;
int n,m,q,pr[N],nx[N],l[N],r[N],d[N],Pr[N];
bool dl[N],fg;
struct node{
	int x,y,z;
	bool operator <(const node a)const{return x+z>a.x+a.z;}
}a[N];
ll Ans,ans;
bool cmp(int u,int v){
	return a[u].x-a[u].y<=a[v].x-a[v].y;
}
void calc(int i,int nw){
	int lv=a[i].x,rv=a[i].x+r[i]-l[i];
	if(rv<=nw)ans+=1ll*(d[i]-nw)*(r[i]-l[i]+1);
	else if(lv<=nw){
		r[i]=min(r[i],l[i]+d[i]-a[i].x);
		rv=a[i].x+r[i]-l[i];
		ans+=1ll*(d[i]-nw)*(r[i]-l[i]+1)-1ll*(rv-nw)*(rv-nw-1)/2;
	}else if(lv<=d[i]){
		if(rv<=d[i])ans+=1ll*(d[i]-lv+1+d[i]-rv+1)*(r[i]-l[i]+1)/2;
		else ans+=1ll*(d[i]-lv+1)*(d[i]-lv+2)/2;
	}
	d[i]=nw;
}
void work(int i,int u,int v){
	int nw=a[i].x+a[i].z-1;
	if(u&&cmp(u,i))return dl[i]=true,void();
	while(v<m+2&&cmp(i,v)){
		calc(v,nw);
		dl[v]=true,v=nx[v];
	}
	if(u&&a[i].y-1<r[u]){
		calc(u,nw);
		r[u]=a[i].y-1;
	}
	d[i]=nw;
	pr[i]=u,nx[i]=v;
	nx[pr[i]]=pr[nx[i]]=i;
	l[i]=a[i].y,r[i]=a[i].y+a[i].z-1;
	if(v<m+2)r[i]=min(r[i],a[v].y-1);
}
void ins(int i){
	int v=m+2;
	while(pr[v]&&a[pr[v]].y>=a[i].y)v=pr[v];
	int u=Pr[i]=pr[v];
	work(i,u,v);
}
void Ins(int i){
	int u,v;
	if(i==m+1){
		v=m+2;
		while(v&&a[pr[v]].y>=a[i].y)v=pr[v];
		u=pr[v];
	}else{
		u=Pr[i];
		if(dl[u]||fg&&nx[u]==m+1&&a[m+1].y<a[i].y)u=m+1;
		v=nx[u];
	}
	work(i,u,v);
}
void init(){
	nx[0]=m+2,pr[m+2]=0;
	for(int i=1;i<=m;++i)ins(i);
	for(int i=pr[m+2];i;i=pr[i])calc(i,0);
	Ans=ans;
}
void solve(){
	ans=0;
	nx[0]=m+2,pr[m+2]=0;
	for(int i=1;i<=m;++i)dl[i]=false;
	fg=false;
	for(int i=1;i<=m;++i){
		if(!fg&&a[m+1]<a[i])Ins(m+1),fg=true;
		Ins(i);
	}
	if(!fg)Ins(m+1);
	for(int i=pr[m+2];i;i=pr[i])calc(i,0);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	sort(a+1,a+m+1);
	init();
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&a[m+1].x,&a[m+1].y,&a[m+1].z);
		solve();
		printf("%lld\n",ans-Ans);
	}
	return 0;
}

题解：AT_dwango2015_prelims_5 電波局

文章操作

相关推荐

评论

题解：AT_dwango2015_prelims_5 電波局