水篇题解。

感觉已经好久好久没写过黄题题解了吧。

日常看错题之当我以为一个猴子在点 $x$ 时要以 $d_x$ 的方向移动然后思考许久无果看了眼样例发现：哦我又看错题了。

上一次看错题，被某个巨佬扯出来搞到一个紫题，吓哭了。

感觉是比较一眼的题目。当然这建立在你题看对了的情况下。

一个点只会朝着一个方向永远移动，所以相遇只有两种情况：

1. 相向而行的相遇：

   • 这要求两点中，最初位于左侧的点是往右走，最初位于右侧的点是往左走。
   • 且两点之间的间隔 $y-x$ 为偶数（奇数的话会擦边而过，但无法在整点上相遇），还要求 $y-x \le 2k$（否则在 $k$ 时间内也无法相遇）。

2. 同向而行的相遇：

   • 正常来讲，同向而行能相遇是因为一个快一个慢。
   • 但是这道题中，所有点的移动速度都是 $1$，这也就不存在“追及”情况了，也就是说，两个同向而行的点能相遇，当且仅当其初始点位置相同。也就是两个本质一样的点。

那么就可以做了，维护三个数组 $R,L_0,L_1$，分别存储：

• $R$ 存储所有往右走的点；
• $L_0$ 存储所有往左走且初始点位为偶数的点；
• $L_1$ 存储所有往左走且初始点位为奇数的点。

对这三个序列升序排序之后，就很好做了。

相向而行的，枚举 $R$ 中的点 $x$，在对应的 $L$ 数组（根据 $x$ 的奇偶性判断是 $L_0$ 还是 $L_1$）内二分到对应区间 $[x,x+2k]$ 所含有的点数，累加答案即可。

同向而行的，只需要分往左还是往右，对下标开两个桶记录一下，贡献 $\sum \frac{cnt(cnt-1)}{2}$。

整个还是非常好做的。

代码里有一些辅助理解的注释喵。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
LL n,k,p[N],Ans;//不开 LL 见祖宗 
vector<LL> L[2],R;//其实应该开数组的但是实在不想写三个长度变量
map<LL,LL> t[2];//充当桶解决重复点的问题 
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)p[i]=read();
    //注意 vector 的下标从 0 开始！！ 
    for(int i=1;i<=n;i++){
        char opt;cin>>opt;
        if(opt=='R')R.pb(p[i]);
        else L[p[i]&1].pb(p[i]);
        //按点位的奇偶性分类
        //因为中间间隔路程只能是偶数（两只猴子都在移动） 
        t[(opt=='L'?0:1)][p[i]]++;//塞进桶 
    }
    sort(R.begin(),R.end());
    sort(L[0].begin(),L[0].end());
    sort(L[1].begin(),L[1].end());
    for(LL x:R){
        //以往右走的为指定物，找右侧奇偶性匹配且距离不长的猴子 
        int o=(x&1);//奇偶性判定
        int l=lower_bound(L[o].begin(),L[o].end(),x)-L[o].begin();
        int r=upper_bound(L[o].begin(),L[o].end(),x+2*k)-L[o].begin()-1;
        //找到能相遇的猴子的左右端点
        //注意右端点要用 upper_bound 最后 -1 因为可能有重复！ 
        Ans+=r-l+1;//累加答案 
    }
    for(int o=0;o<2;o++)//左右方向 
        for(auto [x,y]:t[o])Ans+=y*(y-1)/2;//累加答案
    cout<<Ans<<"\n"; 
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！