2020牛客暑期多校训练营（第二场） H、Happy Triangle （平衡树、线段树）

题面：

题意：
给定一个多重集合，有以下三种操作。
1。往集合里面插入一个数x。
2。从集合里面删除数x。
3。给定x询问集合中是否有两个数a,b，使得a，b，x三个数能组成一个非退化的三角形。（就是正常的三角形）。

官方题解：

题解：
考虑每个询问 x。
我们设有其他两边 a<=b
若x是最长的边，那么需要a+b>x，我们可以选择小于x的最大的和次大的数来判断。
若x不是最长边，那么需要a+x>b，转化一下，x>b-a 我们可以找最小的 b-a 来判断。

我们需要找小于x的最大的和次大的数，维护一个最小的b-a。
找小于x的最大的数和次大的数，是平衡树的基本操作。
维护b-a时，我们可以维护一个子树中的最小差值，子树最大值和子树最小值，然后转移即可。

其实这个玩意,感觉动态开点线段树也可？

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=2e9+10;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int up=100000;
#define int ll
struct node
{
    int val;
    int lc,rc;
    int si,cnt;
    int minn,mi,ma;
}t[maxn];
int tot,root;



void pushup(int p)
{
    t[p].si=t[t[p].lc].si+t[t[p].rc].si+1;
    t[p].mi=min(t[p].val,min(t[t[p].lc].mi,t[t[p].rc].mi));
    t[p].ma=max(t[p].val,max(t[t[p].lc].ma,t[t[p].rc].ma));
    t[p].minn=min(t[t[p].lc].minn,t[t[p].rc].minn);
    //这里注意处理，因为0号节点mi设置为了inf，ma设置为了-inf，t[t[p].rc].mi-t[p].val ，t[p].val-t[t[p].lc].ma就有可能为0了。
    t[p].minn=min(t[p].minn,min(t[p].rc==0?inf:t[t[p].rc].mi-t[p].val,t[p].lc==0?inf:t[p].val-t[t[p].lc].ma));
    t[p].minn=(t[p].cnt>=2?0:t[p].minn);
}


int newnode(int x)
{
    int p=++tot;
    t[p].lc=t[p].rc=0;
    t[p].cnt=t[p].si=1;
    t[p].val=t[p].mi=t[p].ma=x;
    t[p].minn=inf;
    return p;
}

void R(int &p)
{
    int q=t[p].lc;
    t[p].lc=t[q].rc;
    t[q].rc=p;
    p=q;
    pushup(t[p].rc);
    pushup(p);

}

void L(int &p)
{
    int q=t[p].rc;
    t[p].rc=t[q].lc;
    t[q].lc=p;
    p=q;
    pushup(t[p].lc);
    pushup(p);
}

void RL(int &p)
{
    R(t[p].rc);
    L(p);
}

void LR(int &p)
{
    L(t[p].lc);
    R(p);
}


int getmin(int p)
{
    while(t[p].lc) p=t[p].lc;
    return p;
}

int getmax(int p)
{
    while(t[p].rc) p=t[p].rc;
    return p;
}

void maintain(int &p,bool flag)
{
    if(!flag)
    {
        if(t[t[t[p].lc].lc].si>t[t[p].rc].si)
            R(p);
        else if(t[t[t[p].lc].rc].si>t[t[p].rc].si)
            LR(p);
        else return ;
    }
    else
    {
        if(t[t[t[p].rc].rc].si>t[t[p].lc].si)
            L(p);
        else if(t[t[t[p].rc].lc].si>t[t[p].lc].si)
            RL(p);
        else return ;
    }
    maintain(t[p].lc,false);
    maintain(t[p].rc,true);
    maintain(p,true);
    maintain(p,false);
}

void _insert(int &now,int val)
{
    if(!now)
    {
        now=newnode(val);
        return ;
    }
    if(val<t[now].val)
    {
        _insert(t[now].lc,val);
        maintain(now,false);
    }
    else if(val>t[now].val)
    {
        _insert(t[now].rc,val);
        maintain(now,true);
    }
    else
    {
        t[now].cnt++;
    }
    pushup(now);
}

void del(int &p,int x)
{
    if(x<t[p].val)
        del(t[p].lc,x);
    else if(x>t[p].val)
        del(t[p].rc,x);
    else
    {
        if(t[p].cnt>1)
        {
            t[p].cnt--;

        }
        else
        {
             if(t[p].lc&&t[p].rc)
            {
                int q=getmax(t[p].lc);
                t[p].val=t[q].val;
                t[p].cnt=t[q].cnt;
                t[q].cnt=1;
                del(t[p].lc,t[q].val);
            }
            else
            {
                if(t[p].lc) p=t[p].lc;
                else p=t[p].rc;
                return ;
            }
        }
    }
    pushup(p);
}


int get_rank(int x)
{
    int now=root,ans=0;
    while(now)
    {
        if(t[now].val<x) ans+=t[t[now].lc].si+1,now=t[now].rc;
        else now=t[now].lc;
    }
    return ans+1;
}

