101B Buses

問題

バス停が0,1,2,...,nのn+1個ある。
0は自宅でnが目的地である。

m本のバスが走っている。
それぞれのバスはs[i]を出発してt[i]を終着駅とする。
バスは、s[i]からt[i]-1のどこからでも乗ることができるが、降りることができるのはt[i]のバス停のみである。

また、徒歩でバス停間を移動したり、目的地の逆向きにバスに乗ることはできない。
このとき、バスを使って目的地へ行く方法は何通りあるか、mod 10^9+7ｆで求めよ。

制約条件

n≦10^9
m≦10^5
s[i],t[i]≦n

方針

まずは座標圧縮する。すると考える必要のあるバス停は10^9から2*10^5個に減る。

次に終点の順にバスをソートする。
そうすると次のようなDPにより場合の数が求められる。

dp[i]=Σ[j=0〜i-1]dp[j]

ただし、和を求める部分は愚直にやるとTLEするので、binary indexed treeを使ってやる必要がある。

ソースコード

const int MX=222222, mod=(int)1e9+7;
int bit[MX+1];
int sum(int i){
	int s=0;
	while(i>0)(s+=bit[i])%=mod, i-=i&-i;
	return s;
}
void add(int i,int x){
	while(i<=MX)(bit[i]+=x)%=mod, i+=i&-i;
}
int n,m,s[100000],t[100000],v[200002],k;
pi p[100000];

void run(){
	cin>>n>>m; k=0;
	rep(i,m){
		cin>>s[i]>>t[i];
		v[k++]=s[i]; v[k++]=t[i];
	}
	v[k++]=0; v[k++]=n;
	
	sort(v,v+k); k=unique(v,v+k)-v;
	rep(i,k+3)bit[i]=0;
	
	rep(i,m){
		p[i].first=lower_bound(v,v+k,t[i])-v+1;
		p[i].second=lower_bound(v,v+k,s[i])-v+1;
	}
	sort(p,p+m);
	
	add(1,1);
	rep(i,m)add(p[i].first,sum(p[i].first-1)-sum(p[i].second-1));
	
	cout<<(sum(k)-sum(k-1)+mod)%mod<<endl;
}