题解：P11505 [NordicOI 2018] Mysterious Array

xiaoliebao1115 · 2025-01-04 21:11:01 · 题解

思路很好想的一道题吧。

sol

对于一个限制，假设 t_i 是最后 i 位置填上的数，那么必须有对于任意的 a\le j\le b，x\le t_j。所以显然可以求出每一个 t_j 的下界，记作 low_j。

对于一个 x 求出他所有的限制的交集，他显然只能填在这里。

考虑从小到大填数，因为小的难满足越大越容易，假设当前填的数是 i。

• 有关于这个数的限制，那么在交集当中选择所有等于 i 的位置去填。
• 没有限制，那么在所有 low 中算出小于等于 i 的个数然后减去 i-1 即可。

答案就是每个数可填的位置数相乘，注意判 0。

code

按照上述过程写啥都行吧，作者是用 multiset 做的算 low 部分。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int nn=2e5+5,mod=1e9+7;
int n,q,low[nn],l[nn],r[nn],cnt[nn],sum[nn],ans=1;
bool in[nn];
multiset<int> s;
vector<int> ad[nn],er[nn],e[nn];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) l[i]=0,r[i]=n+1;
    for(int i=1;i<=q;i++){
        int a,b,x;
        cin>>a>>b>>x;
        l[x]=max(l[x],a),r[x]=min(r[x],b);
        ad[a].pb(x),er[b+1].pb(x);
    }
    for(int i=1;i<=n;i++){
        for(int z:er[i]){
            if(s.find(z)!=s.end()) s.erase(s.find(z));
        }
        for(int z:ad[i]) s.insert(z);
        if(s.size()){
            auto it=s.end();it--;
            low[i]=*it;
        }
        else low[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(l[i]>r[i]){
            cout<<0<<endl;
            return 0;
        }
        e[l[i]].pb(i),e[r[i]+1].pb(i);
    }
    for(int i=1;i<=n;i++){
        for(int k:e[i]) in[k]=!in[k];
        if(in[low[i]]) cnt[low[i]]++;
        sum[low[i]]++;
    }
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++){
        if(l[i]==0&&r[i]==n+1){
            if(sum[i]-(i-1)<=0){
                cout<<0<<endl;
                return 0;
            }
            ans=(ans*(sum[i]-(i-1)))%mod;
        }
        else{
            if(!cnt[i]){
                cout<<0<<endl;
                return 0;
            }
            ans=(ans*cnt[i])%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}