算法简介：一箭双丘丘！

其实吧，二维数点单独来讲不能算是一个算法，它泛指一种在二维平面上数有多少个点或类似的问题。涉及的数据结构比较广，也算是比较杂的一篇文章了。

二维数点大概有两种：静态的和动态的。根据题目给出的动静之分，我们可以大致知道用什么数据结构，一般来讲，单点动态的我们偏向用树状数组等操作，多点动态应该除了线段树没谁了；还有就是静态，一般来讲非必要情况都是树状数组，毕竟码量低，然后有时候会有扫描线的题目。扫描线还没讲，先挖个坑罢（

这里就挑几个二维数点的实例看看，大概意会一下。

算法演示：一触即发

例题一：烧起来啦！

大秦为你打开题目传送门

题面翻译

平面上有n个点，还有一个长度为⑨的数列$a_1,a_2……a_9$满足$\sum_{i=1}^na_i=n $

你需要画两条水平直线和两条竖直直线将平面划为⑨各部分，每部分点数记为$b_1,b_2……b_9$

要求b是a的一种排列

你的直线坐标可以是实数，构造一组解，或无解（输出-1）

题目思路

虽然说他是紫题，但是太简单了，不必有任何压力（我是一眼秒的

让你把一堆点分成一个九宫格（其实是找九宫格中间的四条分界线）然后每一个格子一定是给出序列的一个排列，其实就是说九宫格里的数字和给出的排列是一一对应的。

那么上来先抓关键词：排列，一眼丁真，数组长度只有九，不难想到直接暴力枚举排列 $9! = 362880$ 。时限是正常的时间限制，也就是说我们要快速的判断一个排列对不对，留给我们的时间还有最多两三百的样子。

那么为什么说这是一个二维数点，我们可以想到一个确定九宫格的方式（我是直接就想到了）前缀和。大概是下面这样：

前缀和思想数点图示

我们一定可以吧平面上的点，划分为一些前缀矩形，这些前缀矩形的点的数量一定是可以找到和算出来的排列一样的，不然就说明对应不上。

Upd：上面图示的第二个绿色式子应该是 10=5+1+1+3 .

那么我们要快速判定一个前缀矩形其实也不难的，其实这个所谓的前缀矩形就是所有的 x 或 y 小于某一个值的点组成的矩形，那么我们不难想到用树状数组维护，二维数组树状数组维护每一个前缀矩形（指 [0,0] 到 [x,y] 的矩形）的点的数量，但是显而易见不可行。因为题目的数据范围很大，就算离散化最坏情况依然需要 $1e5\times 1e5$ 的空间。

于是说我们灵机一动，存下每个 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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;

int n;
int ax[N], ay[N];
pair<int , int >a[N];

int c[20], p[20];

inline void Input() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(ax[i], ay[i]);
        a[i] = make_pair(ax[i], ay[i]);
    }
    for(int i = 1; i <= 9; i++) {
        read(c[i]), p[i] = i;
    }
}

struct preST {
    int t[N], n;
    inline void add(int x) { t[x]++; }
    inline void init() { for(int i = 1; i <= n; i++) t[i] += t[i - 1]; }
    inline int find(int x) {
        int p = lower_bound(t + 1, t + n + 1, x) - t;
        if(t[p] == x) return p;
        return 0;
    }
}tx, ty;

struct BIT {
    vector<int > t[N];
    inline void add(int x, int y) {
        for(int i = x; i <= tx.n; i += i & -i) t[i].push_back(y);
    }
    inline int qry(int x, int y) {
        int ans = 0;
        for(int i = x; i >= 1; i -= i & -i) {
            ans += upper_bound(t[i].begin(), t[i].end(), y) - t[i].begin();
        }
        return ans;
    }
}bit;

inline void Check() {
    int sx1 = c[p[1]] + c[p[4]] + c[p[7]];
    int sx2 = sx1 + c[p[2]] + c[p[5]] + c[p[8]];
    int sy1 = c[p[1]] + c[p[2]] + c[p[3]];
    int sy2 = sy1 + c[p[4]] + c[p[5]] + c[p[6]];
    
    int fx1 = tx.find(sx1); if(!fx1) return;
    int fx2 = tx.find(sx2); if(!fx2) return;
    int fy1 = ty.find(sy1); if(!fy1) return;
    int fy2 = ty.find(sy2); if(!fy2) return;

    if(bit.qry(fx1, fy1) != c[p[1]]) return;
    if(bit.qry(fx1, fy2) - c[p[1]] != c[p[4]]) return;
    if(bit.qry(fx2, fy1) - c[p[1]] != c[p[2]]) return;
    if(bit.qry(fx2, fy2) - c[p[1]] - c[p[2]] - c[p[4]] != c[p[5]]) return;
    if(bit.qry(tx.n, fy1) - c[p[1]] - c[p[2]] != c[p[3]]) return;
    if(bit.qry(tx.n, fy2) - c[p[1]] - c[p[2]] - c[p[3]] - c[p[4]] - c[p[5]] != c[p[6]]) {
        return;
    }
    printf("%lf %lf\n", 1.0 * ax[fx1] + 0.5, 1.0 * ax[fx2] + 0.5);
    printf("%lf %lf\n", 1.0 * ay[fy1] + 0.5, 1.0 * ay[fy2] + 0.5);
    exit(0);
}

