题意
给一个空的(multiset)和(q)次操作，操作有三种。
- 向(multiset)插入一个数(x)。
- 从(multiset)中删除一个数(x)。
- 给你一个(x)，问能不能从(multiset)中找出两个数(a,b)使得它们作为边长能够构成一个三角形。
分析
对于每个询问操作分类讨论：
- (a<=b<=x)，找到最大的(a)和(b)，看是否能构成三角形
- (a<=x<=b)，找到最大的(a)和最小的(b)，看是否能构成三角形
- (x<=a<=b)，需满足(x+a>b)，即(x>b-a)，我们需要找到相邻的差最小的两个数，可以离线将所有(x)离散化一下，以(x)为下标开线段树，点(x)维护(x)和左边相邻的数的差，支持查询区间最小值即可。
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=2e5+10;
const int inf=1e9+10;
int q;
set<int>st,ts;
int tr[N<<2];
int op[N],x[N],b[N],cnt[N],tot;
void bd(int l,int r,int p){
if(l==r) return tr[p]=inf,void();
int mid=l+r>>1;
bd(lson);bd(rson);
tr[p]=min(tr[p<<1],tr[p<<1|1]);
}
void up(int x,int l,int r,int p,int k){
if(l==r) return tr[p]=k,void();
int mid=l+r>>1;
if(x<=mid) up(x,lson,k);
else up(x,rson,k);
tr[p]=min(tr[p<<1],tr[p<<1|1]);
}
int qy(int dl,int dr,int l,int r,int p){
if(l==dl&&r==dr) return tr[p];
int mid=l+r>>1;
if(dr<=mid) return qy(dl,dr,lson);
else if(dl>mid) return qy(dl,dr,rson);
else return min(qy(dl,mid,lson),qy(mid+1,dr,rson));
}
void upd(int x){
auto l=st.lower_bound(x);
if(l!=st.begin()){
--l;
up(x,1,tot,1,b[x]-b[*l]);
}else up(x,1,tot,1,inf);
auto r=st.upper_bound(x);
if(r!=st.end()){
up(*r,1,tot,1,b[*r]-b[x]);
}
}
void ins(int x){
cnt[x]++;
if(cnt[x]>1) return;
upd(x);
st.insert(x);
}
void del(int x){
if(--cnt[x]!=0) return;
st.erase(st.lower_bound(x));
up(x,1,tot,1,inf);
auto r=st.upper_bound(x);
if(r!=st.end()){
auto l=st.upper_bound(x);
if(l!=st.begin()){
--l;
up(*r,1,tot,1,b[*r]-b[*l]);
}else up(*r,1,tot,1,inf);
}
}
bool ck1(int x){
if(cnt[x]>=3) return true;
if(cnt[x]==2){
auto it=st.lower_bound(x);
if(it!=st.begin()) return true;
else return false;
}else{
auto it=st.lower_bound(x);
int y,z;
if(it!=st.begin()){
--it;
y=*it;
if(cnt[y]>=2) z=*it;
else{
if(it!=st.begin()){
--it;
z=*it;
}else return false;
}
}else return false;
return b[y]+b[z]>b[x];
}
}
bool ck2(int x){
auto its=ts.upper_bound(x);
if(its!=ts.end()) return true;
if(cnt[x]==2){
auto it=st.upper_bound(x);
if(it!=st.end()){
return b[x]+b[x]>b[*it];
}return false;
}else{
auto r=st.upper_bound(x);
auto l=st.lower_bound(x);
int y,z;
if(l!=st.begin()){
--l;
y=*l;
}else return false;
if(r!=st.end()){
z=*r;
}else return false;
return b[y]+b[x]>b[z];
}
}
bool ck3(int x){
auto it=st.upper_bound(x);
if(it==st.end()) return false;
++it;
if(it==st.end()) return false;
return b[x]>qy(*it,tot,1,tot,1);
}
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
scanf("%d",&q);
rep(i,1,q){
scanf("%d%d",&op[i],&x[i]);
b[++tot]=x[i];
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
bd(1,tot,1);
rep(i,1,q){
int k=lower_bound(b+1,b+tot+1,x[i])-b;
if(op[i]==1){
ins(k);
if(cnt[k]==2) ts.insert(k);
}else if(op[i]==2){
del(k);
if(cnt[k]==1) ts.erase(ts.find(k));
}else{
ins(k);
if(cnt[k]==2) ts.insert(k);
if(ck1(k)){
puts("Yes");
}else if(ck2(k)){
puts("Yes");
}else if(ck3(k)){
puts("Yes");
}else puts("No");
del(k);
if(cnt[k]==1) ts.erase(ts.find(k));
}
}
return 0;
}