纯思维的1900构造还是有些顶，而且全球场和div1+2感觉还是没有难度分数通胀的，同等的分数全球场的题质量明显高一些。
D. Permutation Addicts
题意：
我们给定一个长度为n的排列a，我们通过a按照如下方法去构造一个数组b。
确定某个数值k(k的取值范围是从1到n)
对于a的第i项
1.如果a[i]>k。那么下标为a[i]的b数组的元素等于a排列中从1到i里选择一个a[j]满足a[j]<=k，如果没有这样的a[j]那么让b的这一个元素为n+1
2.如果a[i]<=k。那么下标为a[i]的b数组的元素等于a排列中从1到i里选择一个a[j]满足a[j]>k，如果没有这样的a[j]那么让b的这一个元素为0
现在不慎丢失了a排列和数值k，请你根据b数组求出a排列和数值k
思路:
分析题意，理解构造过程。
我们通过n次赋值构造出来的b显然是满足这样的一个条件的：下标大于k的让其小于等于k，下标小于等于k的让其大于k，也就是说i>k 那么b[i]<=k；i<=k则有b[i]>k。
1.k的求解
根据上述分析，显然k数值可以作为：有多少项b[i]>i，或者最后一项b[i]>i的下标，这里就不一一说了，所有方式都是和上面构造过程相关的。
2.求解a数组
第一点：对于数组b来讲，n+1和0必定出现一个且仅一个，并且n+1仅出现在前缀，0仅出现在后缀。
(证明很简单，可以自己模拟一下试试)
第二点：我们首先能确定是b数组中值为n+1或0的位置。
举个例子
7 7 7 3 3 3
7的下标集为 1 2 3所以可以确定1 2 3一定是以某种顺序先出现在排列a的头部。
接下来看3的下标集合 4 5 6
推理b中4 5 6出现3显然应该是因为a中3出现的位置要比4 5 6靠前，换句话来说就是3在制约4 5 6，又因为题目中的制约是前方制约后方，显然3应该总是出现4 5 6前的，所以我们需要确保的就是7的集合中 1 2 3的排列一定满足1制约的集合中的元素一定是出现在1后面，2，3以此类推。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, b[N], k;
vector<int> v[N];
vector<int> a;void solve()
{cin>>n;k=0;a.clear();for(int i=0;i<=n+1;i++)v[i].clear();for(int i=1;i<=n;i++){cin>>b[i];k+=b[i]>i;//其实你还以这么想，最后一项b[i]>i的位置就是k的值v[b[i]].push_back(i);}int cur=0;if(v[n+1].size())cur=n+1;int cnt=0;while(cnt<n){cnt+=v[cur].size();for(auto &it:v[cur])if(v[it].size())swap(it,v[cur].back());a.insert(a.end(),v[cur].begin(),v[cur].end());cur=v[cur].back();}cout<<k<<'\n';for(auto it:a)cout<<it<<" ";cout<<'\n';
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--)solve();return 0;
}
明天把SAM的复习扫扫尾巴，开始复习树的内容。
