2020牛客暑期多校训练营（第二场）——H

Happy Triangle

链接：https://ac.nowcoder.com/acm/contest/5667/H
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Given a multiset {MS}MS and {q}q operations. {MS}MS is empty initailly, and operations are in three types, which are as follows:

1. insert an element {x}x into {MS}MS
2. erase an element {x}x from {MS}MS
3. given an integer {x}x, determine whether you can choose two elements {a, b}a,b in {MS}MS that three segments of length {a, b, x}a,b,x can make a nondegenerate triangle.
   输入描述:
   The first line contains an integer q~(1\leq q\leq 2\times 10^5)q (1≤q≤2×10
   5
   ), denoting the number of operations.
   Following {q}q lines each contains two integers op, x~(op \in {1,2,3}, 1\leq x\leq 10^9)op,x (op∈{1,2,3},1≤x≤10
   9
   ), denoting an operation
4. if {op = 1}op=1, insert an element {x}x into {MS}MS
5. if {op = 2}op=2, erase an element {x}x from {MS}MS, it’s guaranteed that there is at least one {x}x in {MS}MS currently
6. if {op = 3}op=3, determine whether you can choose two elements {a, b}a,b in {MS}MS that three segments of length {a, b, x}a,b,x can make a triangle
   输出描述:
   For each query, print one line containing a string “Yes” if the answer is yes or “No” if the answer is no.
   示例1
   输入
   复制
   8
   1 1
   3 1
   1 1
   3 2
   3 1
   1 2
   2 1
   3 1
   输出
   复制
   No
   No
   Yes
   No

题意：再一个序列中进行插入或删除操作，给定一个数，问从序列中选择两个数，这三个数能不能组成一个三角形。
题解：
先粘一下官方题解

我用线段树维护序列中相邻两个数之间的差值，来处理x不是最大边的情况。
先将操作全部记录下来，对所有的x进行离散化。然后建树维护即可。
注意考虑 等边三角形，等腰三角形等这些特殊情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
const int inf=2e9;
int n;
int a[N],b[N],op[N];
map<int,int>dis;
map<int,int>mp;
set<int>s;
struct Tree {
	int x,l,r;
} tr[N*4];
void updata(int p) {
	tr[p].x=min(tr[p*2].x,tr[p*2+1].x);
}
void build(int p,int l,int r) {
	tr[p].l=l,tr[p].r=r;
	if(l==r) {
		tr[p].x=inf;
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	updata(p);
}
void change(int p,int x,int val) {
	if(tr[p].l==tr[p].r) {
		tr[p].x=val;
		return;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	if(x<=mid)change(p*2,x,val);
	else change(p*2+1,x,val);
	updata(p);
}
int ask(int p,int L,int R) {
	if(L<=tr[p].l&&tr[p].r<=R) {
		return tr[p].x;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	int ans=inf;
	if(L<=mid)ans=min(ans,ask(p*2,L,R));
	if(R>mid)ans=min(ans,ask(p*2+1,L,R));
	return ans;
}
int solve() {
	sort(b+1,b+1+n);
	int cut=unique(b+1,b+1+n)-b-1;
	for(int i=1; i<=cut; ++i) {
		dis[b[i]]=i;
	}
	build(1,1,cut);
	set<int>::iterator it,itq,ith;
	for(int i=1; i<=n; ++i) {
		if(op[i]==1) {
			mp[a[i]]++;
			if(mp[a[i]]==1) {
				s.insert(a[i]);
				it=itq=ith=s.find(a[i]);
				itq--;
				ith++;
				if(it!=s.begin()) {
					change(1,dis[a[i]],a[i]-*itq);
				}
				if(ith!=s.end()&&mp[*ith]==1) {
					change(1,dis[*ith],*ith-a[i]);
				}
			} else {
				change(1,dis[a[i]],0);
			}
		} else if(op[i]==2) {
			mp[a[i]]--;
			if(mp[a[i]]==0) {
				it=itq=ith=s.find(a[i]);
				itq--;
				ith++;
				change(1,dis[a[i]],inf);
				if(ith!=s.end()&&mp[*ith]==1) {
					if(it!=s.begin()) {
						change(1,dis[*ith],*ith-*itq);
					} else {
						change(1,dis[*ith],inf);
					}
				}
				s.erase(a[i]);
			} else if(mp[a[i]]==1) {
				it=itq=ith=s.find(a[i]);
				itq--;
				ith++;
				if(it!=s.begin()) {
					change(1,dis[a[i]],a[i]-*itq);
				} else {
					change(1,dis[a[i]],inf);
				}
			}
		} else {
			itq=it=ith=s.lower_bound(a[i]);
			if(mp[a[i]]>1) {
				printf("Yes\n");
				continue;
			} else if(mp[a[i]]==1) {
				if(it!=s.begin()) {
					printf("Yes\n");
					continue;
				}
			} else {
				if(it!=s.begin()) {
					itq--;
					if(mp[*itq]>=2) {
						if((*itq)*2>a[i]) {
							printf("Yes\n");
							continue;
						}
					} else {
						if(itq!=s.begin()) {
							if(*itq+*(--itq)>a[i]) {
								printf("Yes\n");
								continue;
							}
						}
					}
				}
			}
			if(ask(1,dis[a[i]],cut)<a[i]) {
				printf("Yes\n");
			} else {
				printf("No\n");
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d %d",&op[i],&a[i]);
		b[i]=a[i];
	}
	solve();
	return 0;
}