题解：P11505 [NordicOI 2018] Mysterious Array

Purslane · 2025-01-03 18:52:51 · 题解

Solution

Purslane 花了半个小时想这道题，已经到了弱智的境界……

设最后每个位置数是 a_i，那么限制 (l,r,d) 将得到一个必要条件——\forall l \le i \le r，a_i \ge d。因此可以计算出每个数的下界 u_i。

显然 i 只能放在 u_j \le i 的 j 上。

如果 i 有一些限制，设这些限制的交是 [L,R]，则 j \in [L,R]。则显然如果 u_j \le i，则 u_j=i——所以这些 j 都是能放的。

如果没有限制，看有多少个当前还能放数的点即可。

复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,MOD=1e9+7;
int n,q,rnk[MAXN],ans=1;
vector<pair<int,int>> lim[MAXN];
vector<int> occ[MAXN];
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    ffor(i,1,q) {
        int a,b,x;
        cin>>a>>b>>x,lim[x].push_back({a,b});   
    }
    set<int> pos;
    ffor(i,1,n) pos.insert(i);
    roff(i,n,1) {
        for(auto pr:lim[i]) {
            int l=pr.first,r=pr.second;
            while(1) {
                auto it=pos.lower_bound(l);
                if(it==pos.end()||*it>r) break ;
                rnk[*it]=i,pos.erase(it);   
            }
        }
    }
    ffor(i,1,n) rnk[i]=max(rnk[i],1ll),occ[rnk[i]].push_back(i);
    int cnt=0;
    ffor(i,1,n) {
        if(lim[i].size()) {
            int L=0,R=n+1,mul=0;
            for(auto pr:lim[i]) L=max(L,pr.first),R=min(R,pr.second);
            for(auto id:occ[i]) if(L<=id&&id<=R) mul++;
            ans=ans*mul%MOD;
            cnt+=occ[i].size(),cnt--;
        }
        else cnt+=occ[i].size(),ans=ans*cnt%MOD,cnt--;
    }
    cout<<ans;
    return 0;
}