「2021年北京理工大学2020级暑训 rating4」三角形

「题意」

维护一个可重集合,有 $n$ 个操作,为下列三种之一:

  • 1 x:插入 $x$
  • 2 x:删除一个 $x$ (保证集合中至少有 $1$ 个 $x$)
  • 3 x:判断集合中是否存在两个数 $a,b$,使得 $a,b,x$ 能够组成三角形的三条边

$n\leq 2\times 10^5,x\leq 10^9$

「分析」

考虑什么情况下 $a,b,x$ 可以组成三角形:当 $a+b>x$ 且 $|a-b|<x$。

当满足 $|a-b|<x$ 时,显然取尽可能大的 $a,b$ 会更可能符合条件。

因此可以维护一棵权值线段树,维护区间内的最大值、最小值和最小差值。

查询时,先查询左区间的最大值和右区间的最小值是否满足条件,然后当满足右区间的最小差值 $<x$ 时,选择继续进入右区间,否则如果左区间的最小差值 $>x$ 时,进入左区间,否则无解。

复杂度 $O(n\log{x})$。

「参考代码」

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
/*
* @date:
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define up(i, l, r) for (int i = l; i <= r; ++i)
#define dn(i, l, r) for (int i = l; i >= r; --i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int MAXN = 2e5 + 5;
const int MX = 1e9;

struct SegmentTree {
static const int N = ::MAXN * 40;
static const int INF = 0x3f3f3f3f;
struct Node {
int ls, rs, lm, rm, delta, sz;
Node () {
ls = rs = sz = 0;
lm = delta = INF;
rm = -INF;
}
} A[N];
int rt, tot;
int newNode() {
A[tot] = Node();
return tot++;
}
void init() {
rt = tot = 0;
newNode();
}
void pushUp(int rt) {
auto &x = A[rt], &ls = A[A[rt].ls], &rs = A[A[rt].rs];
x.sz = ls.sz + rs.sz;
x.lm = min(ls.lm, rs.lm);
x.rm = max(ls.rm, rs.rm);
x.delta = min(ls.delta, rs.delta);
if (ls.sz && rs.sz) chkMin(x.delta, rs.lm - ls.rm);
}
void update(int &rt, int l, int r, int p, int num) {
if (!rt) rt = newNode();
if (l == r) {
A[rt].sz += num;
assert(A[rt].sz >= 0);
if (!A[rt].sz) {
A[rt] = Node();
} else {
A[rt].lm = A[rt].rm = p;
}
if (A[rt].sz > 1) A[rt].delta = 0;
else A[rt].delta = INF;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(A[rt].ls, l, m, p, num);
else update(A[rt].rs, m + 1, r, p, num);
pushUp(rt);
}
int query(int rt, int l, int r, int x) {
if (!rt || A[rt].delta >= x) return 0;
if (l == r) return 2 * l > x;
int m = (l + r) >> 1;
if (A[A[rt].rs].sz && A[A[rt].ls].sz && A[A[rt].rs].lm - A[A[rt].ls].rm < x && A[A[rt].ls].rm + A[A[rt].rs].lm > x) return 1;
if (A[A[rt].rs].delta < x) return query(A[rt].rs, m + 1, r, x);
else return query(A[rt].ls, l, m, x);
}
} T;

void solve() {
int Q, opt, x;
cin >> Q;
T.init();
while (Q--) {
cin >> opt >> x;
if (!x) {
if (opt == 3) cout << "No\n";
continue;
}
assert(x >= 1 && x <= MX);
if (opt == 1) T.update(T.rt, 1, MX, x, 1);
if (opt == 2) T.update(T.rt, 1, MX, x, -1);
if (opt == 3) cout << (T.query(T.rt, 1, MX, x) ? "Yes" : "No") << "\n";
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}