Happy Triangle(動態開點線段樹）
2021-08-10 10:08:25

Happy Triangle(動態開點線段樹）

思路：動態開點線段樹+ m a p map map維護集合。

對于詢問 1 , 2 1,2 1,2的插入和刪除操作用 m a p map map維護起來就行了。

對于詢問 3 3 3，我們只需要找到 a , b a,b a,b不妨設 a ≤ b aleq b a≤b,使得 a , b , x a,b,x a,b,x組成三角形。

顯然若 a , b , x a,b,x a,b,x能組成三角形，則 b ′ , b , x , ( b ′ ∈ ( a , b ] ) b',b,x,(b'in(a,b]) b′,b,x,(b′∈(a,b])也組成三角形。

因為 x ∈ ( b ? a , a + b ) , b ? b ′ < b ? a , b + b ′ > a + b xin(b-a,a+b),b-b'<b-a,b+b'>a+b x∈(b?a,a+b),b?b′<b?a,b+b′>a+b，使得區間更大，更能滿足情況，綜上即取 b b b的前驅即可。

因此我們考慮用線段樹維護每個數與前驅差值，因為數據范圍有 1 e 9 1e9 1e9，所以考慮離散化或者動態開點。

對每次詢問查詢第一個大于等于 x 2 + 1 dfrac{x}{2}+1 2x?+1的數，然后判斷一下最小差值是否小于 x x x，查詢第一個大于等于 x 2 + 1 dfrac{x}{2}+1 2x?+1的數保證了兩數之和大于 x x x，即上界，然后后面的判斷保證了下界。

時間復雜度： O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100,M=N*40,inf=1e9,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int m[M],ls[M],rs[M],cnt,rt;
map<int,int>mp;
void upd(int &id,int l,int r,int x,int val){
	if(!id) id=++cnt,m[id]=val;
	if(l==r){m[id]=val;return;}
	int mid=l+r>>1;
	if(x<=mid) upd(ls[id],l,mid,x,val);
	else upd(rs[id],mid+1,r,x,val);
	int ans=2e9;
	if(ls[id]&&m[ls[id]]<ans) ans=m[ls[id]];
	if(rs[id]&&m[rs[id]]<ans) ans=m[rs[id]];
	m[id]=ans;
}
void add(int x){
	mp[x]++;
	if(mp[x]==1){
		auto it=mp.lower_bound(x);
		++it;
		if(it!=mp.end()&&it->se==1)
			upd(rt,0,inf,it->first,it->first-x);
		--it;
		int pre=-2e9;
		if(it!=mp.begin()) pre=(--it)->first;
		upd(rt,0,inf,x,x-pre);
	}
	else if(mp[x]==2) upd(rt,0,inf,x,0);
}
void del(int x){
	int pre=-1e9;
	auto it=mp.lower_bound(x);
	mp[x]--;
	if(it!=mp.begin()) pre=(--it)->fi,++it;
	if(!mp[x]){
		if((++it)!=mp.end()&&it->se==1){
			upd(rt,0,inf,it->fi,it->fi-pre);
		}
		upd(rt,0,inf,x,2e9);
		mp.erase(x);
	}
	else if(mp[x]==1) upd(rt,0,inf,x,x-pre);
}
int ask(int x){
	auto it=mp.lower_bound(x/2+1);
	if(it==mp.end()) return 2e9;
	if(it->se>1) return it->first;
	if(it!=mp.begin()){	//這里是begin() 
		auto pre=it;--pre;
		if(pre->fi+it->fi>x) return it->fi;
	}
	if((++it)!=mp.end()) return it->fi;
	return 2e9;
}
int ask_min(int id,int l,int r,int L,int R){
	if(!id||l>r) return 2e9;
	if(L<=l&&R>=r) return m[id];
	int ans=2e9;
	int mid=l+r>>1;
	if(L<=mid) ans=min(ans,ask_min(ls[id],l,mid,L,R));
	if(R>mid) ans=min(ans,ask_min(rs[id],mid+1,r,L,R));
	return ans; 
}
int main(){
	int q,op,x;
	scanf("%d", &q);
    while(q--){
        scanf("%d%d", &op, &x);
        if(op == 1) add(x);
        if(op == 2) del(x);
        if(op == 3) {
            if(ask_min(1,0,inf,ask(x),1e9) < x) puts("Yes");
            else puts("No");
        }
    }
	return 0;
}