动态开点线段树

思想

动态开点线段树与主席树有一点区别。

如果想开n个线段树,每个线段树彼此独立,那么用动态开点线段树就行。
相同点:

  1. 每次只更新一条链。
    不同点:
  2. 主席树每次更新的时候是从原来树的基础上“牵”出一条新的链, 相当于建了一棵新树。
  3. 动态开点线段树并不会保留原来树的信息, 而是在“完善”当前这颗树。

    例题

题目

CF1046A;

有N个机器人,每个机器人有一个位置x, 一个视线半径r, 一个智商值q。

现在询问有多少对机器人可以相互看见,并且智商差的绝对值小于等于K

$1 \leq N \leq 1e5, 1 \leq k \leq 20$

分析

如何解决相互可以看见的问题:

将机器人按半径排序,用线段树维护每个机器人的位置。 依次插入机器人,查询其视线范围机器人的数量。

因为是半径大的先插,所以后插的能看见之前插的,那么之前插的也一定能看见后插的。

解决智商差的问题:

因为k只有20, 设当前机器人智商为q, 那么我们只要暴力查[q - k, q + k]智商内的,并且再其视线范围内的即可。

但是我们不能对每个智商都去开一个线段树,所以我们可以选择动态开点或者主席树。 (主席树差一点点就T了)

(突然发现并不需要对x坐标进行离散化,当然肯定不能去build)

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const int maxm = maxn * 40;
struct Node {
int x, r, q;
bool operator<(const Node &A) const { return r > A.r; }
};
Node a[maxn];
map<int, int> Hashq;
ll sum[maxm];
int lch[maxm], rch[maxm], root[maxn];
int dfn;
void update(int &k, int l, int r, int p, int x) {
if (!k) k = ++dfn;
sum[k] += x;
if (l == r) return;
int mid = l + r >> 1;
if (p <= mid) update(lch[k], l, mid, p, x);
if (mid + 1 <= p) update(rch[k], mid + 1, r, p, x);
}
ll query(int k, int l, int r, int L, int R) {
if (!k) return 0;
if (L <= l && R >= r) return sum[k];
int mid = l + r >> 1;
ll ret = 0;
if (L <= mid) ret += query(lch[k], l, mid, L, R);
if (mid + 1 <= R) ret += query(rch[k], mid + 1, r, L, R);
return ret;
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int Max = 1e9 + 1;
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d%d%d", &a[i].x, &a[i].r, &a[i].q);
sort(a, a + n); // r
dfn = 0;
int tot = 1;
ll ans = 0;
for (int i = 0; i < n; i++) {
int base = max(0, a[i].q - m);
int top = a[i].q + m;
int l = max(0, a[i].x - a[i].r);
int r = min(a[i].x + a[i].r, Max);
for (int j = base; j <= top; j++) {
if (Hashq.find(j) == Hashq.end()) continue;
ans += query(root[Hashq[j]], 0, Max, l, r);
}
if (Hashq[a[i].q] == 0) Hashq[a[i].q] = tot++;
update(root[Hashq[a[i].q]], 0, Max, a[i].x, 1);
}
printf("%lld\n", ans);
}
Thank you for your support!