首页 学习笔记

# 二维数点

顾名思义，就是在一个二维平面内数一个矩形内有多少个点。

例题：P2163 [SHOI2007]园丁的烦恼

# 树状数组

根据二维前缀和的算法，把矩形和改成求 4 个坐标 (x,y)(x,y) 到原点的矩形和，再容斥计算答案。

首先对坐标离散化，按 xx 轴排序，从左到右依次插入每个点。对 yy 轴维护一个树状数组。

  • 插入：在相应的 yy 轴坐标上加 1.

  • 查询：由于按 xx 轴从小到大插入的，树状数组内的点都在当前的 xx 左边。所以查询小于当前 yy 的和就是 (0,0)(0, 0) 到 (x,y)(x, y) 的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//Lugou P2163

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2.5e6 + 10;
int n, m;
struct node{
    int x, y, id, typ;
    inline bool operator < (const node &b) const{
        return x != b.x ? x < b.x : (y != b.y ? y < b.y : id < b.id);
    }
}p[N];
int b[N], ans[N];

int c[N];

inline void add(int x, int y){
    for(; x <= n; x += x & (-x)) c[x] += y;
}

inline int qry(int x){
    int res = 0;
    for(; x; x -= x & (-x)) res += c[x];
    return res;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        p[i] = (node){read(), read(), 0, 0};
    for(int i = 1; i <= m; ++i){
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        p[++n] = (node){x1 - 1, y1 - 1, i, 1};
        p[++n] = (node){x1 - 1, y2, i, -1};
        p[++n] = (node){x2, y1 - 1, i, -1};
        p[++n] = (node){x2, y2, i, 1};
    }
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; ++i) b[i] = p[i].y;
    sort(b + 1, b + 1 + n);
    int tot = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; ++i){
        int pos = lower_bound(b + 1, b + 1 + tot, p[i].y) - b;
        if(p[i].id) ans[p[i].id] += p[i].typ > 0 ? qry(pos) : -qry(pos);
        else add(pos, 1);
    }
    for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
    return 0;
}

# 线段树

很显然扫描线也是可以处理这个问题的。

还是先把所有的点离散化。

对 yy 轴维护线段树，扫描线横着扫。把一个询问 (x1,y1),(x2,y2)(x_1, y_1), (x_2, y_2) 拆成两个部分，减去 0∼x1−10 \sim x_1 - 1 再加上 0∼x20 \sim x_2。

x1x_1 和 x2x_2 的贡献分两次计算。

先按 x1x_1 从小到大排序，对于询问 ii 把 q[i−1].x1∼q[i].x1q[i - 1].x_1 \sim q[i].x_1 的点插到线段树里，然后查询答案。

计算 x2x_2 的贡献时再按 x2x_2 从小到大排序，其他同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define pb push_back
#define find(x) lower_bound(b + 1, b + 1 + tot, x) - b
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 5e5 + 10;
int n, m;
struct node{
    int x, y;
    inline bool operator < (const node &b) const{
        return x != b.x ? x < b.x : y < b.y;
    }
}p[N];
struct Query{
    int x1, y1, x2, y2, id;
    inline bool operator < (const Query &b) const{
        return x1 < b.x1;
    }
}q[N];
int b[N << 3], tot;

inline bool cmp(Query a, Query b) {return a.x2 < b.x2;}

int sum[N << 3], ans[N];

inline void pushup(int rt){
    sum[rt] = sum[ls] + sum[rs];
}

inline void update(int x, int l, int r, int rt){
    if(l == r) return sum[rt]++, void();
    if(x <= mid) update(x, l, mid, ls);
    else update(x, mid + 1, r, rs);
    pushup(rt);
}

inline int query(int L, int R, int l, int r, int rt){
    if(L > r || R < l) return 0;
    if(L <= l && r <= R) return sum[rt];
    return query(L, R, l, mid, ls) + query(L ,R, mid + 1, r, rs);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        p[i] = (node){read() + 1, read() + 1}, b[++tot] = p[i].x, b[++tot] = p[i].y;
    for(int i = 1; i <= m; ++i){
        q[i] = (Query){read() + 1, read() + 1, read() + 1, read() + 1, i};
        b[++tot] = q[i].x1, b[++tot] = q[i].y1, b[++tot] = q[i].x2, b[++tot] = q[i].y2;
    }
    sort(b + 1, b + 1 + tot);
    tot = unique(b + 1, b + 1 + tot) - b - 1;
    for(int i = 1; i <= n; ++i)
        p[i].x = find(p[i].x), p[i].y = find(p[i].y);
    for(int i = 1; i <= m; ++i){
        q[i].x1 = find(q[i].x1), q[i].y1 = find(q[i].y1);
        q[i].x2 = find(q[i].x2), q[i].y2 = find(q[i].y2);
    }
    sort(p + 1, p + 1 + n);
    sort(q + 1, q + 1 + m);
    int pos = 0;
    for(int i = 1; i <= m; ++i){
        while(pos < n && q[i].x1 > p[pos + 1].x) update(p[++pos].y, 1, n, 1);
        ans[q[i].id] -= query(q[i].y1, q[i].y2, 1, n, 1);
    }
    memset(sum, 0, sizeof(sum)), pos = 0;
    sort(q + 1, q + 1 + m, cmp);
    for(int i = 1; i <= m; ++i){
        while(pos < n && q[i].x2 >= p[pos + 1].x) update(p[++pos].y, 1, n, 1);
        ans[q[i].id] += query(q[i].y1, q[i].y2, 1, n, 1);
    }
    for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
    return 0;
}

# 主席树

对 yy 轴维护主席树，按 xx 轴从小到大依次插入点。

查询时，查询权值在 y1∼y2y_1 \sim y_2 的 rt[x2]−rt[x1−1]rt[x_2] - rt[x_1 - 1] 即可。

个人认为主席树这样的想法类似于扫描线，而且实现比线段树实现优美的多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define pb push_back
#define mid ((l + r) >> 1)

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 5e5 + 10;
const int M = 1e7;
int n, m;
struct node{
    int x, y;
    inline bool operator < (const node &b) const{
        return x < b.x;
    }
}a[N];
int b[N], tot;
int rt[N << 5], ls[N << 5], rs[N << 5], sum[N << 5];
int cnt;

inline int update(int pre, int l, int r, int x){
    int p = ++cnt;
    ls[p] = ls[pre], rs[p] = rs[pre], sum[p] = sum[pre] + 1;
    if(l == r) return p;
    if(x <= mid) ls[p] = update(ls[pre], l, mid, x);
    else rs[p] = update(rs[pre], mid + 1, r, x);
    return p;
}

inline int query(int p, int l, int r, int L, int R){
    if(!p || L > r || R < l) return 0;
    if(L <= l && r <= R) return sum[p];
    return query(ls[p], l, mid, L, R) + query(rs[p], mid + 1, r, L, R);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = (node){read(), read()}, b[i] = a[i].x;
    sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n), b[n + 1] = M;
    for(int i = 1; i <= n; ++i) rt[i] = update(rt[i - 1], 0, M, a[i].y);
    for(int i = 1; i <= m; ++i){
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        x1 = lower_bound(b + 1, b + 1 + n, x1) - b;
        x2 = upper_bound(b + 1, b + 1 + n, x2) - b - 1;
        write(query(rt[x2], 0, M, y1, y2) - query(rt[x1 - 1], 0, M, y1, y2)), puts("");
    }
    return 0;
}

更新于 阅读次数 次