题目描述
小红拿到了一个集合,初始为空集。小红可以进行以下两种操作:
- l r ——将一个区间$(l,r)$添加进集合。
- l r ——将区间$(l,r)$从集合中删除。
我们保证,删除操作时,集合中保证至少存在一个$(l,r)$区间。
请你在每次操作后,回答以下问题:当前集合中是否存在两个区间相交?
输入描述:
第一行输入一个正整数$q$,代表操作次数。
接下来的$q$行,每行输入一个字符$op$和两个正整数$l$,$r$,代表一次操作
$op∈ ′+ ′ , ′− ′$
$1 \le q \le 10^5 , 1 \le l \le r \le 10^9$
输出描述:
输出$q$行。如果操作结束后存在两个区间相交,则输出”$Yes$”。否则输出”$No$”。
示例1
输入
4
+ 1 2
+ 4 5
+ 4 6
- 4 5
输出
No
No
Yes
No
题目分析
开始想法是通过二分找位置,来做到删除和插入,然后想了下其实用堆操作就能实现,就抱着试一下的想法写了一下,用的multiset
,为了防止数据的重复性,然后就过了,$O(q^2)$
1.偷鸡写法 $O(q^2)$
#include <iostream>
#include <set>
using namespace std;
int main() {
int q;
cin >> q;
multiset<pair<int, int>> seg;
while (q--) {
char op;
int l, r;
cin >> op >> l >> r;
if (op == '+') {
seg.insert({l, r});
} else {
auto it = seg.find({l , r});
seg.erase(it);
}
bool insect = false;
for (auto it = seg.begin(); it != seg.end() && next(it) != seg.end(); ++it) {
auto ne = next(it);
if (it->second >= ne ->first) {
insect = true;
break;
}
}
cout << (insect ? "Yes" : "No") << endl;
}
return 0;
}
但是其实应该是过不了的,因为加上查询的话$O(q^2)$正常会爆,但是过了
下面是正经写法解题
为了维护这些线段,我们很容易想到线段树,增加线段就是该区间$+1$ ,删除线段就是该区间$-1$,判断是否相交就是看有没有某个区间的最大值大于$1$
但是这里的线段范围很大$10^9$,所以我们需要去离散化预处理线段端点,这样可以将$10^9$个点映射成最多$2*10^5$个点,这样就能建立线段树了。
2.离散化+线段树 $O(qlogq)$
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Node {
int l, r;
int vmax , add;
} tr[N * 8];
vector<int> w;
vector<tuple<char, int, int>> option;
int q, n;
void pushup(int u) {
tr[u].vmax = max(tr[u << 1].vmax, tr[u << 1 | 1].vmax);
}
void pushdown(int u)
{
auto &root = tr[u] , &left = tr[u << 1] , &right = tr[u << 1 | 1];
if(root.add)
{
left.add += root.add , left.vmax += root.add;
right.add += root.add , right.vmax += root.add;
root.add = 0;
}
}
void build(int u, int l, int r) {
if (l == r)
tr[u] = {l, r, 0 , 0};
else {
int mid = l + r >> 1;
tr[u] = {l, r , 0 , 0};
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].vmax;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if (mid >= l)
res = query(u << 1, l, r);
if (mid < r)
res = max(res , query(u << 1 | 1, l, r));
return res;
}
void modify(int u , int l , int r , int v)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].vmax += v;
tr[u].add += v;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1 , l , r , v);
if(r > mid) modify(u << 1 | 1 , l , r , v);
pushup(u);
}
}
int main() {
cin >> q;
char op;
int l, r;
while(q --) {
cin >> op >> l >> r;
option.push_back({op, l, r});
}
for (auto [op, l , r] : option) {
w.push_back(l);
w.push_back(r);
}
sort(w.begin(), w.end());
w.erase(unique(w.begin(), w.end()), w.end());
n = w.size();
build(1, 1, n);
for (auto &[op, l , r] : option) {
l = lower_bound(w.begin(), w.end(), l) - w.begin() + 1;
r = lower_bound(w.begin(), w.end(), r) - w.begin() + 1;
if (op == '+') {
modify(1 , l , r, 1);
} else {
modify(1 , l, r, -1);
}
auto res = query(1, 1, n);
cout << (res > 1 ? "Yes" : "No") << endl;
}
return 0;
}