我永远喜欢39号同学2018。
xh39
·
·
题解
注:文中所有 / 符号表示整除。设 a 表示所求排列。
从简单情况入手，一步步推，找规律。
如何确定 1 的位置?
由于 1 是最小的数，所以任何包含 1 的区间最小值都是 1。
因此，在 S_{(n+1)/2} 的集合中出现个数可以作为1的位置。如下图:
如上图第 n=4 的例子，查询长度为 2 的区间。若 1 在位置 0,3 则重复出现 1 次，在位置 1,2 则出现 2 次。
如上图 n=5 的例子，查询长度为 3 的区间。若 1 在位置 0,1,2,3,4，则出现次数依次为 1,2,3,2,1 。
如上图 n=7 的例子，查询长度为 4 的区间。若 1 在位置 0,1,2,3,4，则出现次数依次为 1,2,3,3,2,1 。
则出现次数为 b ， 那么 a[b+1]=a[n-b-1]=1 。
由与选取 n-b-1 的位置就是选取 b+1 的位置倒过来，所以实质上无影响。本篇题解默认选取 b+1 位置。
如何确定 2 的位置?
此时麻烦一些，因为包含 2 的区间最小值可能是 1 或 2 。
由于出现了 1 的区间最小值只可能是 1 。所以选完 1 以后，1 的左右裂成了两个部分。所以判断到底是在哪个部分。然后就用之前的方法求解。
如何判断区间内是否有解?设区间长度为 size，则 S_{size} 中一定出现了 1 次最小值。而 S_{size+1} 中一定没有出现最小值。所以就判断 S_{size} 中 2 的出现次数。
若两部分内都有解，此时两部分长度相等，那么选取任意一部分都是等价的，本题解选取左部分。
确定完部分就与选取 1 时用同样的方法。
如何选取更多的数?(实现)
假设当前要选取 $i$。考虑用一个链表记录当前已经确定了的数 1~$(i-1)$。同时记录这个数选取的位置 $id$。这样区间就是 [当前.id+1,下一个.id-1]。
这样一来，插入操作，查找操作都方便了很多。就可以在 $O(n^2)$ 的复杂度内出解。
## 参考代码
```cpp
#include<iostream>
using namespace std;
struct i_am_aking_ioi{
int id,next;
}_[1000005]; //链表。
int mark[1005][1005]; //mark[i][j]:长度为i的区间(S[i])内出现了几次j。
int main(){
int n,i,j,A,ykb;
cin>>n;
for(i=1;i<=n;i++){
for(j=i;j<=n;j++){
scanf("%d"，&A);
mark[i][A]++;
}
}
_[0].next=n+1;
_[0].id=-1;
_[n+1].id=n; //初始化不能漏，一开始的区间是[0,n-1]，由于区间是[now.id+1,next.id-1]，所以要一开始要设为-1和n。
for(i=1;i<=n;i++){ //依次插入1~n
for(j=0;j<=n;j=_[j].next){ //在每个区间内查找。
ykb=_[_[j].next].id-_[j].id; //区间长度
if(!mark[ykb][i]&&mark[ykb-1][i]){
_[i].id=_[j].id+mark[ykb+1>>1][i];//这个区间时从now.id+1开始编号的。所以需要加上_[j].id。同时+1-1抵消。
_[i].next=_[j].next;
_[j].next=i;
break; //已经找到，不需要再找。因为多个可行区间任选一个。
}
}
}
for(i=_[0].next;i<=n;i=_[i].next){
cout<<i<<" ";
}
return 0;
}
```
月赛过去了这么久都没有题解。于是就写一篇。