【線段樹/模拟/牛客多校第二場H】Happy Triangle

連結：https://ac.nowcoder.com/acm/contest/5667/H

來源：牛客網

題目描述

Given a multiset MS and q operations. MSs empty initailly, and operations are in three types, which are as follows:

1. insert an element x into MS

2. erase an element x from MS

3. given an integer x, determine whether you can choose two elements a,b in MS that three segments of length a,b,xcan make a nondegenerate triangle.

輸入描述:

The first line contains an integer q (1≤q≤2×1e5), denoting the number of operations.

Following q{q}q lines each contains two integers op,x (op∈{1,2,3},1≤x≤1e9), denoting an operation

1. if op=1, insert an element xinto MS

2. if op=2, erase an element xfrom MS. it's guaranteed that there is at least one x in MScurrently

3. if op=3, determine whether you can choose two elements a,b in MS that three segments of length 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.
      

輸入

8
1 1
3 1
1 1
3 2
3 1
1 2
2 1
3 1      

輸出

No
No
Yes
No      

思路：

插入删除用multiset即可（

若從集合裡取出x,y(x<=y),提出給出z，問是否組成三角形，則将組成的三角形分為三種形況：

1.x<=y<=z，這種情況需要滿足x+y>z,則需找到小于等于z的最大xy看是否滿足不等式；

2.x<z<y，這種情況需要滿足z>y-x,則需要找到大于z的最小y與小于z的最大x看是否滿足不等式；

3.z<=x<=y，這種情況需要滿足z>y-x，則建立一棵線段樹維護集合中存在數字的最小內插補點。當插入删除一個數字時，隻對旁邊兩個數字造成影響。

題目需要離散化，注意寫代碼仔細一點（

代碼：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef multiset<int>::iterator iter;
const int N=2e5+10,M=N*3;
int tree[M];
int op[N],id[N];
int n,m;
int disc[N];//儲存離散化後的數字
multiset<int>st;//儲存集合中的數字
void init(){
    memcpy(disc,id,sizeof(id));
    sort(disc+1,disc+1+n);
    m=unique(disc+1,disc+1+n)-disc-1;
    //for(int i = 1; i <= m; i++)cout<<disc[i]<<endl;
}
int get_id(int x){
    return lower_bound(disc+1,disc+1+m,x)-disc;
}
void build(int root,int l,int r){
    tree[root]=inf;
    if(l==r)return;
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
}
void update(int x,int y,int root,int l,int r){
    if(l==r){
        tree[root]=y;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)update(x,y,root*2,l,mid);
    else update(x,y,root*2+1,mid+1,r);
    tree[root]=min(tree[root*2],tree[root*2+1]);
}
int query(int x,int y,int root,int l,int r){
    if(x<=l&&y>=r)return tree[root];
    int mid=(l+r)/2,ans=inf;
    if(x<=mid)ans=min(ans,query(x,y,root*2,l,mid));
    if(y>mid)ans=min(ans,query(x,y,root*2+1,mid+1,r));
    return ans;
}
bool check1(int z){//x<=y<=z ==> x+y>z
    int x,y;
    iter r = st.upper_bound(z);
    if(r==st.begin())return false;
    r--,x=*r;
    if(r==st.begin())return false;
    r--,y=*r;
    if(x+y>z)return true;
    return false;
}
bool check2(int z){//x<z<y ==> z>y-x
    int x,y;
    iter r = st.lower_bound(z);
    if(r==st.begin())return false;
    r--;x=*r;
    r = st.upper_bound(z);
    if(r==st.end())return false;
    y=*r;
    if(z>y-x)return true;
    return false;
}
void solve(int choice,int x){
    int val=disc[x];
    if(choice==1){
        if(st.count(val)>=1)//已經有這個數字了
            update(x,0,1,1,m);
        else{
            iter r=st.upper_bound(val),l=r;//找到第一個比val大的數的位置
            if(r!=st.end()) update(x,*r-val,1,1,m);
            else update(x,inf,1,1,m);
            if(l!=st.begin()){
                l--;
                if(st.count(*l)==1)update(get_id(*l),val-*l,1,1,m);
            }
        }
        st.insert(val);
    }
    else if(choice==2){
        st.erase(st.find(val));
        iter r=st.upper_bound(val),l=r;//找到第一個比val大的數的位置
        if(st.count(val)==1){
            if(r!=st.end())update(x,*r-val,1,1,m);
            else update(x,inf,1,1,m);
        }
        else if(st.count(val)==0){
            update(x,inf,1,1,m);
            if(l!=st.begin()){
                l--;
                if(st.count(*l)>1)return;
                if(r!=st.end())update(get_id(*l),*r-*l,1,1,m);
                else update(get_id(*l),inf,1,1,m);
            }
        }
    }
    else{
       if(check1(val))printf("Yes\n");//x<=y<=z ==> x+y>z
       else if(check2(val))printf("Yes\n");//x<z<y ==> z>y-x
       else if(val>query(x,m,1,1,m))printf("Yes\n");//z<=x<=y ==> z>y-x == >y-x最小
       else printf("No\n");
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)scanf("%d%d",&op[i],&id[i]);
    init();//離散化
    for(int i = 1; i <= n; i++)id[i]=get_id(id[i]);//,cout<<id[i]<<endl;//轉化成下标
    build(1,1,m);
    for(int i = 1; i <= n; i++)solve(op[i],id[i]);
}
/*
5
1 2
1 6
1 3
1 5
1 4

5
1 2
1 6
1 3
1 3
1 4
*/