本文主要是介绍2020牛客暑期多校训练营（第二场）H Happy Triangle —— 权值线段树，离线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
现在有一个multiset，每次有三种操作：
1 x 往multiset里塞一个x
2 x 删掉multiset里的一个x
3 x 询问是否能从multiset中找出两个数使得他们和x能够构成一个非退化三角形
题解：
那么这道题我一看他就是个权值线段树，但是由于一些小bug，我调了几个小时，最后靠着队友的强力对拍才找到。。。太难了
首先我们知道对于操作3，有两种情况：
1.x是最大的边：那么就从set中找到比x小的最大的两个数判一下
2.x不是最大的边：那么就从权值线段树中找区间是x~all的这些位置中，差值最小的值。
那么我们首先离散化之后，用一个set存当前有哪些值，然后权值线段树存的是，每一个位置和当前比他小的最大的数的差。
然后更新的时候有三种情况：
1.当前没有这个点，就要更新这个位置和第一个比他大的位置的值，但是要注意，如果第一个比他大的位置有两个及以上的数的话，那就不能更新，因为它就是0
2.当前有一个这个点，那么将这个位置的值更新为0
3.当前有两个及以上的这个点，那么就不用变
删除也有三种情况，但是要注意下一个位置的点的数量是否大于等于两个（我就是这种情况没有想到卡了很久）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=4e5+5;
const ll inf=1e18;
ll mi[N*4];
void update(int l,int r,int root,int p,ll v){if(l==r){mi[root]=v;return ;}int mid=l+r>>1;if(mid>=p)update(l,mid,root<<1,p,v);elseupdate(mid+1,r,root<<1|1,p,v);mi[root]=min(mi[root<<1],mi[root<<1|1]);
}
ll query(int l,int r,int root,int ql,int qr){if(l>=ql&&r<=qr)return mi[root];int mid=l+r>>1;ll ans=inf;if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);if(mid<qr)ans=min(ans,query(mid+1,r,root<<1|1,ql,qr));return ans;
}
set<ll>s;
int num[N];
ll b[N];
struct node{int op;ll x;
}a[N];
int main()
{int n;scanf("%d",&n);for(int i=1;i<N*4;i++)mi[i]=inf;for(int i=1;i<=n;i++)scanf("%d%lld",&a[i].op,&a[i].x),b[i]=a[i].x;int cnt=n;b[++cnt]=-1,b[++cnt]=inf;sort(b+1,b+1+cnt);int all=unique(b+1,b+1+cnt)-b-1;s.insert(1),s.insert(all);update(1,all,1,all,inf+1);num[1]=num[all]=1;for(int i=1;i<=n;i++){a[i].x=lower_bound(b+1,b+1+all,a[i].x)-b;if(a[i].op==1){if(!num[a[i].x]){s.insert(a[i].x);set<ll>::iterator it=s.find(a[i].x),iit=it;it--,iit++;update(1,all,1,a[i].x,b[a[i].x]-b[*it]);if(num[*iit]==1)update(1,all,1,*iit,b[*iit]-b[a[i].x]);}else if(num[a[i].x]==1)update(1,all,1,a[i].x,0);num[a[i].x]++;}else if(a[i].op==2){if(num[a[i].x]==2){set<ll>::iterator it=s.find(a[i].x);it--;update(1,all,1,a[i].x,b[a[i].x]-b[*it]);}else if(num[a[i].x]==1){set<ll>::iterator it1=s.find(a[i].x),it2=it1;it1++,it2--;if(num[*it1]==1)update(1,all,1,*it1,b[*it1]-b[*it2]);update(1,all,1,a[i].x,inf);it1--;s.erase(it1);}//if(!num[a[i].x])while(1);num[a[i].x]--;}else{set<ll>::iterator it=s.upper_bound(a[i].x);it--;int f=0;if(num[*it]>=2){if(b[*it]*2>b[a[i].x])printf("Yes\n"),f=1;}else{//if(!num[*it])while(1);if(it!=s.begin()){set<ll>::iterator iit=it;iit--;//if(!num[*iit])while(1);if(b[*it]+b[*iit]>b[a[i].x])printf("Yes\n"),f=1;}//else//printf("No\n");}if(!f){if(query(1,all,1,a[i].x,all)<b[a[i].x])printf("Yes\n");elseprintf("No\n");}}}return 0;
}
/*
5
1 309
1 327
1 327
2 309
3 129*/这篇关于2020牛客暑期多校训练营（第二场）H Happy Triangle —— 权值线段树，离线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
