[BZOJ3224]普通平衡树_weixin_34204722的博客-程序员ITS203

技术标签: 数据结构与算法  

Problem

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个)
  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

Solution

Treap模板题:
Treap为一种节点的优先级满足堆性质的二叉搜索树。
非旋转Treap:
代码较短,常数较Splay较小,比旋转Treap稍大。但因为不是旋转的,所以支持区间操作和可持久化。
最主要的操作为Merge,Split
建树方法参照笛卡尔树的建树方法。
推荐网站:http://memphis.is-programmer.com/posts/46317.html
旋转Treap:
常数十分的小,非常的好用,但不支持区间操作和可持久化。
主要操作为单旋:左旋和右旋

Notice

还不够熟练,很容易打错

Code

非旋转Treap

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define sqz main
#define ll long long
#define reg register int
#define pairint pair<int, int>
#define rep(i, a, b) for (reg i = a; i <= b; i++)
#define per(i, a, b) for (reg i = a; i >= b; i--)
#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)
const int INF = 1e9, N = 100000;
const double eps = 1e-6, phi = acos(-1.0);
ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}
ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}
void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}
int point = 0, root, a[N + 5];
struct node
{
    int Size[N + 5], Val[N + 5], Level[N + 5], Son[2][N + 5];
    inline void up(int u)
    {
        Size[u] = Size[Son[0][u]] + Size[Son[1][u]] + 1;
    }
    int Newnode(int v)
    {
        int u = ++point;
        Val[u] = v, Level[u] = rand();
        Son[0][u] = Son[1][u] = 0, Size[u] = 1;
        return u;
    }
    int Merge(int X, int Y)
    {
        if (X * Y == 0) return X + Y;
        if (Level[X] < Level[Y])
        {
            Son[1][X] = Merge(Son[1][X], Y);
            up(X); return X;
        }
        else
        {
            Son[0][Y] = Merge(X, Son[0][Y]);
            up(Y); return Y;
        }
    }
    void Split(int u, int t, int &x, int &y)
    {
        if (!u)
        {
            x = y = 0;
            return;
        }
        if (Val[u] <= t) x = u, Split(Son[1][u], t, Son[1][u], y);
        else y = u, Split(Son[0][u], t, x, Son[0][u]);
        up(u);
    }
    void Build(int l, int r)
    {
        int last, u, s[N + 5], top = 0;
        rep(i, l, r)
        {
            int u = Newnode(a[i]);
            last = 0;
            while (top && Level[s[top]] < Level[u])
            {
                up(s[top]);
                last = s[top];
                s[top--] = 0;
            }
            if (top) Son[1][s[top]] = u;
            Son[0][u] = last;
            s[++top] = u;
        }
        while (top) up(s[top--]);
        root = s[1];
    }
    int Find_rank(int v)
    {
        int x, y, t;
        Split(root, v - 1, x, y);
        t = Size[x];
        root = Merge(x, y);
        return t + 1;
    }
    int Find_num(int u, int v)
    {
        if (!u) return 0;
        if (v <= Size[Son[0][u]]) return Find_num(Son[0][u], v);
        else if (v <= Size[Son[0][u]] + 1) return u;
        else return Find_num(Son[1][u], v - Size[Son[0][u]] - 1);
    }
    void Insert(int v)
    {
        int t = Newnode(v), x, y;
        Split(root, v, x, y);
        root = Merge(Merge(x, t), y);
    }
    void Delete(int v)
    {
        int x, y, z;
        Split(root, v, x, z), Split(x, v - 1, x, y);
        root = Merge(Merge(x, Merge(Son[0][y], Son[1][y])), z);
    }
}Treap;
int sqz()
{
    int n = read(), x = 0, y = 0;
    while (n--)
    {
        int op = read(), t = read();
        switch (op)
        {
            case 1: Treap.Insert(t); break;
            case 2: Treap.Delete(t); break;
            case 3: printf("%d\n", Treap.Find_rank(t)); break;
            case 4: printf("%d\n", Treap.Val[Treap.Find_num(root, t)]); break;
            case 5: Treap.Split(root, t - 1, x, y);
                    printf("%d\n", Treap.Val[Treap.Find_num(x, Treap.Size[x])]);
                    root = Treap.Merge(x, y); break;
            case 6: Treap.Split(root, t, x, y);
                    printf("%d\n", Treap.Val[Treap.Find_num(y, 1)]);
                    root = Treap.Merge(x, y); break;
        }
    }
    return 0;
}

