题解：P11024 [COTS 2020] 定序 Redoslijed

来一个非乱搞的并查集做法。

首先还是考虑倒着维护所有操作，那么相当于每次选择一段所有颜色都相同的区间，然后删除这个区间内的所有元素，直到所有区间都被操作为止。

接下来按左端点从大到小的顺序考虑所有区间，此时相当于依次将元素

c_N

到

c_1

塞进数组开头，然后判断每一个区间是否合法，那么对每个区间

(l,r,c)

一共有两种可能：

区间内的所有元素颜色相同：此时直接删除即可。
区间内存在不同颜色的元素：此时考虑接下来操作的区间对这个区间的影响，因为我们是按左端点从大到小的顺序枚举的区间，因此接下来的区间一定只会影响当前区间的一段前缀，那么如果我们已经确定当前区间 $(l,r,c)$ 内最靠右的不合法元素的位置 $p$ ，则当且仅当删除该位置后当前区间才变得合法。

将塞入元素的过程视作压栈，那么删除元素的操作相当于弹出栈中所有位置不大于

r

的元素；而对于需要删除的位置

p

，我们可以为每个

p

开一个桶，在删除该元素时顺便处理对应区间的操作。

接下来考虑如何找到位置

p

。我们需要对每个区间

(l,r,c)

快速查询三个位置：

$r$ 之前第一个没有被删除的元素的位置 $i$ 。如果该位置颜色不为 $c$ 则该位置为 $p$ 。
与 $i$ 颜色相同的极长连续段的左端点 $j$ 。
$j$ 之前第一个没有被删除的元素的位置 $k$ 。如果该位置位于 $l$ 左侧则说明区间合法，否则该位置为 $p$ 。

其中的

i

和

k

可以用并查集轻松维护，而极长连续段可以在每次新加入元素时判断：对于栈顶元素

x

和新加入的元素

y

，如果两者颜色相同则将两者对应的联通块合并。

左端点的顺序可以直接桶排，因此时间复杂度由并查集决定，此处为同时使用路径压缩和启发式合并的

O(N\alpha(N))

。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=500000;

int i,j,k,n,m,t,a[N+50],p[N+50];
int qr[N+50],cl[N+50];

int it0,s[N+50],cur;
basic_string<int> v[N+50],ev[N+50];
int it3,op[N+50];

struct FA{
	int sz[N+50],fa[N+50],pos[N+50];
	inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	inline int find2(int x){return pos[find(x)];}
	void hb(int x,int y){
		x=find(x); y=find(y);
		if(x==y)return;
		if(sz[x]<sz[y])swap(x,y);
		sz[x]+=sz[y]; fa[y]=x; pos[x]=min(pos[x],pos[y]);
	}
}fa,fa2;


void del(int id){
	static int q[N+50],L,R;
	q[L=R=1]=id;
	while(L<=R){
		id=q[L++];
		op[++it3]=id;
		while(it0&&s[it0]<=qr[id]){
			int k=s[it0--];
			fa.hb(k,cur);
			if(!cur||a[k]==a[cur])fa2.hb(k,cur);
			for(auto j:ev[k])q[++R]=j;
		}
	}
}

void get(int l,int id){
	const int r=qr[id],c=cl[id];
	int i=fa.find2(r);
	if(i<l){
		del(id); return;
	}
	if(a[i]!=c){
		ev[i]+=id; return;
	}
	i=fa.find2(fa2.find2(i)-1);
	if(i<l)del(id);
	else ev[i]+=id;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(i=1;i<=m;i++){
		cin>>j>>k>>t; v[j]+=i;
		p[j]++; p[k+1]--; qr[i]=k; cl[i]=t;
	}
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)if(a[i]){
		fa.pos[i]=fa.fa[i]=i; fa.sz[i]=1;
	}
	k=0;
	for(i=1;i<=n;i++)if(a[i]){
		if(a[k]!=a[i]){
			fa2.pos[i]=i; k=i;
		}
		fa2.fa[i]=k; fa2.sz[k]++;
	}
	for(i=1;i<=n;i++){
		p[i]+=p[i-1];
		if((!p[i])!=(!a[i])){cout<<"NE"; return 0;}
	}
	for(i=n;i>=1;i--){
		if(!a[i]){
			if(it0){cout<<"NE"; return 0;}
			continue;
		}
		cur=fa.find(i-1);
		if(it0&&a[s[it0]]==a[i]){
			fa2.hb(s[it0],i);
		}
		s[++it0]=i;
		for(auto j:v[i])get(i,j);
	}
	if(it3!=m){cout<<"NE"; return 0;}
	cout<<"DA\n";
	for(i=it3;i>=1;i--)cout<<op[i]<<' ';
}

题解：P11024 [COTS 2020] 定序 Redoslijed

文章操作

相关推荐

评论

题解：P11024 [COTS 2020] 定序 Redoslijed