题解：P12761 [POI 2018 R2] 列车员 Conductor

· · 题解

DP 好题。

我们考虑先用 DP 求解第一个问题，定义 dp_{i} 为第 i 站到第 i+1 站必须检票的最优答案，考虑 DP 的转移。

显然如果存在一个 (a_x,b_x) 使得 b_x \le i，那么我们就不能从 j < a_x 转移，因为这时 (a_x,b_x) 内没有检票。这个区间（即满足条件的最大的 a_x）是好维护的。

我们发现以上式子是 m^2 的，离散化过后是 n^2 的，考虑优化转移。

容易发现转移可以变成一个区间取最小值，单点修改的问题，考虑直接上线段树维护。

要在这个基础上加上方案数也只需要考虑最小值状态的合并即可。

最后取答案时，我们记录下最大的 a_x，从他往后的 dp_i 都是合法的。

下附代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
#define int long long
#define PII pair<int,int>
using namespace std;
const int mod=1000000007;
int t,m,n,q[1000005],a[1000005],mx[1000005],tot,pm[1000005];
PII l[500005],dp[1000005];
PII tr[4000005];
void pushup(PII &x,PII y,PII z){
    if(y.first<z.first) x=y;
    else if(z.first<y.first) x=z;
    else x={y.first,y.second+z.second};
    x.second%=mod;
}
void build(int k,int l,int r){
    tr[k]={1e9,1};
    if(l==r) return;
    int mid=(l+r)/2;
    build(k*2,l,mid),build(k*2+1,mid+1,r);
}
void update(int k,int l,int r,int x,int v1,int v2){
    if(r<x||l>x) return;
    if(l==r){
        tr[k]={v1,v2};
        return;
    }
    int mid=(l+r)/2;
    update(k*2,l,mid,x,v1,v2);update(k*2+1,mid+1,r,x,v1,v2);
    pushup(tr[k],tr[k*2],tr[k*2+1]);
}
PII query(int k,int l,int r,int x,int y){
    if(r<x||l>y) return{1e9,1};
    if(x<=l&&r<=y){
        return tr[k];
    }
    int mid=(l+r)/2;
    PII res;pushup(res,query(k*2,l,mid,x,y),query(k*2+1,mid+1,r,x,y));
    return res;
}
bool cmp(PII x,PII y){
    return x.second<y.second;
}
unordered_map<int,int>mp;
signed main(){
    cin>>t;
    while(t--){
        cin>>m>>n;tot=0;mp.clear();
        int mmx=0;
        for(int i=1;i<=n;i++){
            cin>>l[i].first>>l[i].second;
            mmx=max(mmx,l[i].first);
            q[++tot]=l[i].first,q[++tot]=l[i].second;
        }
        sort(l+1,l+n+1,cmp);
        sort(q+1,q+tot+1);int cur=0;
        for(int i=1;i<=tot;i++){
            if(q[i]!=q[i-1]){
                mp[q[i]]=++cur;pm[cur]=q[i];
                a[cur-1]=q[i]-q[i-1];
            }
        }
        a[cur]=m-q[tot];
        int mxx=0;
        build(1,1,cur);
        for(int i=0;i<=cur;i++) mx[i]=0,dp[i]={0,0};
        for(int i=1;i<=n;i++){
            mxx=max(mxx,mp[l[i].first]);
            mx[mp[l[i].second]]=mxx;
        }
        int res=0;
        for(int i=1;i<=cur;i++){
            if(mx[i]) res=mx[i];
            mx[i]=res;
        }
        for(int i=1;i<cur;i++){
            int lst=mx[i];
            if(lst==0) dp[i]={1,a[i]};
            else dp[i]=query(1,1,cur,lst,i-1),dp[i].first++,dp[i].second*=a[i];
            dp[i].second%=mod;
            update(1,1,cur,i,dp[i].first,dp[i].second);
        }
        PII ans={1e9,1};
        for(int i=mp[mmx];i<cur;i++){
            pushup(ans,ans,dp[i]);
        }
        cout<<ans.first<<' '<<ans.second%mod<<endl;
    }
    return 0;
}