题解：P15847 [NOISG 2026 Finals] 猴子 / Monkeys

zsjaaaxy · 2026-07-22 15:08:02 · 题解

solution

考虑何时两个点产生贡献，不妨设容易发现当且仅当两点重合或两点奇偶性相同且相向而行且距离不超过 2k。

先计算重合的，然后分奇偶性记录方向向右的，然后枚举每个方向向左的二分查找有多少个满足条件的点即可。

时间复杂度 O(n \log n)。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000;
int n,k,ans=0;
vector<int> s[2];
map<int,int> mp;
struct node
{
    int p;
    char d;
}a[N];
bool operator <(node n1,node n2)
{
    return n1.p<n2.p;   
} 
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].p;
        mp[a[i].p]++;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].d;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        if(mp[a[i].p])
        {   
            ans+=mp[a[i].p]*(mp[a[i].p]-1)/2;
            mp[a[i].p]=0;
        }
        if(a[i].d=='R')
        {
            s[a[i].p%2].push_back(a[i].p);
        }
    }
    sort(s[0].begin(),s[0].end()),sort(s[1].begin(),s[1].end());
    for(int i=1;i<=n;i++)
    {
        if(a[i].d=='L')
        {
            int pqh1=lower_bound(s[a[i].p%2].begin(),s[a[i].p%2].end(),a[i].p)-s[a[i].p%2].begin();
            int pqh2=lower_bound(s[a[i].p%2].begin(),s[a[i].p%2].end(),a[i].p-2*k)-s[a[i].p%2].begin();
            ans+=pqh1-pqh2;
        }
    }
    cout<<ans;
    return 0;
}