CFR 101 B. Buses ( DP + Segment Tree )

Problem - 101B - Codeforces
dp[ i ][ t[ i ] ] = sum{ dp[ i - 1 ][ s[ i ] .. t[ i ] - 1 ] }, Ɐ i: current bus
bus需要先依據終點 t做昇序排序。
注意因為區間範圍可能很大，所以需要離散化。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e9 + 9;
const int MAXM = 1e5 + 5;
const int MOD = 1e9 + 7;

void addmod(int &x, int v){ x += v; x %= MOD; }

struct itvt{
    int sum;
    int lb, rb;
    itvt *lc, *rc;
    itvt(int _l = -1, int _r = -1): sum(0), lb(_l), rb(_r), lc(NULL), rc(NULL){}
    void pull(){
        sum = 0;
        if( lc ) addmod( sum, lc->sum );
        if( rc ) addmod( sum, rc->sum );
    }
    void update(int k, int v){
        if( lb == rb ){
            addmod( sum, v );
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ){
            if( !lc ) lc = new itvt( lb, mid );
            lc->update( k, v );
        }
        else{
            if( !rc ) rc = new itvt( mid + 1, rb );
            rc->update( k, v );
        }
        pull();
    }
    int qsum(int ql, int qr){
        if( qr < lb || rb < ql ) return 0;
        if( ql <= lb && rb <= qr ) return sum;
        int res = 0;
        if( lc ) addmod( res, lc->qsum( ql, qr ) );
        if( rc ) addmod( res, rc->qsum( ql, qr ) );
        return res;
    }
};

int n, m;

struct Bus{
    int s, t;
    Bus(int _s = -1, int _t = -1): s(_s), t(_t){}
    bool operator < (const Bus &oth) const{ return t < oth.t; }
} bus[ MAXM ];

void solve(){
    itvt *root = new itvt( 0, n );
    root->update( 0, 1 );
    sort( bus, bus + m );
    for(int i = 0; i < m; ++i)
        root->update( bus[ i ].t, root->qsum( bus[ i ].s, bus[ i ].t - 1 ) );
    printf("%d\n", root->qsum( n, n ));
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
        scanf("%d%d", &bus[ i ].s, &bus[ i ].t);
    solve();
    return 0;
}