【模板】普通平衡树 Splay-白红宇

【模板】普通平衡树 Splay

阅读量：6902 次

发布时间：2019-06-27

本文共 4137 字，大约阅读时间需要 13 分钟。

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入

删除

查询

查询排名为

输入输出格式

输入格式：

第一行为 $\leq opt \leq 6 1≤opt≤6 )$

输出格式：

对于操作

输入输出样例

输入样例#1：

101 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 493598

输出样例#1：

10646584185492737

说明

时空限制：1000ms,128M

1.n的数据范围： $\leq 100000 n≤100000$

2.每个数的数据范围： ${10}^7][−107,107]$

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

Splay Tree 即可；而且好写；

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       //#include
                       
                        //#pragma GCC optimize(2)using namespace std;#define maxn 400005#define inf 0x7fffffff//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-3typedef pair
                        
                          pii;#define pi acos(-1.0)const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                         
                           pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}ll sqr(ll x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/int rt, n, tot = 0;struct node { int ch[2]; int ff; int cnt; int val; int son;}e[maxn<<1];void pushup(int u) { e[u].son = e[e[u].ch[0]].son + e[e[u].ch[1]].son + e[u].cnt;}void rotate(int x) { int y = e[x].ff; int z = e[y].ff; int k = (e[y].ch[1] == x); e[z].ch[e[z].ch[1] == y] = x; e[x].ff = z; e[y].ch[k] = e[x].ch[k ^ 1]; e[e[x].ch[k ^ 1]].ff = y; e[x].ch[k ^ 1] = y; e[y].ff = x; pushup(y); pushup(x);}void splay(int x, int aim) { while (e[x].ff != aim) { int y = e[x].ff; int z = e[y].ff; if (z != aim) { (e[y].ch[0] == x) ^ (e[z].ch[0] == y) ? rotate(x) : rotate(y); } rotate(x); } if (aim == 0)rt = x;}void ins(int x) { int u = rt, ff = 0; while (u&&e[u].val != x) { ff = u; u = e[u].ch[x > e[u].val]; } if (u)e[u].cnt++;// 已经存在 else { u = ++tot;// 总的节点数目 if (ff)e[ff].ch[x > e[ff].val] = u; e[tot].ch[0] = 0; e[tot].ch[1] = 0; e[tot].ff = ff; e[tot].val = x; e[tot].cnt = 1; e[tot].son = 1; } splay(u, 0);}void Find(int x) { // 查找x的位置 int u = rt; if (u == 0)return; while (e[u].ch[x > e[u].val] && x != e[u].val) { u = e[u].ch[x > e[u].val]; } splay(u, 0);}int nxt(int x, int f) { Find(x); int u = rt; if ((e[u].val > x&&f) || (e[u].val < x && !f))return u; u = e[u].ch[f]; while (e[u].ch[f ^ 1])u = e[u].ch[f ^ 1]; return u;}void del(int x) { int last = nxt(x, 0); int Next = nxt(x, 1); splay(last, 0); splay(Next, last); int delt = e[Next].ch[0]; if (e[delt].cnt > 1) { e[delt].cnt--; splay(delt, 0); } else e[Next].ch[0] = 0;}int k_th(int x) { // rank==x int u = rt; if (e[u].son < x)return false; while (1) { int y = e[u].ch[0]; if (x > e[y].son + e[u].cnt) { x -= e[y].son + e[u].cnt; u = e[u].ch[1]; } else if (e[y].son >= x)u = y; else return e[u].val; }}int main(){ //ios::sync_with_stdio(0); ins(inf); ins(-inf); rdint(n); for (int i = 0; i < n; i++) { int op; rdint(op); int x; if (op == 1) { rdint(x); ins(x); } if (op == 2) { rdint(x); del(x); } if (op == 3) { rdint(x); Find(x); cout << e[e[rt].ch[0]].son << endl; } if (op == 4) { rdint(x); cout << k_th(x+1) << endl; } if (op == 5) { rdint(x); cout << e[nxt(x, 0)].val << endl; } if (op == 6) { rdint(x); cout << e[nxt(x, 1)].val << endl; } } return 0;}