P9757 [COCI2022-2023#3] Dirigent 题解

分析

对于一个从小到大（按编号排序）的长度为 \(n\) 的序列 \(A\)，有性质：相邻两个数之差的绝对值为 \(1\) 的数量为 \(n-1\)。

那么，对于这道题，能使环剪开一条边使其按编号排序，必有相邻两个 \(i,j\)，满足 \((A_i-A_j=1)\) 的数量为 \(n-1\)。注意，因为这是个环，所以 \(i,j\) 大小关系不能确定。

记录一个 \(cnt\) 表示满足关系的数量，每次交换 \(x,y\) 的时候将原本 \(x,y\) 的贡献删掉，再将与 \(x,y\) 相邻的数的贡献删掉；增加同理。最后判断一下 \(cnt\) 是否等于 \(n-1\) 即可。

注：与 \(x,y\) 相邻的数可能有 \(y,x\) 两个，需要先判断一下。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int N=3e5+10;
int n,q,a[N];
int X[N],cnt;

il void add(int x){
	if(a[(x-1)==0?n:(x-1)]==a[x]-1) ++cnt;
	return ;
}
il void del(int x){
	if(a[(x-1)==0?n:(x-1)]==a[x]-1) --cnt;
	return ;
}

il void solve(){
	cin>>n>>q;
	for(re int i=1;i<=n;++i) cin>>a[i],X[a[i]]=i;
	for(re int i=1;i<=n;++i) add(a[i]);
	for(re int i=1;i<=q;++i){
		int x,y;cin>>x>>y;
		del(X[x]),del(X[y]);
		if(((X[x]+1)==n+1?1:(X[x]+1))!=X[y]) del((X[x]+1)==n+1?1:(X[x]+1));
		if(((X[y]+1)==n+1?1:(X[y]+1))!=X[x]) del((X[y]+1)==n+1?1:(X[y]+1));
		swap(a[X[x]],a[X[y]]),swap(X[x],X[y]);
		add(X[x]),add(X[y]);
		if(((X[x]+1)==n+1?1:(X[x]+1))!=X[y]) add((X[x]+1)==n+1?1:(X[x]+1));
		if(((X[y]+1)==n+1?1:(X[y]+1))!=X[x]) add((X[y]+1)==n+1?1:(X[y]+1));	
		if(cnt==n-1) cout<<"DA\n";
		else cout<<"NE\n";	
	}
	return ;
}

signed main(){
	solve();
	return 0;
}