【数据结构】二维数点/二维偏序
该内容需要有一定的数据结构基础，前置知识：二维前缀和、树状数组、线段树、扫描线等
二维数点的解法较多，可自行查找和学习其他解法
二维数点简介
二维数点又称二维偏序，它是这样一类问题，给出一个二维平面內的若干个点，多次询问某个矩形区域內包含多少个点（边界也算）。又或者，给一个长为
n
n
n 的序列，多次询问区间
[
l
,
r
]
[l,r]
[l,r] 中值在
[
x
,
y
]
[x,y]
[x,y] 内的元素个数。
能解决这一问题的数据结构较多，包括树状数组/线段树、K-D Tree、可持久化线段树等，运用CDQ分治可解决更高维的偏序问题。以下着重讲解扫描线思想+树状数组解决二维偏序问题的方法。
二维数点的本质，是我们要查询一个矩形区域內的点数，首先考虑二维前缀和，对于矩形
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
(x_1,y_1),(x_2,y_2)
(x1,y1),(x2,y2)，其二维前缀和为
s
[
x
2
]
[
y
2
]
−
s
[
x
1
−
1
]
[
y
2
]
−
s
[
x
2
]
[
y
1
−
1
]
+
s
[
x
1
−
1
]
[
y
1
−
1
]
s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]
s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]。可惜由于时空的双重限制，我们几乎不可能求出二维前缀和。
假设我们将矩形按横坐标排序，对于当前
x
x
x，如果所有
x
′
≤
x
x’ \leq x
x′≤x 的点的纵坐标都已知，那么将会有
s
[
x
]
[
y
]
=
q
u
e
r
y
(
1
,
y
)
s[x][y]=query(1,y)
s[x][y]=query(1,y)，其中
q
u
e
r
y
(
1
,
y
)
query(1,y)
query(1,y) 代表查询纵坐标在
[
1
,
y
]
[1,y]
[1,y] 内的点数，这意味着我们把二维前缀和压成了一维的，每次查询只和
y
y
y 有关，这可以用简单数据结构来维护。整个思想与线段树的扫描线算法是十分相似的。
那么如何求出一个矩形区域內的答案呢？根据二维前缀和公式，我们只需要分别求出其四个区域的贡献（或正或负），相加即可。于是我们在从左往右沿
x
x
x 轴前进的过程中，不断将
x
′
≤
x
x’ \leq x
x′≤x 的点的纵坐标加入树状数组，依次求出所有询问对应的四个区域的贡献。询问需要提前离线，每个询问拆为四个区域。
于是，整个算法过程就是
- 将所有点按横坐标排序
- 将所有矩形询问拆成四个区域，即四次询问，所有询问按
x
x
x 轴排序
- 遍历询问，设当前横坐标为
x
x
x，保证
x
′
≤
x
x’ \leq x
x′≤x 的所有点的纵坐标已加入树状数组，在树状数组中查询答案，贡献加至原询问处
- 输出每个原询问的答案
练习
[SHOI2007]园丁的烦恼
题目链接
题意：平面上给出
n
n
n 个点，
m
m
m 次询问，每次给出一个矩形，询问处于所给矩形区域內的点的数量。
思路：模板题，注意到
n
,
m
n,m
n,m 数据范围较大，离散化带个log容易被卡，而坐标范围为
[
0
,
1
0
7
]
[0,10^7]
[0,107]，其实可以不进行离散化，但是由于坐标范围到0，树状数组不支持0下标，不妨将坐标全部加1。
参考代码：
#include
using namespace std;
constexpr int MAXN = 1e7 + 5;
int sum[MAXN], ans[MAXN];
vector<pair> vec;
vector<tuple> q;
inline int lowbit(int x) { return x & (-x); }
void add(int pos, int x)
{
for (; pos < MAXN; pos += lowbit(pos))
sum[pos] += x;
}
int query_presum(int pos)
{
int ans = 0;
for (; pos > 0; pos -= lowbit(pos))
ans += sum[pos];
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, x1, x2, y1, y2;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> x1 >> y1, ++x1, ++y1;
vec.emplace_back(x1, y1);
}
sort(vec.begin(), vec.end());
for (int i = 0; i < m; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
++x1, ++y1, ++x2, ++y2;
q.emplace_back(x1 - 1, y1 - 1, 1, i);
q.emplace_back(x1 - 1, y2, -1, i);
q.emplace_back(x2, y1 - 1, -1, i);
q.emplace_back(x2, y2, 1, i);
}
sort(q.begin(), q.end());
int cur = 0;
for (auto [x, y, c, id] : q)
{
while (cur < n && vec[cur].first <= x)
add(vec[cur].second, 1), ++cur;
ans[id] += c * query_presum(y);
}
for (int i = 0; i < m; i++)
cout << ans[i] << "\n";
return 0;
}
[CQOI2017]老C的任务
题目链接
题意：平面上给出
n
n
n 个点，每个点有权值
p
i
p_i
pi，
m
m
m 次询问，每次给出一个矩形，询问处于所给矩形区域內的点的权值之和。
思路：我们只会维护点的数量，如果还要维护每个点对应的权值，这是做不到的。但是，把权值
p
i
p_i
pi 看作有
p
i
p_i
pi 个点在当前位置上重合，显然这个问题就转换成了例题。本题中需要离散化。
参考代码：
#include
using namespace std;
constexpr int MAXN = 3e5 + 5;
int64_t sum[MAXN], ans[MAXN];
vector yy;
vector<tuple> vec;
vector<tuple> q;
inline int lowbit(int x) { return x & (-x); }
void add(int pos, int64_t x)
{
for (; pos < MAXN; pos += lowbit(pos))
sum[pos] += x;
}
int64_t query_presum(int pos)
{
int64_t ans = 0;
for (; pos > 0; pos -= lowbit(pos))
ans += sum[pos];
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, x1, x2, y1, y2, p;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> x1 >> y1 >> p;
yy.push_back(y1);
vec.emplace_back(x1, y1, p);
}
sort(vec.begin(), vec.end());
for (int i = 0; i < m; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
yy.push_back(y1 - 1), yy.push_back(y2);
q.emplace_back(x1 - 1, y1 - 1, 1, i);
q.emplace_back(x1 - 1, y2, -1, i);
q.emplace_back(x2, y1 - 1, -1, i);
q.emplace_back(x2, y2, 1, i);
}
sort(q.begin(), q.end());
sort(yy.begin(), yy.end());
yy.erase(unique(yy.begin(), yy.end()), yy.end());
int cur = 0;
for (auto [x, y, c, id] : q)
{
y = lower_bound(yy.begin(), yy.end(), y) - yy.begin() + 1;
while (cur < n)
{
auto [_x, _y, p] = vec[cur];
if (_x > x)
break;
_y = lower_bound(yy.begin(), yy.end(), _y) - yy.begin() + 1;
add(_y, p), ++cur;
}
ans[id] += c * query_presum(y);
}
for (int i = 0; i < m; i++)
cout << ans[i] << "\n";
return 0;
}
[SDOI2009]HH的项链
题目链接
题意：给一个长为
n
n
n 的序列，每个位置元素值为
a
i
a_i
ai，多次询问区间
[
l
,
r
]
[l,r]
[l,r] 中元素种类数。
思路：照常把
x
x
x 所在一维降掉后，发现
y
y
y 轴并没有明显的偏序关系。可以这样考虑，我们只计每个元素第一次在区间中出现时有贡献，设
p
r
e
[
i
]
pre[i]
pre[i] 表示位置
i
i
i 的元素前一次出现的位置，在整个序列中第一次出现时记为0，由此，总的二维偏序关系为：
{
l
≤
x
≤
r
p
r
e
[
x
]
<
l
\left\{ \begin{aligned} l \leq x & \leq r \\ pre[x] & < l \\ \end{aligned} \right.
{l≤xpre[x]≤r<l
由于树状数组不支持0下标，可以稍作平移。能够看到在设定的偏序关系下，查询返回了正确的结果。
参考代码：
#include
using namespace std;
constexpr int MAXN = 1e6 + 5;
int sum[MAXN], pre[MAXN], ans[MAXN];
vector<pair> vec;
vector<tuple> q;
inline int lowbit(int x) { return x & (-x); }
void add(int pos, int x)
{
for (; pos < MAXN; pos += lowbit(pos))
sum[pos] += x;
}
int query_presum(int pos)
{
int ans = 0;
for (; pos > 0; pos -= lowbit(pos))
ans += sum[pos];
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, a, l, r;
cin >> n;
for (int i = 3; i <= n + 2; i++)
{
cin >> a;
vec.emplace_back(i, pre[a] ? pre[a] : 2), pre[a] = i;
}
sort(vec.begin(), vec.end());
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> l >> r, l += 2, r += 2;
q.emplace_back(l - 1, 1, 1, i);
q.emplace_back(l - 1, l - 1, -1, i);
q.emplace_back(r, 1, -1, i);
q.emplace_back(r, l - 1, 1, i);
}
sort(q.begin(), q.end());
int cur = 0;
for (auto [x, y, c, id] : q)
{
while (cur < n && vec[cur].first <= x)
add(vec[cur].second, 1), ++cur;
ans[id] += c * query_presum(y);
}
for (int i = 0; i < m; i++)
cout << ans[i] << "\n";
return 0;
}
CF1320C – World of Darkraft: Battle for Azathoth
题目链接
题意：你有
n
n
n 件武器，
m
m
m 件防具，每件装备有对应的攻击力/防御力和价格，你必须各选择一件。有
p
p
p 只怪物，每只防御力、攻击力、掉落金币分别为
x
i
,
y
i
,
z
i
x_i,y_i,z_i
xi,yi,zi，假设你攻击力和防御力分别是
a
k
,
b
k
a_k,b_k
ak,bk，你只能战胜
a
k
>
x
i
a_k>x_i
ak>xi 且
b
k
>
y
i
b_k>y_i
bk>yi 的怪物。求最大收益（可能为负）。
思路：题目已经给出了二维偏序关系，设
x
x
x 轴和
y
y
y 轴分别表示攻击力和防御力，以怪物作为点，可以发现询问是武器和防具任意组合后，以
(
0
,
0
)
,
(
b
k
−
1
,
a
k
−
1
)
(0,0),(b_k-1,a_k-1)
(0,0),(bk−1,ak−1) 为顶点的一个矩形。枚举武器降掉一维，逐个加点，问题变成每次对于所有防具，求最大收益。
这需要使用线段树来维护，先设定
[
1
,
1
0
6
]
[1,10^6]
[1,106] 內所有防具的初始收益，每次加点相当于给
[
y
i
+
1
,
1
0
6
]
[y_i+1,10^6]
[yi+1,106] 内的所有防具增加
z
i
z_i
zi 的收益，查询全局最值并更新答案即可。
参考代码：
#include
using namespace std;
constexpr int MAXN = 1e6 + 5, N = 1e6 + 1;
int mx[MAXN << 2], add[MAXN << 2], w[MAXN];
vector<pair> weapon;
vector<tuple> mon;
void pushDown(int rt)
{
mx[rt << 1] += add[rt], mx[rt << 1 | 1] += add[rt];
add[rt << 1] += add[rt], add[rt << 1 | 1] += add[rt];
add[rt] = 0;
}
void modify(int L, int R, int C, int l, int r, int rt)
{
if (L <= l && r <= R)
{
mx[rt] += C, add[rt] += C;
return;
}
int mid = (l + r) >> 1;
pushDown(rt);
if (L <= mid)
modify(L, R, C, l, mid, rt < mid)
modify(L, R, C, mid + 1, r, rt << 1 | 1);
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
int query(int L, int R, int l, int r, int rt)
{
if (L <= l && r > 1;
pushDown(rt);
int ans = -2e9;
if (L <= mid)
ans = max(ans, query(L, R, l, mid, rt < mid)
ans = max(ans, query(L, R, mid + 1, r, rt << 1 | 1));
return ans;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, p, x, y, z;
cin >> n >> m >> p;
for (int i = 1; i > x >> y, weapon.emplace_back(x, y);
fill(w, w + MAXN, -2e9);
for (int i = 1; i > x >> y, w[x] = max(w[x], -y);
for (int i = 1; i <= N; i++)
modify(i, i, w[i], 1, N, 1);
for (int i = 1; i > x >> y >> z, mon.emplace_back(x, y, z); //
sort(weapon.begin(), weapon.end());
sort(mon.begin(), mon.end());
int cur = 0, ans = -2e9;
for (auto [a, ca] : weapon)
{
while (cur < mon.size())
{
auto [x, y, z] = mon[cur];
if (x >= a)
break;
modify(y + 1, N, z, 1, N, 1), ++cur;
}
ans = max(ans, -ca + query(1, N, 1, N, 1));
}
cout << ans << endl;
return 0;
}
[传智杯 #4 初赛] 小卡与落叶
题目链接
题意：给出一棵树，初始所有结点为绿色。支持两种操作，一是把整棵树染绿，再将深度
≥
x
\geq x
≥x 的结点染黄，二是询问以结点
x
x
x 为根的子树中黄色结点数量。
思路：一个重要的观察是，对于每次询问，显然只需要考虑它前面的最后一次操作。我们知道子树的dfs序是一个连续区间，设
L
[
v
]
,
R
[
v
]
L[v],R[v]
L[v],R[v] 分别代表子树根结点
v
v
v 的dfs序及其子树中最大dfs序，那么二维偏序关系为
L
[
v
]
≤
d
f
n
[
u
]
≤
R
[
v
]
L[v] \leq dfn[u] \leq R[v]
L[v]≤dfn[u]≤R[v] 且
d
e
p
[
u
]
≥
x
dep[u] \geq x
dep[u]≥x。这是一个把二维数点搬到树上的题目，以dfs序为横轴，深度为纵轴，显然要降掉dfs序，问题变为每次查询符合深度要求的点数。直接顺序读取操作和询问，添加矩形查询，转变为例题。
参考代码：
#include
using namespace std;
constexpr int MAXN = 1e5 + 5;
int L[MAXN], R[MAXN], rnk[MAXN], dep[MAXN], dfn;
int sum[MAXN], ans[MAXN];
vector G[MAXN];
vector<tuple> q;
inline int lowbit(int x) { return x & (-x); }
void add(int pos, int x)
{
for (; pos < MAXN; pos += lowbit(pos))
sum[pos] += x;
}
int query_presum(int pos)
{
int ans = 0;
for (; pos > 0; pos -= lowbit(pos))
ans += sum[pos];
return ans;
}
void dfs(int v, int fa)
{
L[v] = ++dfn;
rnk[dfn] = v;
dep[v] = dep[fa] + 1;
for (auto u : G[v])
{
if (u != fa)
dfs(u, v);
}
R[v] = dfn;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1, x, y; i < n; i++)
{
cin >> x >> y;
G[x].push_back(y), G[y].push_back(x);
}
dfs(1, 0);
int lst = 1e5 + 2, cnt = 0;
for (int i = 1, op, x; i <= m; i++)
{
cin >> op >> x;
if (op == 1)
lst = x;
else
{
++cnt;
q.emplace_back(L[x] - 1, lst - 1, 1, cnt);
q.emplace_back(L[x] - 1, 1e5 + 4, -1, cnt);
q.emplace_back(R[x], lst - 1, -1, cnt);
q.emplace_back(R[x], 1e5 + 4, 1, cnt);
}
}
sort(q.begin(), q.end());
int cur = 1;
for (auto [x, y, c, id] : q)
{
while (cur <= n && cur <= x)
add(dep[rnk[cur]], 1), ++cur;
ans[id] += c * query_presum(y);
}
for (int i = 1; i <= cnt; i++)
cout << ans[i] << "\n";
return 0;
}
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/7836c310a0.html
相关推荐
-
【无标题】 C语言：数据结构之顺序表
C语言：数据结构之顺序表 顺序表 一些比较重要的概念 free（），是释放动态申请内存的空间，不可以随便释放一个普通指针的空间 指针，存储的…
-
数据结构：STL：vector
目录 1.vector头文件 2.vector是什么 3.vector定义 4.vector容器元素访问 4.1 下标访问 4.2 通过迭代器访问 5.vector常用函数 5.1…
-
【Redis】集群-数据分片算法&集群扩容&集群宕机&集群缩容
文章目录 前置内容 如何获取更大的空间 数据分片算法 哈希求余 一致性哈希算法 哈希槽分区算法 (Redis 使用) 集群扩容 集群宕机情况 集群缩容 前置内容 哨兵模式提⾼了系统…
-
流程编排数据结构就下面几个及可视化，核心业务逻辑涉及内部逻辑运算
什么是向量？ 向量是数学、物理学和工程科学等多个自然科学中的基本概念，它是一个具有方向和长度的量，用于描述问题，如空间几何、力学、信号处理等。在计算机科学中，向量被用于表示数据，如…
-
bfprt算法
第k小的数的相关问题 第k小的数如何在时间复杂度O(N)找到 1.利用快排的思想 2.bfprt算法 2.1时间复杂度的分析 3.相关题目和总结 第k小的数如何在时间复杂度O(N)…
-
343. 整数拆分(动态规划)
题目： 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n = 2…
-
【贪心算法】贪心算法原理思想、算法步骤，应用示例（找零问题、活动选择问、霍夫曼编码、最小生成树问题、车辆路径问题）
贪心算法是一种基于贪心策略的优化算法，它在每一步选择中都采取当前状态下的最优决策，而不考虑未来的后果。通常，这种算法对于解决一些最优化问题非常有效，尤其是那些可以通…
-
动态规划-计数、数位统计、状态压缩、树形、记忆化搜索Dp
文章目录 一、前言 二、计数类Dp-整数划分 1.题目描述 输入格式 输出格式 数据范围 输入样例: 输出样例： 2.完全背包算法 代码 3.其他算法 代码 三、数位统计Dp-计数…
-
4.1.1 蓝桥杯之动态规划线性DP课后习题建造房屋
一、信息 问题描述: 设计一个城市建筑方案，满足预算和建造要求。 条件: N条街道，每条街道上有 M个位置。 每个位置建造费用为 1元。 总预算 K元。 要求每条街道至少建一个房屋…
-
算法复习笔记
这里写自定义目录标题 C/C++快速入门 头文件 主函数 输入输出函数 变量类型 注意 if语句 switch语句 循环结构 while语句 do…while语句 fo…
