题解 P3088 【[USACO13NOV]Crowded Cows S】

· · 题解

作为最优解我来发个题解

单调队列不是O(n)的吗?加上排序应该也很快啊

但是线段树也不慢，像我就轻轻松松拿了个rk1

不过楼顶那篇题解跑的好快啊，62ms又破了我纪录

闲话少叙，进入正题

线段树作为最优的一种可以动态的访问区间最值的数据结构，比树状数组更快，比Spare Table使用更广泛（带修），比单调队列更具有随机访问性质，不需要滑动窗口这样询问有一定规律。

线段树绝对是最强力的数据结构，权值线段树可以吊打平衡树，函数式线段树/可持久化线段树可以碾压树状数组套平衡树（少至少一个log）,极端的，替罪羊树套权值线段树可以爆锤块状链表套权值块状数组（nlog²n < n√n）

此题的数据规模较大，暴力肯定死翘翘，卡过去的是神仙。

x(i)太大，又不好离散化，我们考虑用lower_bound/
upper_bound来定位区间端点。

不过要先排个序，把节点简单用数组下标离散一下，把线段树的位置定好，然后单点修改或整体建树。

查询i时找h[i]-D~h[i]+D区间，二分一下即可。

找到区间后找一个最大值S（线段树维护）。

如果S>=h[i]*2,则ans++。

最后输出ans。

喜闻乐见的代码。

很多地方是可以优化的（我太懒了不想再优化），大家试试能不能卡卡常破纪录。

#include <cstdio>
#include <algorithm>
using namespace std;
void read(int &x){
    char c=getchar();
    int k=1;
    while(c<'0'||c>'9') {if(c=='-') k=-1;c=getchar();}
    for(x=0;c>='0'&&c<='9';c=getchar())
    x=x*10+c-'0';
    x*=k;
}
const int N=200005;
int n,p,q,m,k,y,x,s,ans,c,mx,d,b[N];
struct fox{
    int wei,high;
}a[N*4];
bool operator<(fox x,fox y){
    return x.wei<y.wei;
}
int tree[N];
inline void change(int k,int l,int r,int x,int y){
    if(l>x||r<x) return;
    if(l==x&&l==r){
        tree[k]=y;
        return;
    }
    int mid=l+r>>1;
    change(k<<1,l,mid,x,y);
    change(k<<1|1,mid+1,r,x,y);
    tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
inline int query(int k,int l,int r,int x,int y){
    if(l>r) return 0;
    if(l>y||r<x) return 0;
    if(x<=l&&r<=y) return tree[k];
    int mid=l+r>>1,s=query(k<<1,l,mid,x,y);
    s=max(query(k<<1|1,mid+1,r,x,y),s);
    return s;
}
int main(){
    read(n);read(m);
    for(register int i=1;i<=n;i++){
        read(a[i].wei);read(a[i].high);
    }
    sort(a+1,a+n+1);
    for(register int i=1;i<=n;++i){
        change(1,1,n,i,a[i].high);
        b[i]=a[i].wei;
    }
    for(register int i=1;i<=n;i++){
        p=q=b[i];
        p-=m;p=max(p,0);
        q+=m;
        k=lower_bound(b+1,b+n+1,p)-b;
        c=upper_bound(b+1,b+n+1,q)-b-1;//-1很重要
        s=query(1,1,n,k,i);d=query(1,1,n,i,c);
        if(min(s,d)>=a[i].high*2){
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}