2020暑期D2-H 思路+证明
主为自用，欢迎指正。

https://ac.nowcoder.com/acm/contest/5667/H

前置知识：

题意：
给定一个集合MS和q种操作，操作共三种。
1.插入x。
2.删除x。
3.查找MS中是否存在a、b，使得a、b、x构成三角形。
能输出“Yes”，反之“No”。

思路：
首先，三个数之间的差越小，构成三角形的可能性就越大，由于存在插入与删除的操作，否则集合排序，搜索找相邻即可。故，一定要用树的结构来实现插入与删除，由于要实现数之间差最小，容易通过前后缀存入相邻数据。
设，a为b的前驱，若x为a、b中的最大边，若a+b>x，则成立；若x非最大边，则在任意b>=x的节点中，若存在x>b-a，则成立。
因此我们只需实现前驱相邻即可，但是这样反而像个一维数组，而不是一个树。。。
线段树每个节点通过包含一个区间的信息来快速得到区间所需信息，由于线段树的每个叶子节点存放输入数据，后自底向上遍历更新各区间节点信息。
而本体的线段树，增加了对最小值下标low、h1对大元素下标、h2区间次大元素下标、b区间相邻元素差最小值的维护，大体思路依照炮兵布阵即可。

代码步骤：

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#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]);   //向量v是有序排列的，故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);      //在pushup（）中实现真正的修改。
    //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());    //删除v中重复的数。（unique 返回指向不重复区域之后一个位置的迭代器;erase 删除迭代器之间的元素）
    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);    //节点sz-1使该节点无法在query中被获取
        else
        {
            Node q1 = query(1, 0, find(x[i]) - 1);
            if (q1.sz >= 2 and v[q1.h1] + v[q1.h2] > x[i])        //存在x为最大值，即有x有两个前继节点
            {
                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;
}

简单图证：

注：
应注意顺序，即注意查询时，已具有哪些数据。