题解：P1296 奶牛的耳语

· · 题解

前言

这题自从被我 hack 之后已经过去 3 天了，居然还能交题解，再补一个分块做法。

题解

序列是无序的，先排个序。排完序后，把序列分成 \sqrt n 块，每一块都找出一个最大值。因为序列有序，所以最大值肯定是这一块的最后一个数。

如果我们使用暴力做法，我们需要统计每头奶牛后面有多少奶牛与这头奶牛距离小于等于 d，很慢。我们可以枚举每块，如果这一块的最大值都比 d 小或相等，那这一块的其他数就更不用说了。复杂度来到了 O(n \sqrt n)。

下面是这种思路的代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,d;
const int N=1000005;
int a[N],len;
int id[N],maxn[N];
int l[N],r[N];//每块的左右端点 
int lst;//最后一块的编号 
ll ans=0;
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n>>d;
    len=sqrt(n);//块长 
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);//排序 
    for(int i=1;i<=n;i++){
        id[i]=i/len+1;//块编号
        lst=id[i];
        if(id[i]!=id[i-1]){//新的一块 
            l[id[i]]=i;//这一块的左端点为当前点 
            r[id[i]-1]=i-1;//上一块的右端点为上一个点 
            maxn[id[i]-1]=a[i-1];//上一块的最大值为上一个数字 
        }
    }
    r[lst]=n;
    maxn[lst]=a[n];
    for(int i=1,t;i<=n;i++){
        bool flag=0;
        for(int j=i+1;j<=r[id[i]];j++){//遍历这一块其他元素 
            if(a[i]+d>=a[j]) ans++;
            else{
                flag=1;//找到比它大的了
                break; 
            }
        }
        if(flag) continue;
        for(int j=id[i]+1;j<=lst;j++){//遍历后面所有块 
            if(maxn[j]<=a[i]+d) ans+=r[j]-l[j]+1;//加上这一块的大小
            else{
                //这一块有比它大的
                for(int k=l[j];k<=r[j];k++){
                    if(a[k]<=a[i]+d) ans++;
                    else break;
                }
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/16 9:22:10
PROBLEM:P1296
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

还能小优化一下：把 O(\sqrt n) 枚举块的过程转化为 O(\log n) 的二分。（但怎么更慢了……）

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,d;
const int N=1000005;
int a[N],len;
int id[N],maxn[N];
int l[N],r[N];//每块的左右端点 
int lst;//最后一块的编号 
ll ans=0;
bool check(int i,int x){
    if(maxn[x]<=a[i]+d) return 1;
    else return 0;
}
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n>>d;
    len=sqrt(n);//块长 
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);//排序 
    for(int i=1;i<=n;i++){
        id[i]=i/len+1;//块编号
        lst=id[i];
        if(id[i]!=id[i-1]){//新的一块 
            l[id[i]]=i;//这一块的左端点为当前点 
            r[id[i]-1]=i-1;//上一块的右端点为上一个点 
            maxn[id[i]-1]=a[i-1];//上一块的最大值为上一个数字 
        }
    }
    maxn[lst+1]=2147483647;
    l[lst+1]=n+1;
    r[lst]=n;
    maxn[lst]=a[n];
    for(int i=1;i<=n;i++){
        bool flag=0;
        for(int j=i+1;j<=r[id[i]];j++){//遍历这一块其他元素 
            if(a[i]+d>=a[j]) ans++;
            else{
                flag=1;//找到比它大的了
                break; 
            }
        }
        if(flag) continue;
        //二分，启动！！！ 
        int lt=id[i]+1,rt=lst;
        while(lt<=rt){
            int mid=(lt+rt)>>1;
            if(check(i,mid)) lt=mid+1;
            else rt=mid-1;
        }
        ans+=l[lt]-r[id[i]]-1;
        for(int j=l[lt];j<=r[lt];j++){
            if(a[j]<=a[i]+d) ans++;
            else break;
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/16 9:22:10
PROBLEM:P1296
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

后记

本蒟蒻的第 26 篇题解，也是我第一次一道题交两篇题解。

自己 hack 的题写题解就是爽！