Happy Triangle

题目大意

次操作 表示在数组中添加上
表示从数组中删除
问你能否从数组中选出两个数 使得这三个数可以构成一个三角形

解题思路

这题好像好多解法吧,因为是可以离线进行操作的,很巧的是没有一个是本菜鸡会的。赛后看了看大佬们的博客才知道,原来线段树还可以这样操作呀,真的是张见识了。
因为三个数如果想要构成三角形那么必须要满足 任意两个数之和大于第三个数。因此我们可以先对输入的 进行离散化处理后,用线段树维护一个区间中的一些值
我们需要维护区间最大值,次大值,最小值的位置,和区间最小差的值,这样比较方便进行下面的操作。 假设
那么我们只需要查找比 小的那部分区间的最大的两个值即可,这样如果是 那么肯定可有构成三角形 假设
那么的话我们只需要找到比 大的区间中两个数的最小差值大于即可
如果都不满足的话那么就肯定不能构成三角形了

代码

#include<bits/stdc++.h>
using namespace  std;

#define ll long long
const int mx=200200;
const int inf=0x3f3f3f3f;
vector<int>ve;
struct node{
    int l,r;// 表示这个区间的左右边界
//表示这个区间的 最小值,最大值,次小值的  离散后的数组下标 
//区间的数据中相差最小值  
    int low,h1,h2,b;
    int sz;//这个区间的元素个数 
}tr[mx<<2];
//存操作数 和操作数后面的值 
int op[mx],a[mx];
int n;
//获取离散化前面的值 
int get_id(int x){
    return lower_bound(ve.begin(),ve.end(),x)-ve.begin();
}
//建树 
void build(int x,int l,int r){
    tr[x]={l,r,-1,-1,-1,inf,0};
    if(l==r) return;
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
// 更新节点  这里用引用类型的好处是不用写返回值了 可直接更新 
void push_up(node &x,node &left,node &right){
    x.sz=left.sz+right.sz;//这个区间的值等于左右两个之和 
    //最小值肯定在这两个区间中的一个里面 
    if(left.sz){
        x.low=left.low;
    }else{
        x.low=right.low;
    }
// 更新这段区间的最大值和次大值    
    int h[4]={left.h1,left.h2,right.h2,right.h1};
    sort(h,h+4);
    x.h1=h[3],x.h2=h[2]; 
//更新相差最小值    
    x.b=min(left.b,right.b);
    if(left.sz and right.sz){
        //注意因为线段树存的是离线化以后的下标
        //进行比较的时候需要用离散化前的值 
        x.b=min(x.b,ve[right.low]-ve[left.h1]);
    }
}
void push_up(int x){
    push_up(tr[x],tr[x<<1],tr[x<<1|1]);
}
void update(int x,int pos,int k){
    if(tr[x].l==pos and tr[x].r==pos){
        tr[x].sz+=k;
        if(tr[x].sz<=0){
            tr[x].h1=tr[x].h2=tr[x].low=-1;
            tr[x].b=inf;
        }else if(tr[x].sz==1){
            tr[x].h1=tr[x].low=tr[x].l;
            tr[x].h2=-1;
            tr[x].b=inf;
        }else{
            //如果se大于1说明有相同的数出现了所以最大值最小值都是一样的
            //差值最小肯定是0 
            tr[x].low=tr[x].h1=tr[x].h2=tr[x].l;
            tr[x].b=0;
        }
        return;
    }
    int mid=tr[x].l+tr[x].r>>1;
    if(pos<=mid) update(x<<1,pos,k);
    else update(x<<1|1,pos,k);
    push_up(x);
}
node query(int x,int l,int r){
    if(tr[x].l>=l and tr[x].r<=r){
        return tr[x];
    }
    int mid=tr[x].l+tr[x].r>>1;
    if(r<=mid) return query(x<<1,l,r);
    if(l>mid) return query(x<<1|1,l,r);
// 这一步相当于 l 和 r 占据了 x的左区间一点,右区间一点    
    node left=query(x<<1,l,r);
    node right=query(x<<1|1,l,r);
    node res;
    push_up(res,left,right);
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>op[i]>>a[i];
        ve.push_back(a[i]);
    }
//数组下标是1 开始的所以加个最小值 
    ve.push_back(-1);
    //离散化处理 
    sort(ve.begin(),ve.end());
    ve.erase(unique(ve.begin(),ve.end()),ve.end());

    build(1,0,ve.size()-1);
    for(int i=1;i<=n;i++){
        if(op[i]==1){
            update(1,get_id(a[i]),1);
        }else if(op[i]==2){
            update(1,get_id(a[i]),-1);
        }else{
    //  如果找到第一个小于 a[i] 的数  a<b<z;
    // 如果   x+y>x 那么肯定可以 
            node q1=query(1,0,get_id(a[i])-1);
            if(q1.sz>=2&&ve[q1.h1]+ve[q1.h2]>a[i]){
                cout<<"Yes\n";
                continue;
            }
       // x<a<b        
            node q2=query(1,get_id(a[i]),ve.size()-1);
            if(q2.sz){
            //为了计算 比 x 的那部分区间差值最小是多少;
            //防止左区间的 差值 影响右区间所以这里给左区间赋个极大值    
                q1.b=inf;
                node res;
                push_up(res,q1,q2);
            //如果最大值的差小于 x 那么肯定也是可以的  b-a<x    
                if(a[i]>res.b){
                    cout<<"Yes\n";
                    continue;
                }
            }
            cout<<"No\n";
        }
    }
    return 0;
}