旋转Treap

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define sqz main
#define ll long long
#define reg register int
#define rep(i, a, b) for (reg i = a; i <= b; i++)
#define per(i, a, b) for (reg i = a; i >= b; i--)
#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)
const int INF = 1e9, N = 100000;
const double eps = 1e-6, phi = acos(-1.0);
ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}
ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}
void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}
int point = 0, pre, suf, root;
struct node
{
    int Val[N + 5], Level[N + 5], Size[N + 5], Son[2][N + 5], Num[N + 5];
    inline void up(int u)
    {
        Size[u] = Size[Son[0][u]] + Size[Son[1][u]] + Num[u];
    }
    inline void Newnode(int &u, int v)
    {
        u = ++point;
        Level[u] = rand(), Val[u] = v;
        Size[u] = Num[u] = 1, Son[0][u] = Son[1][u] = 0;
    }
    inline void Lturn(int &x)
    {
        int y = Son[1][x]; Son[1][x] = Son[0][y], Son[0][y] = x;
        Size[y] = Size[x]; up(x); x = y;
    }
    inline void Rturn(int &x)
    {
        int y = Son[0][x]; Son[0][x] = Son[1][y], Son[1][y] = x;
        Size[y] = Size[x]; up(x); x = y;
    }
    
    void Insert(int &u, int t)
    {
        if (u == 0)
        {
            Newnode(u, t);
            return;
        }
        Size[u]++;
        if (t == Val[u]) Num[u]++;
        else if (t < Val[u])
        {
            Insert(Son[0][u], t);
            if (Level[Son[0][u]] < Level[u]) Rturn(u);
        }
        else if (t > Val[u])
        {
            Insert(Son[1][u], t);
            if (Level[Son[1][u]] < Level[u]) Lturn(u);
        }
    }
    void Delete(int &u, int t)
    {
        if (!u) return;
        if (Val[u] == t)
        {
            if (Num[u] > 1)
            {
                Num[u]--, Size[u]--;
                return;
            }
            if (Son[0][u] * Son[1][u] == 0) u = Son[0][u] + Son[1][u];
            else if (Level[Son[0][u]] < Level[Son[1][u]]) Rturn(u), Delete(u, t);
            else Lturn(u), Delete(u, t);
        }
        else if (t < Val[u]) Size[u]--, Delete(Son[0][u], t);
        else Size[u]--, Delete(Son[1][u], t);
    }
    
    int Find_rank(int u, int t)
    {
        if (!u) return 0;
        if (Val[u] == t) return Size[Son[0][u]] + 1;
        else if (t < Val[u]) return Find_rank(Son[0][u], t);
        else return Size[Son[0][u]] + Num[u] + Find_rank(Son[1][u], t);
    }
    int Find_num(int u, int t)
    {
        if (!u) return 0;
        if (t <= Size[Son[0][u]]) return Find_num(Son[0][u], t);
        else if (t <= Size[Son[0][u]] + Num[u]) return Val[u];
        else return Find_num(Son[1][u], t - Size[Son[0][u]] - Num[u]);
    }
    void Find_pre(int u, int t)
    {
        if (!u) return;
        if (t > Val[u])
        {
            pre = u;
            Find_pre(Son[1][u], t);
        }
        else Find_pre(Son[0][u], t);
    }
    void Find_suf(int u, int t)
    {
        if (!u) return;
        if (t < Val[u])
        {
            suf = u;
            Find_suf(Son[0][u], t);
        }
        else Find_suf(Son[1][u], t);
    }
}Treap;
int sqz()
{
    int n = read();
    while (n--)
    {
        int op = read(), x = read();
        switch (op)
        {
            case 1: Treap.Insert(root, x); break;
            case 2: Treap.Delete(root, x); break;
            case 3: printf("%d\n", Treap.Find_rank(root, x)); break;
            case 4: printf("%d\n", Treap.Find_num(root, x)); break;
            case 5: pre = 0, Treap.Find_pre(root, x); printf("%d\n", Treap.Val[pre]); break;
            case 6: suf = 0, Treap.Find_suf(root, x); printf("%d\n", Treap.Val[suf]); break;
        }
    }
}

转载于:https://www.cnblogs.com/WizardCowboy/p/7643644.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34204722/article/details/94519744

智能推荐

模仿微视视频录制、支持按下录制抬起暂停以及断点进度条(基于javacv)_qdrzwd2的博客-程序员ITS203

