Lut本科回忆录

赛后补的题

题目描述：

给定一个长度为n的数组a，其中每个a[i]的范围在0~n-1 且每个数仅出现一次 ，其中b数组满足对a和b数组任意的任意区间1<=l<=r<=n，其中mex{a[l],a[l+1]…a[r]}==mex{b[l],b[l+1]…b[r]}，mex是求该区间内未出现的最小非负整数，如mex{1，2，3}=0，mex{0，1，2，3}=4，输出满足的b数组的个数

题解：

我们可以用p来存每个数字在a数组里的位置，初始l=r=p[0]，

然后遍历i从0~n-1，每次查看p[i]的位置是否在区间l到r内，

如果不在l到r内，更行区间，且说明这个位置的数放上去后是区间的边界，mex值在区间改变后也会发生改变，改位置就是固定的，ans不做处理

如果在l到r内，因为i之前的数组的位置都已经找过了，而l和r的位置也存的是i之前的数，那么在这个区间内，除了已经找过的数，其他任意位置是可以随意放的，这时候的任意位置个数就是r-l+1-i，（注意这里的i意思是已经确定了i个数，如果减去，就意味着还有这么些个位置没有放），所以ans*=（这些位置个数）

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1e9+7;
ll a[N];
map<ll,ll>p;
void solve()
{
    int n;cin>>n;
    p.clear();
    rep(i,1,n){
        cin>>a[i];
        p[a[i]]=i;   //记录每个数在数组a的位置
    }
    ll l=p[0],r=p[0]，ans=1;   //初始化区间和答案
    rep(i,1,n-1){
        if(p[i]>l&&p[i]<r){
             ans*=1LL*(r-l+1-i);  //ans*(区间内未出现过数的位置)
             ans%=MOD;
        }
        l=min(l,p[i]);
        r=max(r,p[i]);
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    while(n--)solve();
    return 0;
}