【CF720D】Slalom
题意：一个n*m的网格，其中有k个矩形障碍，保证这些障碍不重叠。问你从(1,1)走到(n,m)，每步只能往右或往上走，不经过任何障碍的方案数。两种方案被视为不同，当且仅当存在一个障碍，它在第一种方案里被从右侧绕过，而在第二种方案里被从左侧绕过（第一种左，第二种右同理）。
$n,mle 10^6,kle 10^5$。
题解：首先我们将相同方案的不同路线放到一起，并用其中最低的那个路线来代表这个方案。然后考虑扫描线，当新加入一个障碍的左侧时，这个侧面以左的所有路线都被迫走到这个障碍的上沿处。用线段树维护一下就好，细节比较多。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int P=1000000007;
const int maxk=100010;
const int maxn=1000010;
int n,m,k,tot;
struct node
{
int x,l,r,k;
}p[maxk*3];
int s[maxn<<2],tag[maxn<<2],siz[maxn<<2];
bool cmp(const node &a,const node &b)
{
return (a.x==b.x)?((a.k==b.k)?(a.l>b.l):(a.k<b.k)):(a.x<b.x);
}
inline void pushdown(int l,int r,int x)
{
if(tag[x]==1)
{
s[lson]=s[rson]=0,tag[lson]=tag[rson]=1;
int mid=(l+r)>>1;
siz[lson]=mid-l+1,siz[rson]=r-mid,tag[x]=0;
}
if(tag[x]==2)
{
s[lson]=s[rson]=0,tag[lson]=tag[rson]=2,siz[lson]=siz[rson]=0,tag[x]=0;
}
}
inline void pushup(int x)
{
s[x]=s[lson]+s[rson],siz[x]=siz[lson]+siz[rson];
if(s[x]>=P) s[x]-=P;
}
void modify(int l,int r,int x,int a,int b)
{
if(l==r)
{
s[x]=b;
return ;
}
pushdown(l,r,x);
int mid=(l+r)>>1;
if(a<=mid) modify(l,mid,lson,a,b);
else modify(mid+1,r,rson,a,b);
pushup(x);
}
void updata(int l,int r,int x,int a,int b,int c)
{
if(a<=l&&r<=b)
{
if(c==1) tag[x]=1,siz[x]=r-l+1,s[x]=0;
else tag[x]=2,siz[x]=s[x]=0;
return ;
}
pushdown(l,r,x);
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a,b,c);
if(b>mid) updata(mid+1,r,rson,a,b,c);
pushup(x);
}
int query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s[x];
pushdown(l,r,x);
int mid=(l+r)>>1,ret=0;
if(a<=mid) ret+=query(l,mid,lson,a,b);
if(b>mid) ret+=query(mid+1,r,rson,a,b);
if(ret>=P) ret-=P;
return ret;
}
int count(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return siz[x];
pushdown(l,r,x);
int mid=(l+r)>>1;
if(b<=mid) return count(l,mid,lson,a,b);
if(a>mid) return count(mid+1,r,rson,a,b);
return count(l,mid,lson,a,b)+count(mid+1,r,rson,a,b);
}
int find(int l,int r,int x,int a)
{
if(l==r) return l;
pushdown(l,r,x);
int mid=(l+r)>>1;
if(a<=siz[lson]) return find(l,mid,lson,a);
return find(mid+1,r,rson,a-siz[lson]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
//freopen("cf720D.in","r",stdin);
n=rd(),m=rd(),k=rd();
int i,a,b,c,d;
for(i=1;i<=k;i++)
{
a=rd(),b=rd(),c=rd(),d=rd();
p[++tot].x=a,p[tot].l=b,p[tot].r=d,p[tot].k=2;
p[++tot].x=a+1,p[tot].l=b,p[tot].r=d,p[tot].k=1;
p[++tot].x=c+1,p[tot].l=b,p[tot].r=d,p[tot].k=3;
}
p[++tot].x=1,p[tot].l=2,p[tot].r=m,p[tot].k=1;
p[++tot].x=1,p[tot].l=2,p[tot].r=m,p[tot].k=3;
p[++tot].x=n+1,p[tot].l=1,p[tot].r=m-1,p[tot].k=2;
sort(p+1,p+tot+1,cmp);
modify(1,m,1,1,1);
for(a=1;a<=tot;a=b+1)
{
for(b=a;b<tot&&p[b+1].x==p[b].x&&p[b+1].k==p[b].k;b++);
if(p[a].k==2)
{
for(i=a;i<=b;i++) if(p[i].r!=m)
{
c=count(1,m,1,1,p[i].r+1);
if(!c) d=0;
else d=find(1,m,1,c);
if(d!=p[i].r+1)
{
modify(1,m,1,p[i].r+1,query(1,m,1,d+1,p[i].r+1));
}
}
}
else if(p[a].k==1)
{
for(i=a;i<=b;i++) updata(1,m,1,p[i].l,p[i].r,1);
}
else
{
for(i=a;i<=b;i++) updata(1,m,1,p[i].l,p[i].r,2);
}
}
printf("%d",query(1,m,1,m,m));
return 0;
}