题目链接：点击打开链接

当转移[l,r] 区间时， 若[0, r-1] 这里的区间都已经转移完毕时是最优的，所以按右端点升序，同理右端点相同时左端点升序，然后树状数组维护一下前缀和。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define N 100005 #define mod 1000000007 #define ll long long int n, m; ll c[N<<2]; inline int lowbit(int x){return x&(-x);} void updata(ll val, int pos){ while(pos <= n){ c[pos] = (c[pos] + val)%mod; pos += lowbit(pos); } } ll sum(int pos){ ll ans = 0; while(pos){ ans = (ans + c[pos])%mod; pos -= lowbit(pos); } return ans; } struct node{ int l, r; }a[N]; bool cmp1(node x, node y){if(x.r==y.r)return x.l
       
        G; void debug(){ for(int i = 0; i < m; i++)printf(" %d %d\n", a[i].l, a[i].r); printf("***"); for(int i = 0; i < G.size(); i++) printf("%d ", G[i]); puts(""); printf("** n = %d\n", n); } void input(){ n++; G.clear(); G.push_back(1); G.push_back(n); for(int i = 0; i < m; i++)scanf("%d %d", &a[i].l, &a[i].r),a[i].l++, a[i].r++, G.push_back(a[i].l), G.push_back(a[i].r); sort(G.begin(), G.end()); G.erase(unique(G.begin(), G.end()), G.end()); // debug(); for(int i = 0; i < m; i++) { a[i].l = lower_bound(G.begin(), G.end(), a[i].l) - G.begin()+1; a[i].r = lower_bound(G.begin(), G.end(), a[i].r) - G.begin()+1; } n = lower_bound(G.begin(), G.end(), n) - G.begin()+1; sort(a, a+m, cmp1); } int main(){ int i, j; while(~scanf("%d %d",&n,&m)){ // bool ok = n==42; input(); if(m==0 || G.size()==1){puts("0");continue;} // debug(); memset(c, 0, sizeof c); updata(1, 1); for(i = 0; i < m; i++){ ll ans = sum(a[i].r-1) - sum(a[i].l-1); if(ans < 0) ans = (ans%mod + mod)%mod; // printf(" %d %d %d\n", a[i].l, a[i].r, ans); updata(ans, a[i].r); // printf(" %d %d %d\n", a[i].l, a[i].r, sum(a[i].r) - sum(a[i].l-1)); } ll ans = sum(n) - sum(n-1); // printf("%d\n", ans); if(ans < 0) ans = (ans%mod + mod)%mod; cout<