专栏文章

题解：P9284 [AGM 2023 资格赛] 海盗

__Weslie_
P9284题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min42w40
此快照首次捕获于
2025/12/01 20:14
3 个月前
此快照最后确认于
2025/12/01 20:14
3 个月前
查看原文
大板子。

Solution P9284

考虑沿用 P5490 【模板】扫描线 & 矩形面积并 的思想，原因是询问一定是一条线。
首先把询问离线下来。
横坐标和纵坐标处理方式类似（其实几乎一样），所以这里只介绍横坐标的。
现在有这么一个矩形。
如你所见，这张图上左边还有一条线从左往右扫。
动态维护一颗线段树，维护的是当前红线上每个位置被几个炸弹覆盖。
不难发现这一个横坐标的状态有很多是可以从上一个横坐标转移过来的，但是有两种需要更新：
  • 如果红线扫到矩形的左边界，那么矩形上下边界及之间的部分就会多被炸弹覆盖一次。
  • 如果扫到了右边界紧挨着靠右的位置，则矩形上下边界及之间的部分就不会像之前的位置一样被炸弹覆盖。
对每个横坐标开一个 vector，然后把左右边界放到上面。
由于更改的一定是区间，所以写区间加法线段树。
然后考虑询问：把询问分类，然后标记在当前横坐标上。
判断三种结果的方案如下：
  • MISS：一个炮弹都没打中这些位置，区间被覆盖次数最大值为 00。
  • SUNK：这些位置全都被打中，区间被覆盖次数最小值 >0>0。
  • HIT：这些位置有打中的也有没打中的，区间最大值 >0>0，但是区间最小值 =0=0。
纵坐标类似，就是把红线从左往右变成从下往上。
CodeCPP
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
using namespace std;
const int N=200005;
const int mod=1;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
struct segtree{
	struct node{
		int mn,mx,tag;
	}tr[N<<2];
	void pushup(int now){
		tr[now].mx=max(tr[ls].mx,tr[rs].mx);
		tr[now].mn=min(tr[ls].mn,tr[rs].mn);
		return;
	}
	void build(int l,int r,int now){
		tr[now].tag=0;
		if(l==r){
			tr[now].mn=0;
			tr[now].mx=0;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,ls);
		build(mid+1,r,rs);
		pushup(now);
	}
	void pushdown(int now){
		if(tr[now].tag){
			tr[ls].mn+=tr[now].tag;
			tr[ls].mx+=tr[now].tag;
			tr[rs].mn+=tr[now].tag;
			tr[rs].mx+=tr[now].tag;
			tr[ls].tag+=tr[now].tag;
			tr[rs].tag+=tr[now].tag;
			tr[now].tag=0;
		} 
	}
	void update(int l,int r,int al,int ar,int now,int x){
		if(al<=l&&r<=ar){
			tr[now].mx+=x;
			tr[now].mn+=x;
			tr[now].tag+=x;
			return;
		}
		pushdown(now);
		int mid=(l+r)>>1;
		if(al<=mid)update(l,mid,al,ar,ls,x);
		if(ar>mid)update(mid+1,r,al,ar,rs,x);
		pushup(now);
	}
	int query_min(int l,int r,int al,int ar,int now){
		if(al<=l&&r<=ar)return tr[now].mn;
		pushdown(now);
		int mid=(l+r)>>1,res=0x3f3f3f3f;
		if(al<=mid)res=min(res,query_min(l,mid,al,ar,ls));
		if(ar>mid)res=min(res,query_min(mid+1,r,al,ar,rs));
		return res;
	}
	int query_max(int l,int r,int al,int ar,int now){
		if(al<=l&&r<=ar)return tr[now].mx;
		pushdown(now);
		int mid=(l+r)>>1,res=-0x3f3f3f3f;
		if(al<=mid)res=max(res,query_max(l,mid,al,ar,ls));
		if(ar>mid)res=max(res,query_max(mid+1,r,al,ar,rs));
		return res;
	}
}tr;
#define mp make_pair
vector<pair<pair<int,int>,int> >a1[N],a2[N],a3[N],a4[N];
int n,m,p,q;
int ans[N];
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	fastio;
	cin>>n>>m>>p;
	for(int i=1,lx,rx,ly,ry;i<=p;i++){
		cin>>lx>>ly>>rx>>ry;
		a1[lx].push_back(mp(mp(ly,ry),1));
		a1[rx+1].push_back(mp(mp(ly,ry),-1));
		a2[ly].push_back(mp(mp(lx,rx),1));
		a2[ry+1].push_back(mp(mp(lx,rx),-1));
	}
	cin>>q;
	for(int i=1,opt,l,r,x;i<=q;i++){
		cin>>opt>>x>>l>>r;
		if(opt==1){
			a3[x].push_back(mp(mp(l,r),i));
		}
		else a4[x].push_back(mp(mp(l,r),i));
	}
	for(int i=1;i<=n;i++){
		for(auto o:a1[i]){
			tr.update(1,n,o.fi.fi,o.fi.se,1,o.se);
		}
		for(auto o:a3[i]){
			int mn=tr.query_min(1,n,o.fi.fi,o.fi.se,1),mx=tr.query_max(1,n,o.fi.fi,o.fi.se,1);
			if(mx==0)ans[o.se]=0;
			else if(mn==0)ans[o.se]=1;
			else ans[o.se]=2;
		}
	}
	tr.build(1,n,1);
	for(int i=1;i<=m;i++){
		for(auto o:a2[i]){
			tr.update(1,n,o.fi.fi,o.fi.se,1,o.se);
		}
		for(auto o:a4[i]){
			int mn=tr.query_min(1,n,o.fi.fi,o.fi.se,1),mx=tr.query_max(1,n,o.fi.fi,o.fi.se,1);
			if(mx==0)ans[o.se]=0;
			else if(mn==0)ans[o.se]=1;
			else ans[o.se]=2;
		}
	}
	for(int i=1;i<=q;i++){
		if(ans[i]==0)cout<<"MISS\n";
		else if(ans[i]==1)cout<<"HIT\n";
		else cout<<"SUNK\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...