题解 CF720D 【Slalom】

jun头吉吉 · 2020-10-06 22:15:05 · 题解

CF720D 【Slalom】

题意

一个 n \times m的网格，其中有k个矩形障碍，保证这些障碍不重叠。问你从(1,1)走到(n,m)，每步只能往右或往上走，不经过任何障碍的不同方案数。

两种方案被视为不同，当且仅当存在一个障碍，它在第一种方案里被从右侧绕过，而在第二种方案里被从左侧绕过。

方案数对10^9+7取模

题解

这是一个灰常厉害的题目，~~厉害到看了题解还是云里雾里，对着代码懵逼了半天才看懂~~

首先，这个不同的定义与我们平常接触到的略有不同。我们平常用f_{i,j}来dp的思路似乎不太可行。于是下面有本题第一个非常重要的转化：只记录最低的路径上的方案数。那么样例就是长这样的：

一条最低的路径指的是在所有相同的路径中所有点都最低的。如绿色就是一条最低的路径，而紫色就不是。可以证明，最低的路径的条数就等于方案数

~~至于为什么竖的没有更新本人才疏学浅解释不清楚还是留给大家自己思考吧~~

最后的答案即为2+1=3。

先来讲一讲这个东西是如何得到的：

如果当前列没有新矩形，那么f_{i,j}=f_{i-1,j}
如果加入了新矩形，那么新矩形的上方一列会产生新的最低的路径，那第4列第5行举例。

那么b就是从x,y,z转移过来，与a半毛钱关系都没有。于是我们设矩形从y1到y2，那么就有：

f_{i,x}=0,x\in[y1,y2]

f_{i,y2+1}=\sum_{x=low}^{y2+1}f_{i-1,x}\ (low\text{为从从y2下去能到的最远距离})

那么现在我们的时间复杂度为O(nm^2)，空间复杂度为O(n)，考虑优化。

首先，考虑此算法的瓶颈在哪里。主要还是两个地方：

求出 low
求 \sum_{x=low}^{y2+1}f_{i-1,x}

第二个东西求和用线段树维护十分简单。第一个东西就有点神奇了。

我们用一个set来存储当前所有覆盖的线段。那么我们就可以找到最大（指按pair的排序方法）的一条第一条线段。那么low就可以取他的 y2+1 。可能 y2+1 并不是最远距离。看下面一张图片来理解一下：

两个之间的 f 值必定是 0 ，因此不会影响 dp。

于是我们高高兴兴的打了一棵线段树，把一个矩形 (x1,y1)\to (x2,y2) 看作是在 x1 加入 [y1,y2] ，在 x2+1减去[y1,y2] ，用set维护最低线段。然后你会开开心心地 \color{red}\text{WA} 光。接下来是本题的一些细节：

加线的时候要从高往低加，因为低的会影响高的。
一开始set里要插入{0,0}不然会出现奇奇怪怪的错误
要先删线再加线~~如果你用multiset当我没说~~

本题的大致思路就是这样了。

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
    x=0;char c=getchar();bool f=false;
    for(;!isdigit(c);c=getchar())f!=c=='-';
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    if(f)x=-x;
}
template<typename T ,typename ...Arg>
inline void read(T &x,Arg &...args){
    read(x);read(args...);
}
template<typename T>
inline void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
const int mod=1e9+7;
const int N=1e6+10;
struct Seg_Tree{
    struct node{
        int l,r;
        int tag;//全零
        int sum; 
    }T[N*4];
    #define lson x<<1
    #define rson x<<1|1
    void build(int x,int l,int r){
        T[x].l=l,T[x].r=r;
        if(l==r)return;
        int mid=l+r>>1;
        build(lson,l,mid);
        build(rson,mid+1,r);
    }
    void pushup(int x){
        T[x].sum=(T[lson].sum+T[rson].sum)%mod;
    }
    void pushdown(int x){
        if(T[x].tag){
            T[lson].tag=T[rson].tag=1;
            T[lson].sum=T[rson].sum=0;
            T[x].tag=0;
        }
    }
    void upd(int x,int pos,int val){
        if(T[x].l==T[x].r){
            T[x].sum=val;
            return;
        }
        pushdown(x);
        int mid=T[x].l+T[x].r>>1;
        if(pos<=mid)upd(lson,pos,val);
        if( mid<pos)upd(rson,pos,val);
        pushup(x); 
    }
    void zero(int x,int l,int r){
        if(l<=T[x].l&&T[x].r<=r){
            T[x].tag=1;T[x].sum=0;
            return;
        }
        pushdown(x);
        int mid=T[x].l+T[x].r>>1;
        if(l<=mid)zero(lson,l,r);
        if(mid<r)zero(rson,l,r);
        pushup(x);
    }
    int qry(int x,int l,int r){
        if(l<=T[x].l&&T[x].r<=r)return T[x].sum;
        pushdown(x);
        int tmp=0,mid=T[x].l+T[x].r>>1;
        if(l<=mid)(tmp+=qry(lson,l,r))%=mod;
        if(mid<r)(tmp+=qry(rson,l,r))%=mod;
        return tmp;
    }
}seg;
int n,m,T;
vector<pair<int,int>>add[1000010],del[1000010];
set<pair<int,int>>s;
signed main(){
    read(n,m,T);
    while(T--){
        int X1,Y1,X2,Y2;
        read(X1,Y1,X2,Y2);
        add[X1].push_back(make_pair(Y1,Y2));
        del[X2+1].push_back(make_pair(Y1,Y2));
    }
    s.insert({0,0});
    for(auto Seg:add[1])
        s.insert(Seg);
    seg.build(1,1,m);
    seg.upd(1,1,1);
    for(int i=2;i<=n;i++){
        sort(add[i].begin(),add[i].end());
        reverse(add[i].begin(),add[i].end());
        for(auto Seg:add[i]){
            int x=Seg.first,y=Seg.second;
            if (y==m) continue;
            auto it=s.lower_bound(make_pair(y+2,0));it--;
            int ans=0;
            auto pr=*it;
            if(pr.second<=y)ans=seg.qry(1,pr.second+1,y+1);
            seg.upd(1,y+1,ans);
        }
        for(auto Seg:del[i])
            s.erase(Seg);
        for(auto Seg:add[i])
            s.insert(Seg),
            seg.zero(1,Seg.first,Seg.second);
    }
    auto it=s.end();it--;
    printf("%d",seg.qry(1,(*it).second+1,m));
}