int get_val(int k)
{
    int now=root;
    while(1)
    {
        if(t[t[now].lc].si+1==k) return t[now].val;
        else if(t[t[now].lc].si>=k) now=t[now].lc;
        else k-=t[t[now].lc].si+1,now=t[now].rc;
    }
}

int get_front(int x)
{
    int now=root,ans=-inf;
    while(now)
    {
        if(t[now].val<x) ans=max(ans,t[now].val),now=t[now].rc;
        else now=t[now].lc;
    }
    return ans;
}

int get_behind(int x)
{
    int now=root,ans=inf;
    while(now)
    {
        if(t[now].val>x) ans=min(ans,t[now].val),now=t[now].lc;
        else now=t[now].rc;
    }
    return ans;
}

int find_val(int x)
{
    int now=root,ans=inf;
    int maxx=-inf;
    while(now)
    {
        if(t[now].val>=x)
        {
            ans=min(ans,t[now].cnt>=2?0ll:inf);
            ans=min(ans,min(t[t[now].rc].minn,t[now].rc==0?inf:t[t[now].rc].mi-t[now].val));
            //这里还是要注意t[now].val-max(t[t[now].lc].ma,maxx) 可能为0而导致结果错误。
            ans=min(ans,(t[now].lc==0&&maxx==-inf)?inf:t[now].val-max(t[t[now].lc].ma,maxx));
            now=t[now].lc;
        }
        //这里维护一个最大值，是因为找到某些符合要求的b的时候，需要找一个最大的a
        else maxx=max(maxx,t[now].val),now=t[now].rc;
    }
    return ans;
}

void init()
{
     t[0].minn=inf;
     t[0].ma=-inf;
     t[0].mi=inf;
    _insert(root,-inf);
    _insert(root,inf);
}

signed main(void)
{
    int q,op,x;
    init();
    scanf("%lld",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%lld%lld",&op,&x);
        if(op==1)
        {
            _insert(root,x);
        }
        else if(op==2)
        {
            del(root,x);
        }
        else
        {
            int pre=get_front(x);
            if(pre!=-inf)
            {
                int prepre=get_front(pre);
                {
                    if(pre+prepre>x)
                    {
                        printf("Yes\n");
                        continue;
                    }
                }
            }
            if(find_val(x)<x)
            {
                printf("Yes\n");
                continue;
            }
            printf("No\n");
        }
    }
    return 0;
}

动态开点线段树：
离线加离散化也可。
线段树上，叶子节点维护值为 pos 的数与其前面的最近的数的差。
pushup的时候维护最小值。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int up=1e9;

struct node
{
    int lc,rc;
    int val;
}t[maxn*35];
int root,cnt;
map<int,int>mp;

int newnode(void)
{
    cnt++;
    t[cnt].lc=t[cnt].rc=0;
    return cnt;
}

void pushup(int p)
{
    t[p].val=min(t[t[p].lc].val,t[t[p].rc].val);
}

int change(int p,int l,int r,int pos,int val)
{
    if(!p) p=newnode();
    if(l==r)
    {
        t[p].val=val;
        return p;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) t[p].lc=change(t[p].lc,l,mid,pos,val);
    else t[p].rc=change(t[p].rc,mid+1,r,pos,val);
    pushup(p);
    return p;
}

int ask(int p,int l,int r,int pos)
{
    if(!p) return inf;
    if(l==r) return t[p].val;
    int mid=(l+r)>>1;
    if(pos<=mid) return min(ask(t[p].lc,l,mid,pos),t[t[p].rc].val);
    else return ask(t[p].rc,mid+1,r,pos);
}

void add(int x)
{
    mp[x]++;
    if(mp[x]==1)
    {
        auto it=mp.lower_bound(x);
        it++;
        if(it!=mp.end()&&it->second==1)
            root=change(root,1,up,it->first,it->first-x);
        it--;
        int pre=-inf;
        if(it!=mp.begin()) pre=(--it)->first;
            root=change(root,1,up,x,x-pre);
    }
    else if(mp[x]==2) root=change(root,1,up,x,0);
}

void del(int x)
{
    auto it=mp.lower_bound(x);
    mp[x]--;
    int pre=-inf;
    if(it!=mp.begin()) pre=prev(it)->first;
    if(mp[x]==0)
    {
        if(++it!=mp.end()&&it->second==1)
            root=change(root,1,up,it->first,it->first-pre);
        root=change(root,1,up,x,inf);
        mp.erase(x);
    }
    else if(mp[x]==1) root=change(root,1,up,x,x-pre);

}

void ans(int x)
{
    auto it=mp.lower_bound(x);
    if(it!=mp.begin())
    {
        int a=(--it)->first;
        if(it!=mp.begin())
        {
            int b=(--it)->first;
            if(a+b>x)
            {
                printf("Yes\n");
                return ;
            }
        }
    }
    if(ask(root,1,up,x)<x) printf("Yes\n");
    else printf("No\n");
    return ;
}

int main(void)
{
    t[0].val=inf;
    int q,op,x;
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==1) add(x);
        else if(op==2) del(x);
        else ans(x);
    }
    return 0;
}