专栏文章

题解：P7477 「C.E.L.U-02」划分可重集

zzxh923
P7477题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miou5y4l
此快照首次捕获于
2025/12/03 01:12
3 个月前
此快照最后确认于
2025/12/03 01:12
3 个月前
查看原文

思路

很难评价这题调出来的时候我的精神状态。
首先这个 kk 明显可以二分，所以直接二分就好。
然后我们可以发现，一个数要么扔到 aa 里，要么扔到 bb 里。既不能都扔进去也不能都不扔进去，所以这两个东西是互斥的，然后就可以用 2-SAT 做了。
我们的限制形如，如果一个数扔到某一个可重集里，那么值在一个区间内的数不能扔到这个集合里，然后受限制这些数的位置都在当前位置以前。
因为有这个位置的限制，所以我们不能使用线段树优化建图，而需要使用主席树优化建图。
首先先离散化一下。
然后这个东西和线段树优化建图其实没有本质区别，但是会遇到一个问题，就是如果有多个相同的数，我连边只会连最后一个，前面的就连不到了。
所以我们需要在离散化的时候把这个数的位置也加进去一块离散化，这样就没有上面提到的问题了。
剩下的就是 2-SAT 板子了。

代码

CPP
#include<bits/stdc++.h>
// #define int long long
#define N 20005
#define M N*20
#define K N*80
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
#define mpi make_pair
using namespace std;
int T=1,n,m,tot,v[N],id[N][2],pos[4][N];
int dfn[K],low[K],stk[K],ts,top,col,d[K];
int rt[4][N],lsh,inf=2e9;
pii a[N];
bool ist[K];
int h[K],e[K<<1],ne[K<<1],idx;
pii f[N];
void adde(int a,int b){
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
struct ds_out{
	struct node{
		int ls,rs,id;
	}tr[M];
	int cnt;
	void add(int &u,int las,int l,int r,int p,int v){
		u=++cnt;
		tr[u]=tr[las];
		tr[u].id=++tot;
		if(l==r){
			adde(v,tr[u].id);
			return;
		}
		int mid=l+r>>1;
		if(p<=mid)add(tr[u].ls,tr[las].ls,l,mid,p,v);
		else add(tr[u].rs,tr[las].rs,mid+1,r,p,v);
		if(tr[u].ls){
			adde(tr[tr[u].ls].id,tr[u].id);
		}
		if(tr[u].rs){
			adde(tr[tr[u].rs].id,tr[u].id);
		}
	}
	void modify(int u,int l,int r,int L,int R,int id){
		if(L>R)return;
		if(!u)return;
		if(l>=L&&r<=R){
			adde(tr[u].id,id);
			return;
		}
		int mid=l+r>>1;
		if(L<=mid)modify(tr[u].ls,l,mid,L,R,id);
		if(R>mid)modify(tr[u].rs,mid+1,r,L,R,id);
	}
}d1,d2;
struct ds_in{
	struct node{
		int ls,rs,id;
	}tr[M];
	int cnt;
	void add(int &u,int las,int l,int r,int p,int v){
		u=++cnt;
		tr[u]=tr[las];
		tr[u].id=++tot;
		if(l==r){
			adde(tr[u].id,v);
			return;
		}
		int mid=l+r>>1;
		if(p<=mid)add(tr[u].ls,tr[las].ls,l,mid,p,v);
		else add(tr[u].rs,tr[las].rs,mid+1,r,p,v);
		if(tr[u].ls){
			adde(tr[u].id,tr[tr[u].ls].id);
		}
		if(tr[u].rs){
			adde(tr[u].id,tr[tr[u].rs].id);
		}
	}
	void modify(int u,int l,int r,int L,int R,int id){
		if(L>R)return;
		if(!u)return;
		if(l>=L&&r<=R){
			adde(id,tr[u].id);
			return;
		}
		int mid=l+r>>1;
		if(L<=mid)modify(tr[u].ls,l,mid,L,R,id);
		if(R>mid)modify(tr[u].rs,mid+1,r,L,R,id);
	}
}d3,d4;
void tar(int u){
	dfn[u]=low[u]=++ts;
	stk[++top]=u;
	ist[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tar(j);
			low[u]=min(low[u],low[j]);
		}
		else if(ist[j])low[u]=min(low[u],dfn[j]);
	}
	if(low[u]>=dfn[u]){
		int y;
		col++;
		do{
			y=stk[top--];
			ist[y]=0;
			d[y]=col;
		}while(y!=u);
	}
}
void init(){
	for(int i=0;i<=tot;i++){
		dfn[i]=low[i]=0;
		ist[i]=0;
		d[i]=0;
		h[i]=-1;
	}
	d1.cnt=0;d2.cnt=0;
	d3.cnt=0;d4.cnt=0;
	for(int i=1;i<=n;i++){
		rt[0][i]=rt[1][i]=0;
		rt[2][i]=rt[3][i]=0;
	}
	col=top=ts=idx=0;
	tot=n*2;
}
bool check(int k){
	init();
	for(int i=1;i<=m;i++){
		int x=f[i].x,y=f[i].y;
		adde(id[x][0],id[y][1]);
		adde(id[y][0],id[x][1]);
		adde(id[x][1],id[y][0]);
		adde(id[y][1],id[x][0]);
	}
	int lim=lsh;
	for(int i=1;i<=n;i++){
		auto it=upper_bound(a+1,a+lsh+1,mpi(v[i],i))-a-1;
		d1.add(rt[0][i],rt[0][i-1],1,lim,it,id[i][0]);
		d2.add(rt[1][i],rt[1][i-1],1,lim,it,id[i][1]);
		d3.add(rt[2][i],rt[2][i-1],1,lim,it,id[i][0]);
		d4.add(rt[3][i],rt[3][i-1],1,lim,it,id[i][1]);
	}
	for(int i=2;i<=n;i++){
		{
			tot++;
			auto it=upper_bound(a+1,a+lsh+1,mpi(v[i],i))-a-1;
			auto it1=lower_bound(a+1,a+lsh+1,mpi(v[i]-k,inf))-a-1;
			d1.modify(rt[0][i],1,lim,it,it,tot);
			d4.modify(rt[3][i-1],1,lim,1,it1,tot);
			tot++;
			d1.modify(rt[0][i-1],1,lim,1,it1,tot);
			d4.modify(rt[3][i],1,lim,it,it,tot);
		}
		{
			tot++;
			auto it=upper_bound(a+1,a+lsh+1,mpi(v[i],i))-a-1;
			auto it1=lower_bound(a+1,a+lsh+1,mpi(v[i]+k,0))-a;
			d2.modify(rt[1][i],1,lim,it,it,tot);
			d3.modify(rt[2][i-1],1,lim,it1,lim,tot);
			tot++;
			d2.modify(rt[1][i-1],1,lim,it1,lim,tot);
			d3.modify(rt[2][i],1,lim,it,it,tot);
		}
	}
	for(int i=1;i<=n*2;i++){
		if(!dfn[i]){
			tar(i);
		}
	}
	for(int i=1;i<=n;i++){
		if(d[id[i][0]]==d[id[i][1]]){
			return 0;
		}
	}
	return 1;
}
void solve(int cs){
    if(!cs)return;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v[i];
		a[i]={v[i],i};
	}
	sort(a+1,a+n+1);
	lsh=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=m;i++){
		cin>>f[i].x>>f[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<2;j++){
			id[i][j]=++tot;
		}
	}
	int l=0,r=1e9,res=-1;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			r=mid-1;
			res=mid;
		}
		else l=mid+1;
	}
	cout<<res<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	for(int cs=1;cs<=T;cs++){
		solve(cs);
	}
	return 0;
}

评论

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

正在加载评论...