2020牛客多校第2场 H. Happy Triangle【线段树】

原题链接： Happy Triangle

题目描述

维护一个可重集合，进行 次操作，
操作1：插入一个数
操作2：删除一个数
操作3：给出一个数 ，判断是否能从集合中找到两个数 , 使得 这三个数组成一个三角形

输入样例

8
1 1
3 1
1 1
3 2
3 1
1 2
2 1
3 1

输出样例

No
No
Yes
No

线段树

出题人题解：
首先，我们在回答询问时只考虑相邻的两个数，因为对于一组数 不妨设
如果能构成三角形的三边，那么我们把 替换成 的前驱也一定是合法的

对于上面说法的解释：
对于集合中的一对数 ，如果有 则可以构成三角形三边
把 替换成 的前驱 （），则合法区间变成了
由于 所以有 且
合法区间向两侧扩张，所以选相邻的两个数更优

如何解决询问：
对于每一次询问考虑两种情况：

• 是最大边，找到集合中 的两个前驱，如果他们的和大于 则合法

• 不是最大边，对于集合中任意的 ，如果有 ，则合法

线段树如何维护：

首先我们对操作给出的所有数做一遍离散化，构建值域线段树

struct Node{
    int l, r;
    int low, h1, h2, b;
    int sz;
}tr[N << 2];

sz 为区间中包含的元素个数
low 为区间中包含的最小的元素的下标（没有数时为-1）
h1 为区间中包含的最大的元素的下标（没有数时为-1）
h2 为区间中包含的次大的元素的下标（没有数时为-1）
b 为区间中相邻元素的差的最小值（sz < 2时为正无穷）

单点更新和 都比较复杂，具体可以看完整代码

更新 时要考虑右子区间的最小值与左子区间的最大值

区间询问返回一个结构体
对于每个询问 我们做两次区间询问：
q1 = query(1, 0, find(x) - 1)
q2 = query(1, find(x), v.size() - 1)

如果 q1的 则满足情况

中的每个数都是 的，而情况 只需要有一个数 即可
因此我们令 q1.b = INF，仅用 的最大值作为 最小值的前驱，更新一下
判断是否有

时间复杂度

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;

vector<int> v;
int find(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

struct Node{
    int l, r;
    int low, h1, h2, b;
    int sz;
}tr[N << 4];

int op[N], x[N];

void build(int u, int l, int r)
{
    tr[u] = {l, r, -1, -1, -1, INF, 0};
    if(l == r)  return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void pushup(Node &u, Node &left, Node &right)
{
    u.sz = left.sz + right.sz;

    if(left.sz)  u.low = left.low;  else  u.low = right.low;

    int h[4] = {left.h1, left.h2, right.h1, right.h2};
    sort(h, h + 4);
    u.h1 = h[3], u.h2 = h[2];

    u.b = min(left.b, right.b);
    if(left.sz and right.sz)  u.b = min(u.b, v[right.low] - v[left.h1]);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void modify(int u, int x, int c)
{
    if(tr[u].l == x and tr[u].r == x)
    {
        tr[u].sz += c;
        if(tr[u].sz <= 0)  tr[u].low = tr[u].h1 = tr[u].h2 = -1,  tr[u].b = INF;
        else if(tr[u].sz == 1)  tr[u].low = tr[u].h1 = tr[u].l,  tr[u].h2 = -1,  tr[u].b = INF;
        else  tr[u].low = tr[u].h1 = tr[u].h2 = tr[u].l,  tr[u].b = 0;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid)  modify(u << 1, x, c);
    else  modify(u << 1 | 1, x, c);
    pushup(u);
    //printf("[%d, %d]  sz = %d  b = %d\n", tr[u].l, tr[u].r, tr[u].sz, tr[u].b);
}

Node query(int u, int l, int r)
{
    if(tr[u].l >= l and tr[u].r <= r)  return tr[u];

    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid)  return query(u << 1, l, r);
    if(l > mid)  return query(u << 1 | 1, l, r);

    Node left = query(u << 1, l, r), right = query(u << 1 | 1, l, r), res;
    pushup(res, left, right);
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d%d", &op[i], &x[i]);
        v.push_back(x[i]);
    }

    v.push_back(-1);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    build(1, 0, v.size() - 1);
    for(int i = 1; i <= n; i ++)
    {
        if(op[i] == 1)  modify(1, find(x[i]), 1);
        else if(op[i] == 2)  modify(1, find(x[i]), -1);
        else
        {
            Node q1 = query(1, 0, find(x[i]) - 1);
            if(q1.sz >= 2 and v[q1.h1] + v[q1.h2] > x[i])
            {
                puts("Yes");
                continue;
            }
            Node q2 = query(1, find(x[i]), v.size() - 1);
            //printf("q1.sz = %d    q2.sz = %d\n", q1.sz, q2.sz);
            if(q2.sz)
            {
                q1.b = INF;
                Node res;
                pushup(res, q1, q2);
                //printf("q2.b = %d  res.b = %d\n", q2.b, res.b);
                if(x[i] > res.b)
                {
                    puts("Yes");
                    continue;
                }
            }
            puts("No");
        }
    }
    return 0;
}