Nowcoder Muti-School Training 2 H Happy Triangle multiset + splay平衡树

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题目大意

维护一个多重集合,支持三种操作:

  • 1 : 加入一个x
  • 2 : 删除一个x
  • 3 : 询问当前在多重集中,是否存在两个数a,b,使得x能与a,b组成一个合法的三角形

题解

这题有线段树动态建点和离线离散化建线段树的做法,但是平衡树的做法一定是最好想的。

考虑查询操作我们可以假设下面两种情况:

  1. x为唯一最大边,则要a,b都小于x,于是只需要找比x更小的两个前驱作为a,b,判断a+b>x是否成立即可。
  2. x不是唯一最大边,假设b≥a,于是我们需要b≥x && b - a < x,而b-a最小的条件一定是b确定的情况下,a是b的一个非严格前驱,这样我们只需要找x的后缀最小值就行了。

第一种情况非常简单,直接用multiset维护、查询就行了,只需要注意一下边界问题。

第二种情况比较麻烦,没法用STL做,所以就用平衡树维护。平衡树维护的信息为子树内相邻两数差的最小值,排序的键值为当前数的大小,查询答案的时候,找到x的后缀节点,然后判断此节点与前一个节点的差mnval和其右子树中的相邻两数差的最小值mn中的最小值是否<x即可。

需要注意考虑边界问题。

最后提示的一点,s.lower_bound(x)和s.upper_bound(x)是比lower_bound(s.begin(),s.end(),x)和upper_bound(s.beign(),s.end(),x)要快不少的。我就被坑了……。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
multiset<int>s;
const int maxn = 2e5+5;
typedef pair<int,int> PI;
struct splay_node{
    int siz;
    PI val;
    int mn;
    splay_node *fa,*ch[2];
    void update(){
        mn = min(val.second,min(ch[0]->mn,ch[1]->mn));
    }
    void set_ch(int type,splay_node *child);
    int get_wh(){
        return (this == this->fa->ch[0]) ? 0 : 1;
    }
}*root,pool[maxn<<1],*null;
int cnt = 0;
void splay_node::set_ch(int type,splay_node *child){
    this->ch[type] = child;
    if(child != null){
        child->fa = this;
    }
    update();
    return;
}
splay_node *newnode(int val,int mn){
    splay_node *newone = pool + ++cnt;
    newone->val = make_pair(val,mn);
    newone->siz = 1;
    newone->mn = mn;
    newone->fa = newone->ch[0] = newone->ch[1] = null;
    return newone;
}
void init(){
    cnt = 0;
    null = pool;
    null->mn = INF;
    null->fa = null->ch[0] = null->ch[1] = null;
    null->val = make_pair(-1,-1);
    null->siz = 0;
    root = null;
    return;
}
void rotate(splay_node *&now){
    splay_node *oldfa = now->fa;
    splay_node *grand = now->fa->fa;
    int wh = now->get_wh();
    oldfa->set_ch(wh,now->ch[wh^1]);
    now->set_ch(wh^1,oldfa);
    now->fa = grand;
    if(grand != null){
        grand->ch[grand->ch[0] == oldfa ? 0 : 1] = now;
    }
    return;
}
void splay(splay_node *now,splay_node *tar){
    for(;now->fa != tar;rotate(now)){
        if(now->fa->fa == tar)continue;
        if(now->get_wh() == now->fa->get_wh())
            rotate(now->fa);
        else rotate(now);
    }
    if(tar == null)root = now;
    return;
}
void insert(int vl,int mn){
    splay_node *now = root;
    splay_node *last = null;
    PI val = make_pair(vl,mn);
    while(now != null){
        last = now;
        if(val == now->val){
            now->siz++;
            return;
        }
        if(val > now->val){
            now = now->ch[1];
        }
        else now = now->ch[0];
    }
    splay_node *newone = newnode(vl,mn);
    if(last == null){
        root = newone;
        return;
    }
    else{
        if(newone->val < last->val)last->set_ch(0,newone);
        else last->set_ch(1,newone);
        splay(newone,null);
    }
    return;
}
splay_node *find(PI val){
    splay_node *now = root;
    while(now != null){
        if(now->val == val)break;
        if(now->val < val)now = now->ch[1];
        else now = now->ch[0];
    }
    if(now != null)splay(now,null);
    return now;
}
void del(PI val){
    splay_node *now = find(val);
    if(now == null)return;
    if(now->siz > 1){
        now->siz--;
        return;
    }
    if(now->ch[0] == null && now->ch[1] == null)root = null;
    else if(now->ch[1] == null){
        now->ch[0]->fa = null;
        root = now->ch[0];
    }
    else if(now->ch[0] == null){
        now->ch[1]->fa = null;
        root = now->ch[1];
    }
    else{
        splay_node *one = now->ch[0];
        while(one->ch[1] != null)one = one->ch[1];
        splay(one,now);
        one->set_ch(1,now->ch[1]);
        one->fa = null;
        root = one;
    }
    return;
}
void nxt(int val){
    int ans = INF;
    splay_node *now = root;
    splay_node *last = null;
    while(now != null){
        if(now->val.first >= val){
            last = now;
            ans = min(ans,now->val.first);
            now = now->ch[0];
        }
        else now = now->ch[1];
    }
    if(last != null)splay(last,null);
    return;
}
int num = 0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    init();
    int q,op,x;
    cin >> q;
    s.insert(INF);
    insert(-INF,INF);
    insert(INF,INF);
    while(q--){
        cin >> op >> x;
        switch(op){
            case 1 : {              
                auto it = s.upper_bound(x);
                if(it == s.end()){
                    num++;
                    s.insert(x);
                    insert(x,INF);
                    break;
                }
                auto nxit = it;
                num++;
                if(it != s.begin()){
                    it--;
                    del(make_pair(*nxit,*nxit - *it));
                    insert(x,x-*it);
                }
                s.insert(x);
                insert(*nxit,*nxit-x);
                break;
            }
            case 2 : {
                auto it = s.find(x);
                if(it != s.end()){
                    s.erase(it);
                    auto it1 = s.upper_bound(x);
                    auto it2 = it1;
                    if(it1 != s.begin()){
                        it1--;
                        del(make_pair(x,x - *it1));
                        insert(*it2,*it2 - *it1);
                    }
                    del(make_pair(*it2,*it2 - x));
                    num--;
                }
                break;
            }
            case 3 : {
                if(num < 2){
                    cout << "No\n";
                    break;
                }
                auto it = s.lower_bound(x);
                if(it != s.begin()){
                    int vala = *(--it);
                    if(it != s.begin()){
                        int valb = *(--it);
                        if(vala + valb > x){
                            cout << "Yes\n";
                            break;
                        }
                    }
                }
                nxt(x);
                if(root != null){
                    int mn = root->val.second;
                    mn = min(mn,root->ch[1]->mn);
                    if(mn < x){
                        cout << "Yes\n";
                        break;
                    }
                }
                cout << "No\n";
                break;
            }    
        }
    }
    return 0;
}

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00