C. Min Max Sort 

思路：

a[i]数组记录i下标数为a[i],xu[i]数组记录数i所在位置为xu[i]

1，每次都是从排列取两个数，小的放前面，大的放后面。

2，我们注意到，对于1...n排列，如果中间的n/2-1与n/2相对位置是xu[n/2-1]<=xu[n/2],我们是不用去调换他们，因为在他们中间的值后面自然会用到

3，递推下去，如果对于x，xu[x]<=xu[n-x+1],并且xu[x]xu[n-x]我们也不需要动x,因为他们都满足相对位置正确，即使中间有值，后面自然会被取出，他们就会在一起。

4，如果一对x与n-x+1一旦取出，我们保证，比x小的数一定要取出才能放x前面（比n-x+1大的数才能放他后面)，因为这对一取出，x最前面，n-x+1在最后面

#include 
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair pll;
typedef pair pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 2e5 + 10;int a[N], xu[N];int main()
{int t, n;cin >> t;while (t--){int ans = 0;cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i], xu[a[i]] = i;for (int i = (n + 1) / 2; i >= 1; --i){int k = n - i + 1;if (i == (n + 1) / 2){if (xu[i] > xu[k]){ans = i;break;}}else{if (xu[i] > xu[k] || xu[i] >= xu[i + 1] || xu[k] <= xu[k - 1]){ans = i;break;}}}cout << ans << endl;}return 0;
}

D. Fixed Prefix Permutations

思路：

1，定义p*q的排列为每个r[i]=q[ p[i] ]，我们的期望是对于r[1],希望q的下标j使得q[j]=1,对于r[2],我们希望q的下标j使得q[j]=2....r[k]->q[j]=k。即我们需要一个排列q,他们1到k的值的下标依次为p[1],p[2],...p[k]

2，因为需要连续的1到k，且与所有排列匹配，我们容易联想建立一颗字典树。

3，树的层定义为1到m层，我们存储i层树的边为q[ j ]（值为i）的下标j，表示存在在第i层，有下标为j的边可以使得q[j]=i

4,当我们存储完所有边后，我们对要求的排列从1层到m层，每次询问第i层是否存在下标为j=p[i]的边，有则使得q[j]=i成立。

#include 
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair pll;
typedef pair pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 5e4 + 10;int tree[N * 10][15], pos[15], a[N][15];//pos记录每一个排列第i层的下标j
int n, m;
int num;
int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while (t--){cin >> n >> m;num = 0;for (int i = 0; i <= n * m; ++i)memset(tree[i], 0, sizeof(tree[i]));//案例t可能太大，如果每次都是全部归0，会被tlefor (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){cin >> a[i][j];pos[a[i][j]] = j;}int p = 0;for (int i = 1; i <= m; ++i)//建字典树{if (!tree[p][pos[i]])tree[p][pos[i]] = ++num;//在层数p建立下标为j=pos[i]的边p = tree[p][pos[i]];}}for (int i = 1; i <= n; ++i){int ans = 0, p = 0;for (int j = 1; j <= m; ++j){if (tree[p][a[i][j]])ans++, p = tree[p][a[i][j]];else break;}cout << ans;if (i == n)cout << endl;else cout << ' ';}}return 0;
}