有点难…

Solution

网上已经讲得很详细了吧？

补充几个问题。一是可以直接 $f_{R}=\sum \limits_{j=L-1}^R f_j$ 进行转移。但是得注意先转移大区间再转移小区间（这属于被部分包含），否则的话你可能会丢失不选小区间的决策。

第二个问题是若速度可以相等，那么需要将开始的排序进行一些小修改。考虑 $X_i$ 的左端比它大的最小的 $j$ ，若有数个 $V_k$ 等于 $V_j$ ，那么这些 $V_k$ 的点是肯定不能被染色的。右侧同理。

Code

// Code by ajcxsu

#include<bits/stdc++.h>
#define MOD (1000000007)
using namespace std;

const int N=5e5+10;
int h[N], l[N], r[N];
vector<int> L[N];
int x[N], v[N], a[N];
bool cmp(const int &a, const int &b) { return v[a]<v[b] || (v[a]==v[b] && x[a]<x[b]); }
int f[N], S[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>x[i]>>v[i], a[i]=i;
    sort(a+1, a+1+n, cmp);
    int stk[N], p[N], t=0;
    for(int i=1; i<=n; i++) {
        if(!t || stk[t]<x[a[i]]) stk[++t]=x[a[i]], p[t]=i;
        int l=1, r=t, mid;
        while(l<r) {
            mid=(l+r)>>1;
            if(stk[mid]<x[a[i]]) l=mid+1;
            else r=mid;
        }
        ::l[i]=p[r];
    }
    t=0;
    for(int i=n; i>=1; i--) {
        if(!t || stk[t]>x[a[i]]) stk[++t]=x[a[i]], p[t]=i;
        int l=1, r=t, mid;
        while(l<r) {
            mid=(l+r)>>1;  
            if(stk[mid]>x[a[i]]) l=mid+1;
            else r=mid;
        }
        ::r[i]=p[r];
    }
    for(int i=1; i<=n; i++) L[r[i]].push_back(l[i]);
    f[0]=S[0]=1;
    for(int i=1; i<=n; i++) {
        S[i]=S[i-1];
        sort(L[i].begin(), L[i].end());
        for(int j:L[i]) {
            f[i]=(1ll*f[i]+S[i]-(j-2>=0?S[j-2]:0)+MOD)%MOD;
            S[i]=(f[i]+S[i-1])%MOD;
        }
    }
    cout<<f[n]<<endl;
    return 0;
}