题解 AT4353 【[ARC101D] Robots and Exits】

2020-02-12 08:38:07


可能更好的阅读体验


神仙题...

我们先把所有只有只会从一个出口出去的机器人删掉,这些机器人不影响答案。

对于剩下的机器人,记它到左边第一个出口的距离为 $a$ ,到右边第一个出口的距离为 $b$ 。那么每个机器人可以看成一个点 $(a,b)$ 。

设 $x$ 为所有机器人往左移动的最远点到初始位置的距离, $y$ 为所有机器人往右移动的最远点到初始位置的距离。

那么每次相当于把 $(x,y)$ 变成 $(x+1,y)$ 或者 $(x,y+1)$ 。

可以发现当 $x=a_i$ 时,机器人 $i$ 会走左边第一个出口出去;当 $y=b_i$ 时,机器人 $i$ 会走右边第一个出口出去。

于是可以看成从原点开始走,每次可以往上或者往右走,那么最后走的折线的上下两边分别代表走左边的和走右边的集合。

可以把折线平移,然后就可以用经过的点来表示折线了。

设 $f[i]$ 表示折线最后经过的点是 $i$ 的方案数。那么有 $\displaystyle f[i]=1+\sum_{x_j<x_i,y_j<y_i}f[j]$ 。

直接用树状数组优化 DP 即可,时间复杂度 $O(n\log n)$ 。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=1e9+7;

int n,m,cnt,top;
int a[N],b[N],S[N];
pair<int,int> p[N];
int f[N];

inline int cmp(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    else return a.second>b.second;
}

int c[N];
inline int lowbit(int x) { return x&-x; }
inline int query(int x) { int res=0;
    for (;x;x-=lowbit(x)) res=(res+c[x])%mod;
    return res;
}
inline void add(int x,int y) {
    for (;x<=top;x+=lowbit(x)) c[x]=(c[x]+y)%mod;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=m;++i) b[i]=read();
    for (re int i=1;i<=n;++i) {
        if (a[i]<=b[1]||a[i]>=b[m]) continue;
        int x=lower_bound(b+1,b+m+1,a[i])-b;
        if (b[x]==a[i]) continue;
        p[++cnt]=make_pair(a[i]-b[x-1],b[x]-a[i]);
        S[++top]=b[x]-a[i];
    }
    sort(S+1,S+top+1); top=unique(S+1,S+top+1)-S-1;
    for (re int i=1;i<=cnt;++i)
        p[i].second=lower_bound(S+1,S+top+1,p[i].second)-S;
    sort(p+1,p+cnt+1,cmp); cnt=unique(p+1,p+cnt+1)-p-1;
    f[0]=1;
    for (re int i=1;i<=cnt;++i)
        f[i]=query(p[i].second-1)+1,add(p[i].second,f[i]);
    int ans=0;
    for (re int i=0;i<=cnt;++i) ans=(ans+f[i])%mod;
    printf("%d\n",ans);
    return 0;
}