Happy Triangle

题目大意

有 $m$ 次操作 $1$ $x$ 表示在数组中添加上 $x$
$2 \ x$ 表示从数组中删除 $x$
$3\ x$ 问你能否从数组中选出两个数 $a \ b$ 使得这三个数可以构成一个三角形

解题思路

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

代码

#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;
}

[Happy Triangle

Happy Triangle

题目大意

解题思路

代码