题目

前言

做模拟赛做到的，手模一堆小样例模出来的。

思路

首先我们要知道一个结论：把一个排列通过交换相邻元素来得到恒等排序的最小交换次数等于这个排列的逆序对个数。

接着，我们要知道一个重要结论：$\text{inv}(p) \ge \sum_{i=1}^N \frac{|p_i-i|}{2}$。

::::info[证明] 定义 $h(p)=|p_i-i|$，我们要观察一次相邻交换对 $h(p)$ 的影响。

假设我们交换相邻的两个元素 $p_k$ 和 $p_{k+1}$，交换前两项 $|p_i-i|$ 的和为：

交换后两项 $|p_i-i|$ 的和为：

计算 $|B-A|$ 的取值范围。

• $|p_k-(k+1)|$ 与 $|p_k-k|$ 的差绝对值最大为 1。
• $|p_{k+1}-k|$ 与 $|p_{k+1}-(k+1)|$ 的差绝对值最大为 1。

所以 $B-A$ 的取值范围只能是 $\{-2,0,2\}$。

• 每进行一次相邻交换，$\text{inv}(p)$ 改变 1。
• 每进行一次相邻交换，$h(p)$ 最多改变 2。

当我们通过 $\text{inv}(p)$ 次交换将排列变为恒等排列时：

• 逆序对数从 $\text{inv}(p)$ 变为 $0$。
• $h(p)$ 从 $\sum |p_i - i|$ 变为 $0$。

由上可得 $\text{inv}(p) \times 2 \ge h(p)$，即 $\text{inv}(p) \ge \sum_{i=1}^N \frac{|p_i-i|}{2}$ ::::

由此可知，在 $\text{inv}(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}$ 时，对于每一次交换 $(p_x,p_{x+1})$ 必须满足 $p_x$ 与 $p_{x+1}$ 都向目标靠近，也就是不能存在无效的替换。

若排列中存在 $p_i>p_j>p_k(i<j<k)$ 这样的三元组，则该排列一定是不合法的，因为对于中间的 $p_j$，它肯定会被右边的 $p_k$ 与左边的 $p_i$ 所跨过，造成两次无效的替换。

方法

知道了上面的结论后就可以很简单的解决该问题了，由于需要处理所有循环移位，我们将原排列复制两遍，形成一个长度为 $2N$ 的数组 $A$。

对于每一个位置 $A_i$，计算其左侧排列的最大值的位置 $l_i$ 与其右侧排列的最小值位置 $r_i$，如果存在 $A_{l_i}>A_i>A_{r_i}$ 且 $r_i-l_i \le N$，那么就可以知道若一个长度为 $N$ 的排列包含了区间 $[l_i,r_i]$，则此排列必不合法。设该排列的起始点为 $s$，则

• $s \le L_i$。
• $s+N-1\ge R_i$。

即 $R_i - N + 1 \le s \le L_i$。

使用差分数组记录所有使排列变“坏”的起始位置 $s$。注意处理窗口在 $2N$ 序列上循环映射回 $1 \dots N$ 的逻辑。最终差分数组中值为 $0$ 的位置即为好的起始点。

Code

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

ll T;
ll n;
ll a[410000],l[410000],r[410000],d[410000];

void make(ll aa,ll bb){
	if (aa>bb) return;
	ll x=(aa%n+n-1)%n+1,y=(bb%n+n-1)%n+1;
	if (x<=y){
		d[x]++;d[y+1]--;
	}else{
		d[x]++;d[n+1]--;
		d[1]++;d[y+1]--;
	}
}

void solve(){
	cin>>n;
	for (int i=0;i<=2*n;i++){
		a[i]=0;l[i]=-1;r[i]=-1;d[i]=0;
	}
	for (int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	stack <int> q;
	for (int i=1;i<=2*n;i++){
		while (!q.empty()&&a[q.top()]<=a[i])q.pop();
		if (!q.empty()&&i-q.top()<n)l[i]=q.top();
		q.push(i);
	}
	while (!q.empty())q.pop();
	for (int i=2*n;i>=1;i--){
		while (!q.empty()&&a[q.top()]>=a[i])q.pop();
		if (!q.empty()&&q.top()-i<n)r[i]=q.top();
		q.push(i);
	}
	for (int i=1;i<=2*n;++i){
		if(l[i]!=-1&&r[i]!=-1){
			make(r[i]-n+1,l[i]);
		}
	}
	vector<int> v;
	ll res=0;
	for (int i=1;i<=n;++i){
		res+=d[i];
		if (!res) v.push_back((n-i+1)%n);
	}
	sort(v.begin(),v.end());
	cout<<v.size()<<"\n";
	for(int i=0;i<v.size();++i){
		cout<<v[i]<<" ";
	}
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) solve();
	return 0;
}