题解 P2163 [SHOI2007] 园丁的烦恼

· · 题解

题解 P2163 [SHOI2007] 园丁的烦恼

写了很久的归并板子发现 l>r 必须判……调了 1h+，警钟长鸣。

一种比较特别的思路。

前排提醒：本题解与其发布前该题的所有题解均不同，为归并排序树做法，并附带归并排序树的简要说明。

题意

给定平面直角坐标系中 n 个点和 m 次询问，每次询问给出 x1,y1,x2,y2，求以 (x1,y1) 为左下角，(x2,y2) 为右上角的矩形内包含的点数。边界上也算。

数据范围：n,m \le 5 \times 10^5，所有的坐标不超过 10^7。

做法

上周六的 ABC339G 给了我想出这个做法的灵感。题解

这个做法主要的优势：

但常数较大，不开 O2 无法通过。

众所周知，两条平行于 y 轴的直线和两条平行于 x 轴的直线可以截出一个矩形，像这样：

然后往上撒几个点：

首先我们只考虑一次询问。

先给点按横坐标排个序（点上标的数字），然后二分确定点的范围（标红的点）：

接着把这些点拎出来再按纵坐标排一次（红色点上带括号的数字）：

就可以二分查找询问的纵坐标得到答案了。

因为要排序，所以一次询问的复杂度最坏是 O(n \log n)，于是总复杂度成了 O(nm \log n)，无法通过。因此只能考虑优化第二次排序。

于是受刚才提到的题目启发，我们在第一次排序的基础上，建出类似于线段树的结构，其中每个节点存这次调用归并排序函数后被排序的部分的顺序。这么说不太好理解，那就继续上图：

注：图中给出点的横坐标只是为了方便大家从前面的图中找点。实际写代码时建议在按横坐标排完序后把结构体拆成两个数组，归并排序时只操作纵坐标，因为这样方便使用 STL 二分查找。

图中 dep 同代码中 msort、query 两个函数中的 dep 参数，为函数递归的深度。每个框为一个节点。

接下来把要查询的区间（浅黄色）分成几个尽可能大的黑框区间（金黄色）：

然后在每个区间中二分查找，就得到了符合要求的点的个数（绿色）：

分成的区间个数是 \log n 级别的，二分查找又是 \log n 的，因此其复杂度为 O(m \log^2 n)，为 2\times10^8，但显然是跑不满的，加快读快输并吸氧后最慢点可跑进 800 ms，其他点小于 100 ms。

注意归并排序时判断 l>r 的情况，否则可能在第四个点 MLE。

代码

//省略头文件及快读快输
struct point{
    ll x,y;
};
inline bool cmp(point x,point y){//按 x 排序
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
ll n,m,b,c,d,e,ax[500010],ay[500010],f[20][500010];
point a[500010];
inline void msort(ll l,ll r,ll dep){//归并板子，但答案存到 f 数组里
    if(l>=r){
        f[dep][l]=ay[l];
        return ;
    }
    ll mid=(l+r)>>1;
    msort(l,mid,dep+1);
    msort(mid+1,r,dep+1);
    ll p=l,p1=l,p2=mid+1;
    while(p1<=mid&&p2<=r){
        if(f[dep+1][p1]<f[dep+1][p2]){
            f[dep][p]=f[dep+1][p1];
            p1++;
        }
        else{
            f[dep][p]=f[dep+1][p2];
            p2++;
        }
        p++;
    }
    while(p1<=mid){
        f[dep][p]=f[dep+1][p1];
        p1++;
        p++;
    }
    while(p2<=r){
        f[dep][p]=f[dep+1][p2];
        p2++;
        p++;
    }
}
inline ll query(ll l,ll r,ll l2,ll r2,ll x,ll y,ll dep){
    ll mid=(l2+r2)>>1;
    if(l==l2&&r==r2){
        return upper_bound(f[dep]+l2,f[dep]+r2+1,y)-lower_bound(f[dep]+l2,f[dep]+r2+1,x);//统计答案
    }
    if(l>mid){//完全在左半边
        return query(l,r,mid+1,r2,x,y,dep+1);
    }
    if(r<=mid){//完全在右半边
        return query(l,r,l2,mid,x,y,dep+1);
    }
    return query(l,mid,l2,mid,x,y,dep+1)+query(mid+1,r,mid+1,r2,x,y,dep+1);//两边都有，从 mid 处切开
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++){
        //将排序后的结构体拆成两个数组，方便后面二分查找
        ax[i]=a[i].x;
        ay[i]=a[i].y;
    }
    msort(0,n-1,0);
    while(m--){
        cin>>b>>c>>d>>e;
        ll l=lower_bound(ax,ax+n,b)-ax;
        ll r=upper_bound(ax,ax+n,d)-ax-1;
        if(r<l)cout<<0<<endl;
        else cout<<query(l,r,0,n-1,c,e,0)<<endl;
    }
    return 0;
}