BZOJ - 3224 Tyvj 1728 普通平衡树 splay

#include <algorithm>
#include  <iterator>
#include  <iostream>
#include   <cstring>
#include   <cstdlib>
#include   <iomanip>
#include    <bitset>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include    <vector>
#include     <stack>
#include     <cmath>
#include     <queue>
#include      <list>
#include       <map>
#include       <set>
#include   <cassert>

using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000")  //c++
// #pragma GCC diagnostic error "-std=c++11"
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)

#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue



typedef long long ll;
typedef unsigned long long ull;

typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl ‘\n‘

#define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行
#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)
#define max3(a,b,c) max(max(a,b), c);
//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //2147483647
const ll nmos = 0x80000000;  //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //18
// const int mod = 10007;
const double esp = 1e-8;
const double PI=acos(-1.0);
const double PHI=0.61803399;    //黄金分割点
const double tPHI=0.38196601;


template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<‘0‘||ch>‘9‘) f|=(ch==‘-‘),ch=getchar();
    while (ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x=f?-x:x;
}


/*-----------------------showtime----------------------*/
#define root e[0].ch[1]
        const int maxn = 100009;
        struct node{
            int v,father;
            int ch[2];
            int sum;
            int recy;
        }e[maxn];
        int n,points;

        void update(int x){
            e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + e[x].recy;
        }
        int identify(int x){
            return e[e[x].father].ch[0] == x?0:1;
        }

        int crepoint(int v, int father){
            n++;
            e[n].v = v;
            e[n].father = father;
            e[n].sum = e[n].recy = 1;
            return n;
        }
        void destory(int x){
            e[x].v = e[x].ch[0] = e[x].ch[1] = e[x].sum = e[x].father = e[x].recy = 0;
            if(x == n)n--;
        }

        void connect(int x,int f,int son){
            e[x].father = f;
            e[f].ch[son] = x;
        }
        void rotate(int x){
            int y = e[x].father;
            int mroot = e[y].father;
            int mrootson = identify(y);
            int yson = identify(x);
            int B = e[x].ch[yson^1];
            connect(B,y,yson);
            connect(y,x,(yson^1));
            connect(x,mroot,mrootson);
            update(y);update(x);
        }

        void splay(int at,int to){
            to = e[to].father;
            while(e[at].father != to){
                int up = e[at].father;
                if(e[up].father == to)rotate(at);
                else if(identify(up) == identify(at)){
                    rotate(up);
                    rotate(at);
                }
                else {
                    rotate(at);
                    rotate(at);
                }
            }
        }

        int find(int v){
            int now = root;
            while(true){
                if(e[now].v == v){
                    splay(now,root);
                    return now;
                }
                int next = v < e[now].v?0:1;
                if(!e[now].ch[next])return 0;
                now = e[now].ch[next];
            }
        }

        int build(int v){
            points++;
            if(root == 0){root = 1; crepoint(v, 0);return 1;}
            else{
                int now = root;
                while(true){
                    e[now].sum++;
                    if(v == e[now].v){
                        e[now].recy++;
                        return now;
                    }
                    int next = v < e[now].v?0:1;
                    if(!e[now].ch[next]){
                        crepoint(v,now);
                        e[now].ch[next] = n;
                        return n;
                    }
                    now = e[now].ch[next];
                }
                return now;
            }
        }
        void push(int v){
            int add = build(v);

            splay(add, root);

        }
        void pop(int v){
            int deal = find(v);
            if(deal == 0)return;
            points--;
            if(e[deal].recy > 1){
                e[deal].recy--;
                e[deal].sum--;
                return;
            }
            if(!e[deal].ch[0]){
                root = e[deal].ch[1];
                e[root].father = 0;
            }
            else {
                int lef = e[deal].ch[0];
                while(e[lef].ch[1]) lef = e[lef].ch[1];
                splay(lef, e[deal].ch[0]);
                int rig = e[deal].ch[1];
                connect(rig,lef,1); connect(lef,0,1);
                update(lef);
            }
        }

        int upper(int v){
            int g = root,now = root;
            int result = inf;
            while(now){
                if(e[now].v > v && e[now].v < result)result = e[now].v,g = now;
                if(v < e[now].v) now = e[now].ch[0];
                else now = e[now].ch[1];
            }
            if(g!=root)splay(g,root);
            return result;
        }

        int lower(int v){
            int g = root,now = root;
            int result = -inf;
            while(now){
                if(e[now].v < v && e[now].v > result)result = e[now].v,g = now;
                if(v > e[now].v) now = e[now].ch[1];
                else now = e[now].ch[0];
            }
            if(g!=root)splay(g,root);
            return result;
        }

        int Rank(int v){

            int ans = 0, now = root;
            //debug(now);
            while(true){
                if(e[now].v == v)return ans + e[e[now].ch[0]].sum + 1;
                if(now == 0)return 1;
                if(v < e[now].v) now = e[now].ch[0];
                else{
                    ans = ans + e[e[now].ch[0]].sum + e[now].recy;
                    now = e[now].ch[1];
                }
            }
            if(now) splay(now,root);
            return 0;
        }
        int atrank(int x){
            if(x > points)return -inf;
            int now = root;
            while(true){
                int minused = e[now].sum - e[e[now].ch[1]].sum;
                if(x > e[e[now].ch[0]].sum && x <= minused)break;
                if(x < minused) now = e[now].ch[0];
                else{
                    x = x - minused;
                    now = e[now].ch[1];
                }
            }
            splay(now,root);
            return e[now].v;
        }
int main(){
        int t;
        scanf("%d", &t);
        while(t--){
            int op,x;
            scanf("%d%d", &op, &x);
            if(op == 1) push(x);
            else if(op == 2)pop(x);
            else if(op == 3)printf("%d\n",Rank(x));
            else if(op == 4)printf("%d\n", atrank(x));
            else if(op == 5)printf("%d\n", lower(x));
            else printf("%d\n", upper(x));
        }

        return 0;
}