矩形查询的模板。
顺便一提原题面非常精彩。

Problem

https://www.luogu.org/problemnew/show/P2163
n 个坐标点，m 次询问，问某个矩形里有多少个点。

Solution

本题理应是一道 KDT 模板。
然而数据范围大，离线用 CDQ 分治。
每个询问拆成四个第三维坐标为 1 的点（二维前缀和），普通点第三维坐标为 0。
坐标离散化，作稍有改动的三维偏序即可。
无需去重。
细节就不说了。

Code

// Code by ajcxsu
// Problem: gardener's problem

#include<bits/stdc++.h>
using namespace std;

const int N=3e6+10;
struct Node {
    int x,y,z,id,ex;
} arr[N], cac[N];
bool cmp(const Node &a, const Node &b) { return a.x==b.x?(a.y==b.y?a.z<b.z:a.y<b.y):a.x<b.x; }
int num[N], p, np;
map<int, int> ma;
int ans[N];

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

void dfs(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    dfs(l, mid), dfs(mid+1, r);
    int i=l, j=mid+1, k=l, cnt=0;
    while(i<=mid && j<=r) {
        if(arr[i].y<=arr[j].y) cac[k++]=arr[i], cnt+=!arr[i++].z;
        else {
            cac[k++]=arr[j];
            ans[arr[j].id]+=cnt*arr[j].ex;
            j++;
        }
    }
    while(i<=mid) cac[k++]=arr[i++];
    while(j<=r) cac[k++]=arr[j], ans[arr[j].id]+=cnt*arr[j].ex, j++;
    for(int i=l;i<=r;i++) arr[i]=cac[i];
}

int main() {
    int n, m;
    gn(n), gn(m);
    for(int i=1;i<=n;i++)
        ++p, gn(arr[p].x), gn(arr[p].y), num[np++]=arr[p].x, num[np++]=arr[p].y;
    int x1, y1, x2, y2;
    for(int i=1;i<=m;i++) {
        gn(x1), gn(y1), gn(x2), gn(y2);
        x1--, y1--;
        arr[++p].x=x1, arr[p].y=y1, arr[p].ex=1, arr[p].id=i, arr[p].z=1;
        arr[++p].x=x1, arr[p].y=y2, arr[p].ex=-1, arr[p].id=i, arr[p].z=1;
        arr[++p].x=x2, arr[p].y=y1, arr[p].ex=-1, arr[p].id=i, arr[p].z=1;
        arr[++p].x=x2, arr[p].y=y2, arr[p].ex=1, arr[p].id=i, arr[p].z=1;
        num[np++]=x1, num[np++]=x2, num[np++]=y1, num[np++]=y2;
    }
    sort(num, num+np);
    np=unique(num, num+np)-num;
    for(int i=0;i<np;i++) ma[num[i]]=i+1;
    for(int i=1;i<=p;i++) arr[i].x=ma[arr[i].x], arr[i].y=ma[arr[i].y];
    sort(arr+1, arr+1+p, cmp);
    dfs(1,p);
    for(int i=1;i<=m;i++)
        printf("%d\n", ans[i]);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2163.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