inline void Work() {
    sort(ax + 1, ax + n + 1);
    sort(ay + 1, ay + n + 1);
    tx.n = unique(ax + 1, ax + n + 1) - ax - 1;
    ty.n = unique(ay + 1, ay + n + 1) - ay - 1;
    for(int i = 1; i <= n; i++) {
        a[i].first = lower_bound(ax + 1, ax + tx.n + 1, a[i].first ) - ax;
        a[i].second= lower_bound(ay + 1, ay + ty.n + 1, a[i].second) - ay;
        bit.add(a[i].first, a[i].second);
        tx.add(a[i].first), ty.add(a[i].second);
    }
    tx.init(), ty.init();
    for(int i = 1; i <= tx.n; i++) {
        sort(bit.t[i].begin(), bit.t[i].end());
    }
    do {
        Check();
    }while(next_permutation(p + 1, p + 10));
    printf("-1\n");
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

例题二：才不是普通布偶

然后来看一道动态的题罢

题面大意

在二维平面上两种操作：

  1. 0 x y ：增加一个坐标为 $(x,y)$ 的节点（重复节点不算）
  2. 1 x1 y1 x2 y2 ：查询左上角 $(x1,y1)$ 到右下角 $(x2,y2)$ 的矩形内有多少点

题目思路

没话说，这种就是典型的二维树状数组题目了，应该是没有思路可言的罢。

题解代码

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
const int N = 3e4 + 10;
const int M = 2e3 + 10;

struct BIT {
    ll c[M];
    inline void clear() { memset(c, 0, sizeof(c)); }
    inline void add(int x, ll v) {
        for(int i = x; i < M; i += (i & (-i))) {
            c[i] += v;
        }
    }
    inline ll qry(int x) {
        ll ans = 0;
        for(int i = x; i >= 1; i -= (i & (-i))) {
            ans += c[i];
        }
        return ans;
    }
};

struct BIT_2D {
    BIT c[M];
    inline void clear() { 
        for(int i = 0; i < M; i++) c[i].clear();
    }
    inline void add(int x, int y, ll v) {
        for(int i = x; i < M; i += (i & (-i))) {
            c[i].add(y, v);
        }
    }
    inline ll qry(int x, int y) {
        ll ans = 0;
        for(int i = x; i >= 1; i -= (i & (-i))) {
            ans += c[i].qry(y);
        }
        return ans;
    }
}bit2d;

int n;

int vis[M][M];

inline void Input() {
    read(n);
}

inline void Work() {
    int op, ax, ay, bx, by;
    for(int i = 1; i <= n; i++) {
        read(op, ax, ay);
        ax++, ay++;
        if(op == 0) {
            if(vis[ax][ay]) continue;
            bit2d.add(ax, ay, 1);
            vis[ax][ay] = 1;
        }
        else {
            read(bx, by);
            bx++, by++;
            printf("%lld\n", bit2d.qry(bx, by) - bit2d.qry(bx, ay - 1) - bit2d.qry(ax - 1, by) + bit2d.qry(ax - 1, ay - 1)); // 引用了二位前缀和思路
        }
    }
}

例题三：是兔兔伯爵！

然后这里会给出一个二维数点问题的经典思路，先看题。

题面大意

天文学家经常检查星图，星图上的星星由平面上的点表示，每个星星都有笛卡尔坐标。将一个星星的等级定义为在给定星星的左边和下边的星星数量。天文学家想要知道星星等级的分布情况。

img

例如，参考上图中的星图。编号为5的星星的等级等于3（由编号为1、2和4的三颗星星组成）。编号为2和4的星星的等级是1。在这个星图中，只有一颗等级为0的星星，两颗等级为1的星星，一颗等级为2的星星，以及一颗等级为3的星星。

你需要编写一个程序，计算给定星图上每个等级的星星数量。

题目思路

这道题的思路是很经典的。题目让我们求星星左下角的点的数量，不难想到一个点左下面的点都是满足 x 坐标和 y 坐标都小于等于这个点的。但是同时维护两个最小值很麻烦，于是我们用排序。比如说我们按照 x 排序，那么第 $i$ 个点的左下角的点其实就是 $1\sim i-1$ 所有 y 坐标小于等于它的点的数量了，因为已经按照 x 排序，那么下标小的点 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
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 2e4 + 10;
const int M = 4e4 + 10;

int n;
pair<int , int >a[N];

inline void Input() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i].first, a[i].second);
        a[i].first++, a[i].second++;
    }
}

struct BIT {
    int c[M];
    inline void add(int x, int v) {
        for(int i = x; i < M; i += (i & (-i))) {
            c[i] += v;
        }
    }
    inline int qry(int x) {
        int ans = 0;
        for(int i = x; i >= 1; i -= (i & (-i))) {
            ans += c[i];
        }
        return ans;
    }
}bit;

int cnt[N];

inline void Work() {
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        cnt[bit.qry(a[i].second)]++;
        bit.add(a[i].second, 1);
    }
    for(int i = 0; i < n; i++) {
        printf("%d\n", cnt[i]);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

算法实战：疾如野火

其实吧，还有一个扫描线没有讲，扫描线作为一个单独的算法或者说思想，我打算单独写在一篇文章中的，所以说这篇文章的内容就这样结束了。

查看相关算法标签喵！