以CF1883D为例
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6;
int n;
vector<int> p;
int l[N], r[N];
char op[N];
struct Node {
int l, r;
int x, a;
} tr[N];
void pushup(int u)
{
tr[u].x = max(tr[u << 1].x, tr[u << 1 | 1].x);
}
void pushdown(int u)
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.a)
{
left.a += root.a, left.x += root.a;
right.a += root.a, right.x += root.a;
root.a = 0;
}
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1,l, mid), build(u << 1 | 1, mid + 1, r);
}
// int query(int u, int l, int r)
// {
// if (l <= tr[u].l && tr[u].r <= r) return tr[u].x;
// pushdown(u);
// int mid = l + r >> 1;
// int res = 0;
// if (l <= mid) res = query(u << 1, l, r);
// if (r > mid) res = max(res, query(u << 1 | 1, l, r));
// return res;
// }
void modify(int u, int l, int r, int y)
{
if (l <= tr[u].l && tr[u].r <= r)
{
tr[u].a += y;
tr[u].x += y;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, y);
if (r > mid) modify(u << 1 | 1, l, r, y);
pushup(u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
while (T -- )
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> op[i] >> l[i] >> r[i];
p.push_back(l[i]), p.push_back(r[i]);
}
sort(p.begin(), p.end());
unique(p.begin(), p.end());
for (int i = 1; i <= n; i ++ )
{
l[i] = lower_bound(p.begin(), p.end(), l[i]) - p.begin() + 1;
r[i] = lower_bound(p.begin(), p.end(), r[i]) - p.begin() + 1;
}
build(1, 1, 2 * n);
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
if (op[i] == '+')
{
cnt ++ ;
modify(1, l[i], r[i], 1);
}
else
{
cnt -- ;
modify(1, l[i], r[i], -1);
}
if (tr[1].x != cnt && cnt > 1) cout << "YES\n";
else cout << "NO\n";
}
}
}