E.S 老师的礼物

题解

None 的判断

首先将所有 与 连边，若连边后存在环或图的状态与 冲突则答案不存在。

否则，我们首先判断图的连通性。

将图上的点按 到 的顺序在数轴上一字排开，发现两个联通块能够合并，当且仅当两个联通块对应的区间有交。

证明: 令左侧联通块对应区间为 ，右侧联通块对应区间为 ，如果没有交（即 ），则右边的联通块均有 ，左边的联通块均有 ，不符合条件；如果有交，则可选取满足 且 的点对 并连接。

据此我们可以尝试将最右侧的联通块依次往左合并。具体地，我们从 到 维护指针 ，同时记录使得 最小的位置 ，若 指向其他联通块则连接 （联通块最右侧的点一定满足 ），若途中指针已离开联通块边界则答案不存在。

Unique 的判断

定义初始联通块为将所有 与 连边后形成的联通块，若整个图联通，则当且仅当总边数为初始联通块个数减 时答案唯一。

注意到两个点 能够连接，当且仅当 来自不同初始联通块且 。

对于限制 ，我们可以离线后用树状数组处理：在每个队列 中存储数 ，之后将所有 和 从大到小扫一遍，在扫到 时将 加 ，对于每次询问，查询 对应的前缀和。

对于联通块的限制，我们可以统计出整个图的连边数，再减去每个联通块对应的连边数。

时间复杂度 。注意常数。

代码

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

#define N 500005

int i,j,k,n,m,t,a[N+50],mn[N+50];

vector<pair<int,int> > res;

void show(){
	sort(res.begin(),res.end());
	cout<<"Unique\n"; for(auto [i,j]:res)cout<<i<<' '<<j<<'\n';
}

int fa[N+50],l[N+50],sz[N+50],f[N+50];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
void add(int x,int y){for(;x<=n;x+=(-x&x)){f[x]+=y;}}
int get(int x,int y=0){for(;x;x-=(-x&x)){y+=f[x];}return y;}

basic_string<int> q[N+50],cl[N+50];

int solve2(int m){
	int i,j,k; ll tot=0;
	for(i=1;i<=n;i++){
		q[a[i]]+=i;
		cl[find(i)]+=i;
	}
	for(i=n;i>=1;i--){
		add(a[i],1);
		for(auto j:q[i]){
			tot+=get(j);
		}
	}
	for(i=1;i<=n;i++)basic_string<int>().swap(q[i]);
	memset(f,0,n*4+50);
	for(i=1;i<=n;i++){
		if(cl[i].empty())continue;
		basic_string<int> s;
		for(auto j:cl[i]){
			q[a[j]]+=j;
			s+=j; s+=a[j];
		}
		sort(s.begin(),s.end());
		s.erase(unique(s.begin(),s.end()),s.end());
		reverse(s.begin(),s.end());
		for(auto j:s){
			if(find(j)==i)add(a[j],1);
			for(auto k:q[j]){
				tot-=get(k);
			}
		}
		for(auto j:cl[i]){
			add(a[j],-1);
			basic_string<int>().swap(q[a[j]]);
		}
	}
	tot/=2;
	for(i=1;i<=n;i++){
		basic_string<int>().swap(cl[i]);
	}
	return tot>m;
}

int solve(){
	int i,j,k,fk=0,it=n;
	res={};
	unordered_map<ll,int> mp;
	for(i=1;i<=n;i++){
		fa[i]=i; mn[i]=n+1; l[i]=i; sz[i]=1;
	}
	for(i=1;i<=n;i++){
		int x=i,y=a[i];
		if(x==y)return 0;
		j=i; k=a[i]; if(j>k)swap(j,k);
		mn[x]=min(mn[x],y); mn[y]=min(mn[y],x);
		x=find(x); y=find(y);
		if(x!=y){
			fa[y]=x; l[x]=min(l[x],l[y]); sz[x]+=sz[y]; it--;
		}
		else{
			if(!mp.count(1ll*N*j+k))return 0;
		}
		mp[1ll*N*j+k]=1;
	}
	for(i=1;i<=n;i++)if(mn[i]!=a[i])return 0;
	fk=solve2(it-1);
	int id=n; i=n;
	while(sz[find(n)]!=n){
		k=find(n);
		if(sz[k]==n-l[k]+1)return 0;
		for(;i>=1;i--){
			if(find(i)==find(n)){
				if(a[i]<a[id])id=i;
			}
			else{
				int x=id,y=i;
				j=x; k=y; if(j>k)swap(j,k);
				x=find(x); y=find(y);
				fa[y]=x; l[x]=min(l[x],l[y]); sz[x]+=sz[y];
				if(a[i]<a[id])id=i;
				mp[1ll*N*j+k]=1;
				break;
			}
		}
	}
	if(fk)return 2;
	for(auto [w,i]:mp)res.push_back({w/N,w%N});
	return 1;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		for(i=1;i<=n;i++)cin>>a[i];
		int ty=solve();
		if(ty==1)show();
		else if(ty==0)cout<<"None\n";
		else cout<<"Many\n";
	}
}