二维数点问题

二维数点在OI中有着广泛的应用,很多题目正解或其部分分都可以转化为二维数点的模型.

一般性的静态二维数点问题:

给出平面上的\(n\)个点的坐标\(P_i(x_i,y_i)\),\(Q\)次查询,每次查询\((a,b,c,d)\),表示,求在矩形\((a,b),(c,d)\)中的点数

\(a,b,c,d,n <= 10^5\)

数据范围都是\(10^5\)级别的,我们就不能运用前缀和去解决问题了

但是可以运用二维前缀和的思想

我们设\(S(x,y)\)表示\((0,0)(x,y)\)这个矩阵中点的个数

每次询问的答案很明显是

\(S(c,d) - S(a - 1,d) - S(c,b - 1) + S(c - 1,d - 1)\)

我们就将个询问拆成这四部分分解维护

之后用扫描线的思想维护树状数组,大体思路是这样的:

先将所有的点,和我们拆分完成之后的询问全部按照\(x\)进行排序

(对于\(x\)这一维)之后每次扫到一个询问的\(x\),就把当前还剩下的小于等于\(x\)的点全部加上

加上什么呢,这个点在\(y\)这一维的贡献(可能有点绕)

就是我们把树状数组的下标看做权值

当前影响的是\(1- y\)这个范围的点.所以在树状数组上将这个区间的贡献\(+1\)

例题BZOJ1935/Luogu2163[SHOI2007]园丁的烦恼

就是上面的问题,但是注意一下坐标有\((0,0)\),而树状数组\(0\)没有意义,所以将所有坐标整体\(+1\)

另外这道题坐标范围是\(10^7\)级别的,按理来说应当对\(y\)这一维离散化,但是树状数组跑的飞快,就不管了,反正空间不会炸.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e5 + 5;
int c[10000003];
int n,m;
int ans[N];
struct tree{
    int x,y;    
}v[N];
struct ques{
    int x,y;
    int id,opt; 
    ques(int xx = 0,int yy = 0,int num = 0,int o = 0){
        x = xx,y = yy,id = num,opt = o;
    }
}q[N << 2];
inline char nc(){
    #define SIZE 1000000+5
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
}
inline int read(){
    int x = 0;char ch = nc();int flag = 0;
    while(!isdigit(ch)){
        if(ch == '-') flag = -1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
    return x;
}
inline bool cmp1(tree x,tree y){
    return x.x < y.x;   
}
inline bool cmp2(ques x,ques y){
    return x.x < y.x;
} 
inline void updata(int x,int val){
    for(;x <= n;x += x & -x) c[x] += val;   
}
inline int query(int x){
    int res = 0;
    for(;x;x -= x & -x) res += c[x];
    return res; 
}
int main(){
    int cnt = 0;
    n = read(),m = read();
    for(int i = 1;i <= n;++i)
    v[i].x = read() + 1,v[i].y = read() + 1;
    for(int i = 1;i <= m;++i){
        int x1 = read() + 1,y1 = read() + 1,x2 = read() + 1,y2 = read() + 1;
        q[++cnt] = ques(x2,y2,i,1);
        q[++cnt] = ques(x1 - 1,y2,i,-1);
        q[++cnt] = ques(x2,y1 - 1,i,-1);
        q[++cnt] = ques(x1 - 1,y1 - 1,i,1);
    }
    sort(v + 1,v + n + 1,cmp1);
    sort(q + 1,q + cnt + 1,cmp2);
    int now = 1;
    for(int i = 1;i <= cnt;++i){
        while(v[now].x <= q[i].x && now <= n) 
            updata(v[now].y,1),now++;
        ans[q[i].id] += q[i].opt * query(q[i].y);
    //  printf("%d %d\n",query(q[i].y),q[i].id);
    }
    for(int i = 1;i <= m;++i) printf("%d\n",ans[i]);
    return 0;   
}