专栏文章

题解：P10208 [JOI 2024 Final] 礼物交换 / Gift Exchange

BBig_Bishop
P10208题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min4shr3
此快照首次捕获于
2025/12/01 20:34
3 个月前
此快照最后确认于
2025/12/01 20:34
3 个月前
查看原文
题意可以变为询问区间内有没有二分图完美匹配。
考虑使用霍尔定理。
将这些 Ai,BiA_i,B_i 排序后形如。
BBABBABABBA........BBABBABABBA........
考虑什么样的情况是不合法的。
把所有的 AA 当作左部点。
贪心的想一下。
首先以 AA 结尾的前缀肯定是相比 BB 结尾的更劣。
对于这样的一个前缀，在保证选最右侧的 AA 的时候，最劣的子集情况就是全选所有的 AA ，因为 BB 的个数不会改变。
即 cntB≥cntAcnt_B\ge cnt_A 。
但是 AiA_i 不能连 BiB_i。
推理一下。
只有在 BBABAA...⏞x个A，x个BBA\overbrace{BBABAA...}^{x个A，x个B}BA 的情况下无解。
这对相邻的 ABAB 真是对苦命鸳鸯啊！
考虑一下就是 [Bi,Ai][B_i,A_i] 不和其他区间相交。
维护出每个 ii 左边第一个与其相交的，右边第一个与其相交的，离线下来扫描线即可。
CPP
#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
int read(){
	int p=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') p=(p<<1)+(p<<3)+ch-'0',ch=getchar();
	return p;
}
const int N=5e5+5;
struct seg2{
	int mx[N*4],tag[N*4];
	void pd(int id){
		if(tag[id]==INF) return;
		tag[id<<1]=min(tag[id<<1],tag[id]);
		tag[id<<1|1]=min(tag[id<<1|1],tag[id]);
		mx[id<<1]=min(mx[id<<1],tag[id]);
		mx[id<<1|1]=min(mx[id<<1|1],tag[id]);
		tag[id]=INF; 
	}
	void change(int L,int R,int l,int r,int id,int v){
		if(L<=l&&r<=R){
			mx[id]=v;
			tag[id]=v;
			return;
		}
		pd(id);
		int mid=l+r>>1;
		if(L<=mid) change(L,R,l,mid,id<<1,v);
		if(R>mid) change(L,R,mid+1,r,id<<1|1,v);
		mx[id]=min(mx[id<<1],mx[id<<1|1]); 
	}
	int query(int L,int R,int l,int r,int id){
		if(L<=l&&r<=R) return mx[id];
		pd(id);
		int mid=l+r>>1;
		if(L<=mid&&R>mid) return min(query(L,R,l,mid,id<<1),query(L,R,mid+1,r,id<<1|1));
		else if(L<=mid) return query(L,R,l,mid,id<<1);
		else return query(L,R,mid+1,r,id<<1|1);
	}
}t3;
struct seg{
	int mx[N*8],tag[N*8];
	void pd(int id){
		if(!tag[id]) return;
		tag[id<<1]=max(tag[id<<1],tag[id]);
		tag[id<<1|1]=max(tag[id<<1|1],tag[id]);
		mx[id<<1]=max(mx[id<<1],tag[id]);
		mx[id<<1|1]=max(mx[id<<1|1],tag[id]);
		tag[id]=0; 
	}
	void change(int L,int R,int l,int r,int id,int v){
		if(L<=l&&r<=R){
			mx[id]=v;
			tag[id]=v;
			return;
		}
		pd(id);
		int mid=l+r>>1;
		if(L<=mid) change(L,R,l,mid,id<<1,v);
		if(R>mid) change(L,R,mid+1,r,id<<1|1,v);
		mx[id]=max(mx[id<<1],mx[id<<1|1]); 
	}
	int query(int L,int R,int l,int r,int id){
		if(L<=l&&r<=R) return mx[id];
		pd(id);
		int mid=l+r>>1;
		if(L<=mid&&R>mid) return max(query(L,R,l,mid,id<<1),query(L,R,mid+1,r,id<<1|1));
		else if(L<=mid) return query(L,R,l,mid,id<<1);
		else return query(L,R,mid+1,r,id<<1|1);
	}
}t1,t2;
int a[N],b[N];
int n,m;
int ans[N];
int pl[N],pr[N];
vector<int> v1[N];
vector<pair<int,int> > q[N];
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	for(int i=1;i<=n;i++){
		pl[i]=t1.query(b[i],a[i],1,2*n,1);
		t1.change(b[i],a[i],1,2*n,1,i);
	}
	for(int i=n;i;i--){
		pr[i]=n-t2.query(b[i],a[i],1,2*n,1)+1;
		t2.change(b[i],a[i],1,2*n,1,n-i+1);
	}
	for(int i=0;i<=500000*4;i++) t3.tag[i]=t3.mx[i]=INF;
	for(int i=1;i<=n;i++){
		v1[pr[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) t3.change(i,i,1,n,1,pl[i]);
	m=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		q[y].push_back({x,i});
	}
	for(int i=1;i<=n;i++){
		for(int j:v1[i]){
			t3.change(j,j,1,n,1,INF);
		}
		for(pair<int,int> j:q[i]){
			int o=t3.query(j.first,i,1,n,1);
			if(o>=j.first) ans[j.second]=1;
			else ans[j.second]=0;
		}
	}
	for(int i=1;i<=m;i++) if(ans[i]) puts("Yes");else puts("No");
	return 0;
}

评论

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

正在加载评论...