题解：P14532 [RMI 2018] 颜色 / Colors

先考虑一个正确的操作方式，由于点权是不能变大的，所以把目标点权最大的挑出来，设为

v

，点权比

v

大的点都是无意义的，需要找一个小于等于

v

的最大点权进行覆盖，且只能操作这些点，然后把目标点权为

v

的点删掉，直到全部点都删光为止。发现这样会进行很多无意义赋值，考虑直接跳到

v

等于这个点目标点权的时刻，发现此时

b_i>v

的点已经被删光了，

a_i<v

的点不能操作，所以能操作的点必须满足

b_i\leq v\leq a_i

，能操作的边必须两个端点都满足这个限制，只要在当前点的连通块内有一个点满足

a_i=v

即合法，充要性是显然的。

因此考虑线段树分治，按秩合并并查集，启发式合并 unordered_multiset，注意 erase 函数会将整个 multiset 中所有值为

value

的元素全部删掉，所以要使用 find 找出一个后再 erase。时间复杂度应该是

O(n\log^2n)

的。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=4e5+5;
int flag,a[N],b[N],f[N],h[N],tp=0;
struct node2{int x,y,z;}st[M];
struct node{int x,y;}s[M];
vector<int> e[N<<2],pt[N];
unordered_multiset<int> ex[N];
void add(int u,int l,int r,int x,int y,int z){
	if(x<=l && r<=y){
		e[u].emplace_back(z);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) add(u<<1,l,mid,x,y,z);
	if(mid<y) add(u<<1|1,mid+1,r,x,y,z);
	return;
}
int find(int x){
	if(x==f[x]) return x;
	return find(f[x]);
}
void merge(int x,int y,int u){
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	tp++;
	st[tp].x=u;
	if(h[fx]>h[fy]){
		f[fy]=fx;
		st[tp].y=fy;
		if(ex[fx].size()<ex[fy].size()){
			swap(ex[fx],ex[fy]);
			st[tp].z=1;
		}
		else st[tp].z=0;
		for(auto it:ex[fy]) ex[fx].insert(it);
	}
	else if(h[fx]<h[fy]){
		f[fx]=fy;
		st[tp].y=fx;
		if(ex[fy].size()<ex[fx].size()){
			swap(ex[fx],ex[fy]);
			st[tp].z=1;
		}
		else st[tp].z=0;
		for(auto it:ex[fx]) ex[fy].insert(it);
	}
	else {
		f[fy]=fx;h[fx]++;h[fy]++;
		st[tp].y=fy;
		if(ex[fx].size()<ex[fy].size()){
			swap(ex[fx],ex[fy]);
			st[tp].z=1;
		}
		else st[tp].z=0;
		for(auto it:ex[fy]) ex[fx].insert(it);
	}
	return;
}
void dg(int u,int l,int r){
	for(auto it:e[u]) merge(s[it].x,s[it].y,u);
	if(l==r){
		for(auto it:pt[l]){
			int x=find(it);
			if(ex[x].find(l)==ex[x].end()){
				flag=1;
				break;
			}
		}
	}
	else {
		int mid=l+r>>1;
		dg(u<<1,l,mid);
		dg(u<<1|1,mid+1,r);
	}
	while(tp>0 && st[tp].x==u){
		int x=st[tp].y,z=st[tp].z;
		if(h[x]==h[f[x]]) h[x]--,h[f[x]]--;
		for(auto it:ex[x]) ex[f[x]].erase(ex[f[x]].find(it));
		if(z) swap(ex[x],ex[f[x]]);
		f[x]=x;tp--;
	}
	e[u].clear();
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		int n,m;flag=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++){
			cin>>b[i];
			if(a[i]<b[i]) flag=1;
			pt[b[i]].emplace_back(i);
			f[i]=i,h[i]=1;
			ex[i].insert(a[i]);
		}
		for(int i=1,x,y,l,r;i<=m;i++){
			cin>>x>>y;
			s[i].x=x,s[i].y=y;
			l=max(b[x],b[y]);
			r=min(a[x],a[y]);
			if(l<=r) add(1,1,n,l,r,i);
		}
		dg(1,1,n);
		if(flag==1) cout<<"0\n";
		else cout<<"1\n";
		for(int i=1;i<=n;i++){
			ex[i].clear();
			pt[i].clear();
		}
	}
    return 0;
}

题解：P14532 [RMI 2018] 颜色 / Colors

文章操作

相关推荐

评论

题解：P14532 [RMI 2018] 颜色 / Colors