apk下载视频录制apk下载,项目源码地址为https://github.com/qdrzwd/VideoRecorder  现在应该已经有很多人知道Vine和Instagram。前者做短视频分享起家后被Twitter收购, 后者做照片分享起家后被Facebook收购,随后也迅速添加了视频分享功能。   可以说,短视频分享是社交网络适应移动互联网发展的大趋势。短视频分享应用已经...

minikube 结合阿里云镜像搭建本地开发测试环境_minikube aliyun_DevStream的博客-程序员ITS203

我的同事Daniel Hu写了一篇英文的博客,关于如何使用 minikube 搭建本地的 k8s 环境的。

mysql 按时间排序 取每5条数据的平均值、评价数_Hy_164274021的博客-程序员ITS203

建表语句:CREATE TABLE `trade_params1` ( `ID` int(11) NOT NULL AUTO_INCREMENT, `PERIOD` int(11) DEFAULT NULL, `THEDATE` date DEFAULT NULL, `DAYCOUNT` int(11) DEFAULT NULL, PRIMARY KEY (`ID`))...

二叉树应用-表达式·表达式树·表达式求值(数据结构基础 第6周)_NodYoung的博客-程序员ITS203

问题描述 分析 有点麻烦,这道题还没做。大概想了一下,首先应该是由中缀表达式可转换为后缀表达式( 栈与队列-等价表达式(数据结构基础 第3周))。然后可以由中缀和后缀构建出整棵树(二叉树基础-由中根序列和后根序列重建二叉树(数据结构基础 第5周))。后缀表达式可直接带入数值进行等式计算。 详情参考:http://blog.csdn.net/u014391294/article/deta

Qt工作笔记-QMenu::exec中使用QWidget::mapToGlobal()与QCursor::pos()之间的些许差异_IT1995的博客-程序员ITS203_qmenu exec

源码如下:widget.h#ifndef WIDGET_H#define WIDGET_H#include &amp;lt;QWidget&amp;gt;namespace Ui {class Widget;}class Widget : public QWidget{ Q_OBJECTpublic: explicit Widget(QWidget *parent...

c++小游戏代码(5个) 免费_小游戏代码编程_studyhard520的博客-程序员ITS203

DEV-C++的编程内容十分受限,想编游戏更是天方夜谭,但总有大神,我为大家准备了5个dev-c++就能编的程序

随便推点

Android 开发调试工具_胡椒粉0121的博客-程序员ITS203_安卓调试工具

Android 开发调试工具—ADBADB的用途在Android Studio中工作时,手机插口需要连接其他设备因此无法用线与电脑连接,因此可以利用Android Studio内嵌的命令台通过adb实现WIFI连接手机与电脑。什么是ADBAndroid调试桥(Android Debug Bridge)是多种用途的调试工具,帮助管理设备或模拟器的状态ADB常用命令Android Studio 利用 ADB WIFI 插件实现真机无线调试Android 开发调试工具—DDMS

socket编程函数简介 --send recv read write_马鸿凯_新浪博客_Ma_Hong_Kai的博客-程序员ITS203

部上上一博客不足之处socket编程里面的通过send和recv实现客户端服务器的交互tcp 里面的read和write则是对发送的数据进行读,和写入将要发送的数据http://blog.csdn.net/u011408355/article/details/45921541上面的博客记录的很仔细。。。一旦,我们建立好了tcp连接之后,我们就可以把得到的fd当作文件描述符来使...

android TeleComm Telephony Dialer之间的说明_蚁人日记的博客-程序员ITS203_teleservice

安卓在5.0之后在TeleService和IncallUI之间多加了一层TeleComm,个人感觉是不想让IncallUI和Phone进程联系过于紧密,也便于其他通话方式的添加(不仅仅局限于通过电信运营商拨打传统电话),上文出自:https://blog.csdn.net/qq_35427437/article/details/102963199学习android的通讯模块Telephony,那么先看下其框架结构:应用层:包含android的应用程序应用框架层:也就是常说的framewor

虚拟现实在招聘中的应用_Kaikai?的博客-程序员ITS203

来源:物联之家(iothome.com)虚拟现实(VR)在招聘中的部署将解决几个挑战,如寻找合适的人才、在全球范围内面试候选人、员工培训等。企业的目标是在他们认为有必要时,立即吸引和雇用到有能力的人才。即使是美国经济也有利于增加新的就业机会,美国经济在2018年12月创造了31.2万个新的就业机会,这是过去三年来就业人数增幅最大的一次。由于工作岗位的增加,用人单位正在相互竞争,以寻找最...

推荐文章

热门文章

相关标签