AT_arc101_d [ARC101F] Robots and Exits题解

sword7level · 2026-10-22 21:04:10 · 题解

题意：

题目是说有 n 个机器人 m 个洞，每次所有机器人统一移动，若某个机器人移到某个洞该机器人退出，设该机器人编号为 i 该洞编号为 j，记 a_i=j，求数组 a 的可能数量。

题目分析：

首先我们考虑机器人不能跳过某个洞，那么很显然每个机器人只能从它坐标的相邻两个洞离开。我们可以先把只有一边有洞的机器人剔除，因为它们只有一种贡献。对于两边都有洞的机器人，设向左移出的状态为 0，向右移出的状态为 1，那么题目相当于是在计数 a 这个 01 序列的个数。这个序列有一些限制，这些限制与每个机器人与左右两相邻洞的距离有关，我们记二元组 (x_i,y_i) 表示第 i 个机器人到左边最近洞和右边最近洞的距离。若二元组完全相等，那么它们的 01 状态一定相等，我们可以把它们视作一个点，所以先去重。

这里需要注意，不能把两个机器人的限制静态地写成“若 i 走右、j 走左，则必须同时满足 x_i>x_j 且 y_i<y_j”，因为机器人消失有先后，不能只做两两静态比较。正确的方式是看整体移动过程：设当前已经向左扩展到的最大距离为 L，向右扩展到的最大距离为 R。初始时 L=R=0，每次操作只会让 L 或 R 增大，因此整个移动过程可以看成 (L,R) 平面中一条从 (0,0) 出发、只能向右或向上走的单调路径。

对每个机器人 i，它对应平面上的点 (x_i,y_i)。如果路径先到达竖线 L=x_i，即到达时 R<y_i，那么机器人 i 先碰到左出口，走左边；如果路径先到达横线 R=y_i，即到达时 L<x_i，那么机器人 i 先碰到右出口，走右边。因此，一条单调路径会决定每个机器人走左还是走右：路径左上方的点走左，路径右下方的点走右，路径经过的点约定走右。

但同一个方案可能对应多条路径，例如全走左时，路径可以先向右走一段再向上，也可以一直向右走。为了得到一一对应，我们取规范折线：在所有能分开该方案的单调路径中，取最靠左上的一条，也就是取所有走右点的左上包络。这样得到的规范折线由方案唯一确定。反过来，任意一条规范折线也唯一确定一种合法选择：折线左上方机器人走左，右下方机器人走右，折线上的点走右。因此合法方案与规范折线一一对应。

规范折线经过的点按 x、y 都严格递增，也就是一个严格上升序列。空序列对应折线不经过任何点，此时所有点都在折线左上方，全部走左，也是一种合法方案。于是合法方案与严格上升子序列一一对应。

因此，把所有去重后的二元组按 x 升序排序；若 x 相同，则按 y 降序排序，避免同一个 x 的两个点同时被选入严格上升序列。取出排序后的 y 序列，答案就是该序列的严格上升子序列个数，包含空序列。

设排序后的 y 序列为 b_1,b_2,\dots,b_k。令 dp_i 表示以 b_i 结尾的严格上升子序列个数，则

其中前面的 1 表示只选 b_i 自己。最终答案为

前面的 1 表示空序列。用树状数组维护 b_i 的前缀和即可，每次

再把 dp_i 加到位置 b_i 上。复杂度为 O(k\log k)，其中 k\le N，最后对 10^9+7 取模。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10,mod=1e9+7;
int n,m,a[N],b[N],maxn=0;
ll dp[N];
pair<int,int> dot[N];
struct BIT{
    ll tree[N];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void add(int x,ll k){
        while(x<=maxn){
            (tree[x]+=k)%=mod;
            x+=lowbit(x);
        }
    }
    inline ll query(int x){
        ll res=0;
        while(x){
            (res+=tree[x])%=mod;
            x-=lowbit(x);
        }
        return res;
    }
}tree;
vector<int> x,y;
inline bool cmp(pair<int,int> x,pair<int,int> y){
    if(x.first==y.first) return x.second>y.second;
    return x.first<y.first;
}
signed main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    freopen("esc.in","r",stdin);
    freopen("esc.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]<b[1] || a[i]>b[m]) continue;
        int pos=lower_bound(b+1,b+1+m,a[i])-b;
        dot[++cnt]={a[i]-b[pos-1],b[pos]-a[i]};
        x.push_back(dot[cnt].first);
        y.push_back(dot[cnt].second);
    }
    sort(x.begin(),x.end());sort(y.begin(),y.end());
    x.erase(unique(x.begin(),x.end()),x.end());
    y.erase(unique(y.begin(),y.end()),y.end());
    for(int i=1;i<=cnt;i++){
        dot[i].first=lower_bound(x.begin(),x.end(),dot[i].first)-x.begin()+1;
        dot[i].second=lower_bound(y.begin(),y.end(),dot[i].second)-y.begin()+1;
    }
    maxn=y.size();
    sort(dot+1,dot+1+cnt,cmp);
    cnt=unique(dot+1,dot+1+cnt)-dot-1;
    ll ans=1;
    for(int i=1;i<=cnt;i++){
        ll add=tree.query(dot[i].second-1)+1;
        (ans+=add)%=mod;
        tree.add(dot[i].second,add);
    }
    cout<<ans;
    return 0;
}