Acw 5046
思路
dp，\(dp_i\) 表示前i种药且吃第i种药使智商达到\(r_i\)的方案，根据题意可知
\[dp_i = \sum dp_j,(r_j\in [l_i,r_i-1])
\]
先将各区间按右端点排序， 求j的区间可用二分.
代码
//9.24
int n,m,k;
int f[N],s[N];
//acw 110
struct seg
{
int l,r;
bool operator <(const seg &a) const
{
if(r!=a.r) return r<a.r;
return l<a.l;
}
}w[N];
int get_l(int x)
{
int l=1,r=m+1;
while(l<r)
{
int mid=(l+r)/2;
if(w[mid].l<=x) l=mid+1;
else r=mid;
}
return r;
}
int get_r(int x)
{
int l=1,r=m+1;
while(l<r)
{
int mid=(l+r+1)/2;
if(w[mid].r<=x) l=mid;
else r=mid-1;
}
return r;
}
void solve()
{
cin>>n>>m;
for(int i=2;i<=m+1;i++) cin>>w[i].l>>w[i].r;
sort(w+1,w+m+2);
int res=0;
f[1]=1,s[1]=1;
for(int i=2;i<=m;i++)
{
int l=get_l(w[i].l);
int r=get_r(w[i].r);
f[i]=(s[r]-s[l-1])%mod;
s[i]=(s[i-1]+f[i])%mod;
if(w[i].r>=n) res=(res+f[i])%mod;
}
cout<<(res+mod)%mod<<endl;
}