来个不一样的做法：扫描线，线段树上二分。
思路
我们发现只需找到小球落到每个挡板后的下一个挡板，就可以建出一张 DAG，在 DAG 上简单 DP 即可求方案。
所以我们考虑怎么建图。
大多人用扫描线是从下到上扫描的，但我们考虑从左到右扫描。
我们在挡板左端做加入操作，右端做删除操作，对于扫描中每一个横坐标，我们可以用线段树维护出每个高度的挡板编号。
对于第 \(i\) 号挡板，我们需要在横坐标为 \(l_i-1\) 和 \(r_i+1\) 时，找到最高的挡板 \(j\)，满足 \(u_j < u_i\) 且 \(u_j + s_j \geq u_i\)。
显然，我们只要在线段树上维护区间 \(u_j + s_j\) 的最大值，就可以线段树上二分，对每个 \(i\) 求出对应的 \(j\)。
时间复杂度 \(O((n + w)\log{n})\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MOD=1e9+7;
int Add(int a,int b){
return (a+b)%MOD;
}
int Mul(int a,int b){
return 1ll*a*b%MOD;
}
int h,w,n,u[N],s[N],ord[N],rk[N],cnt,f[N];
vector<int> lh,ne[N];
struct operation{
int t,id,x;
bool operator < (const operation &B) const{
//注意排序时的优先级，这个需要全面的考虑
if(x!=B.x){
return x<B.x;
}else{
if(t!=B.t){
return t<B.t;
}else{
if(t){
return u[id]>u[B.id];
}else{
return u[id]<u[B.id];
}
}
}
}
}op[2*N];
struct SGT{//线段树
struct node{
int l,r,val;
}tree[4*N];
void pushup(int p){
tree[p].val=max(tree[2*p].val,tree[2*p+1].val);
}
void build(int p,int l,int r){
tree[p]={l,r,0};
if(l<r){
int mid=(l+r)/2;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
}
}
void modify(int p,int x,int v){
int l1=tree[p].l,r1=tree[p].r;
if(l1==r1){
tree[p].val=u[v]+s[v];
}else{
int mid=(l1+r1)/2;
if(x<=mid){
modify(2*p,x,v);
}else{
modify(2*p+1,x,v);
}
pushup(p);
}
}
int query(int p,int x,int v){
int res=0;
if(x){
int l1=tree[p].l,r1=tree[p].r;
if(l1==r1){
if(tree[p].val>=v){
res=r1;
}
}else{
int mid=(l1+r1)/2;
if(x>mid){
res=query(2*p+1,x,v);
}
if(!res&&tree[2*p].val>=v){
res=query(2*p,x,v);
}
//线段树上二分的精髓在于上面的两个if，如果写错复杂度就会不对
}
}
return res;
}
}tr;
int main(){
scanf("%d%d%d",&h,&w,&n);
for(int i=1;i<=n;i++){
int l,r;
scanf("%d%d%d%d",&u[i],&l,&r,&s[i]);
ord[i]=i;
if(l-1){
op[++cnt]={1,i,l-1};
}else{
lh.push_back(i);//所有靠到1的挡板特殊处理
}
if(r+1<=w){
op[++cnt]={0,i,r+1};
}
}
sort(ord+1,ord+n+1,[&](int x,int y){
return u[x]<u[y];
});
for(int i=1;i<=n;i++){
rk[ord[i]]=i;
}
//ord[i]指第i低的挡板编号，rk[i]指挡板i的高度排名
sort(op+1,op+cnt+1);
tr.build(1,1,n);
for(int i=0;i<lh.size();i++){
tr.modify(1,rk[lh[i]],lh[i]);//一定要加入靠到1的挡板
}
for(int i=1,j=1;i<=w;i++){
while(j<=cnt&&op[j].x==i&&!op[j].t){
int idx=op[j].id;
tr.modify(1,rk[idx],0);//删除挡板
ne[rk[idx]].push_back(tr.query(1,rk[idx]-1,u[idx]));
j++;
}
f[tr.query(1,n,h+1)]++;
while(j<=cnt&&op[j].x==i&&op[j].t){
int idx=op[j].id;
ne[rk[idx]].push_back(tr.query(1,rk[idx]-1,u[idx]));
tr.modify(1,rk[idx],idx);//加入挡板
j++;
}
}
for(int i=n;i>=1;i--){
if(ne[i].size()==1){
f[ne[i][0]]=Add(f[ne[i][0]],Mul(2,f[i]));
}else{
f[ne[i][0]]=Add(f[ne[i][0]],f[i]);
f[ne[i][1]]=Add(f[ne[i][1]],f[i]);
}
}
//DAG上DP
printf("%d",f[0]);
return 0;
}