CF101B Buses 题解

题意

有 \(n\) 个公交站， \(m\) 辆车，只能从 \([s_i,t_i-1]\) 范围里的公交站上车，问有多少种到第 \(n\) 站的方案。

分析

这显然是一道 dp 题。 \(dp_i\) 表示坐第 \(i\) 辆车到 \(t_i\) 站的方案数。首先将所有公交车按照终点从小到大排序，这样就可以二分找到终点符合条件的一段公交车的左端点 \(l\) 和右端点 \(r\) ，\(dp_i= \sum\limits_{j=l}^r dp_j\) ，特判一下起点为 \(0\) 的情况，用前缀和优化即可。

代码

#include 
#define int long long
using namespace std;
const int inf=2139062143;
const int MAXN=1e5+7;
const int mod=1e9+7;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
	register T1 x=0;register bool f=false;char ch=getchar();
	while(ch<'0') f|=(ch=='-'),ch=getchar();
	while(ch>='0') x=(x*10)+(ch^48),ch=getchar();
	x=(f?-x:x);a=x;qread(b...);
}
int n,m,dp[MAXN],pre[MAXN],ans;
struct node{int s,t;node(){;}node(int _s,int _t):s(_s),t(_t){}bool operator < (const node &o)const{return ta;
signed main()
{
    qread(n,m);int i,j;
    for(i=0;i