题解：P11505 [NordicOI 2018] Mysterious Array

· · 题解

一眼丁真秒掉的计数题，开心。

看到这个题想起来 ABC262Ex Max Limited Sequence。区别就是这题要求排列，那题没要求。

首先处理约束信息，因为要求的是区间最小值，所以我们可以用 set 处理出每个位置的值域下界，也就是所有包含该位置的区间约束的最大值。

然后对于一个最小值约束 \min=x，可能存在若干对要求 (l,r)，由于这是一个排列每个数只能出现一次，但是必须所有区间都合法。所以 x 必然出现在这些区间取交得出来的 [L,R] 中。

接下来考虑填入数字，对于每个位置是形如 a_i\ge x 的形式。如果按照序列顺序填入不好判断哪些数字用过了，所以我们考虑按照值域约束从大到小填入，这样子对于当前扫描到的数 x，因为约束是 \ge x，[x,n] 之内的所有数就一视同仁了。先考虑确定 x，就是在 [L,R] 之内选择一个数，那么是 R-L+1 种方案。

接着考虑安排其他 \ge x 位置的答案，我们就是要在 [x+1,n] 之内给他们分配（注意 x 这个时候已经被用过了），然后之前也用过若干个数字（所有满足值域下界 >x 的位置个数），设一共有 num 个，那么就是有 n-x-num 个数可以被我们利用，填入 y-1 个位置（y 是要求 a_i\ge x 的位置个数，由于已经填入了 x，所以是 y-1），就是 A^{n-x-num}_{y-1}。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int mod=1e9+7;
void add(int &x,int y){ x=x+y>=mod?x+y-mod:x+y; }
void sub(int &x,int y){ x=x<y?x-y+mod:x-y; }
void chkmax(int &x,int y){ x=x>y?x:y; }
void chkmin(int &x,int y){ x=x<y?x:y; }
struct limit{
    int l,r,x;
}lim[maxn];  
vector<int> pos[maxn],vec[maxn],ad[maxn],del[maxn]; 
int mn[maxn],fac[maxn],inv[maxn],ans=1,cnt=0,n,m; multiset<int> s;
int qpow(int x,int k){
    int res=1;
    for(;k;k>>=1){
        if(k&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
    }
    return res;
}
void end(){ cout<<"0"; exit(0); }
int A(int N,int M){
    if(N==0||M==0) return 1;
    return 1ll*fac[N]*inv[N-M]%mod; 
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m; fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2); for(int i=n-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
    for(int i=1;i<=m;i++){
        cin>>lim[i].l>>lim[i].r>>lim[i].x;
        ad[lim[i].l].pb(i); del[lim[i].r+1].pb(i);
        vec[lim[i].x].pb(i);
    }
    for(int i=1;i<=n;i++){
        for(auto z:ad[i]) s.insert(-lim[z].x);
        for(auto z:del[i]) s.erase(s.find(-lim[z].x));
        if(s.size()){ int z=*s.begin(); mn[i]=-z; pos[-z].pb(i); }
        else pos[0].pb(i);
    }
    for(int i=n;i>=1;i--){
        if(!vec[i].size()) continue;
        int L=-n,R=n;
        for(auto z:vec[i]) chkmax(L,lim[z].l),chkmin(R,lim[z].r);
        int num=0,rest=n-i-cnt;
        if(rest+1<(int)pos[i].size()||L>R) end();
        for(auto z:pos[i])
            if(L<=z&&z<=R) num++;
        ans=1ll*ans*num%mod; num=pos[i].size()-1;
        ans=1ll*ans*A(rest,num)%mod;
        cnt+=pos[i].size();
    }
    ans=1ll*ans*fac[pos[0].size()]%mod;
    cout<<ans;
    return 0;
}