洛谷P3835 【模板】可持久化平衡树

题目背景

本题为题目 普通平衡树 的可持久化加强版。

数据已经经过强化

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)
  3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)
  6. 求x的后继(后继定义为大于x,且最小的数,如不存在输出2147483647)

和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化)

每个版本的编号即为操作的序号(版本0即为初始状态,空树)

输入输出格式

输入格式:

第一行包含一个正整数N,表示操作的总数。

接下来每行包含三个正整数,第 ii 行记为 v_i, opt_i, x_ivi​,opti​,xi​。

v_ivi​表示基于的过去版本号( 0 \leq v_i < i0≤vi​<i ),opt_iopti​ 表示操作的序号( 1 \leq opt \leq 61≤opt≤6 ), x_ixi​ 表示参与操作的数值

输出格式:

每行包含一个正整数,依次为各个3,4,5,6操作所对应的答案

输入输出样例

输入样例#1:

10
0 1 9
1 1 3
1 1 10
2 4 2
3 3 9
3 1 2
6 4 1
6 2 9
8 6 3
4 5 8

输出样例#1:

9
1
2
10
3

说明

数据范围:

对于10%的数据满足: 1 \leq n \leq 101≤n≤10

对于30%的数据满足: 1 \leq n \leq 2\cdot {10}^21≤n≤2⋅102

对于50%的数据满足: 1 \leq n \leq 3\cdot {10}^31≤n≤3⋅103

对于80%的数据满足: 1 \leq n \leq {10}^51≤n≤105

对于90%的数据满足: 1 \leq n \leq 2\cdot {10}^51≤n≤2⋅105

对于100%的数据满足: 1 \leq n \leq 5\cdot {10}^51≤n≤5⋅105 , -{10}^9 \leq x_i \leq {10}^9−109≤xi​≤109

经实测,正常常数的可持久化平衡树均可通过,请各位放心

样例说明:

共10次操作,11个版本,各版本的状况依次是:

  1. [][]
  2. [9][9]
  3. [3, 9][3,9]
  4. [9, 10][9,10]
  5. [3, 9][3,9]
  6. [9, 10][9,10]
  7. [2, 9, 10][2,9,10]
  8. [2, 9, 10][2,9,10]
  9. [2, 10][2,10]
  10. [2, 10][2,10]
  11. [3, 9][3,9]

也是没谁了

数据压根就没有5.6的21***的情况

而且不知道为啥我的样例没过就A了。。

#include<bits/stdc++.h>
using namespace std;
#define ls tree[k].ch[0]
#define rs tree[k].ch[1]
const int MAXN=1e6+10,INF=1e7;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
struct node
{
    int pri,v,ch[2],siz;
}tree[MAXN];
int x,y,z,tot=0,root[MAXN];
int new_node(int val)
{
    tree[++tot].pri=rand()*rand(),tree[tot].v=val,tree[tot].siz=1;
    return tot;
}
void update(int k){   tree[k].siz=tree[ls].siz+tree[rs].siz+1; }
void split(int now,int k,int &x,int &y)
{
    if(!now)  {x=y=0;return ;}
    if(tree[now].v<=k)  x=now,split(tree[now].ch[1],k,tree[now].ch[1],y);
    else y=now,split(tree[now].ch[0],k,x,tree[now].ch[0]);
    update(now);
}
int merge(int x,int y)
{
    if(!x||!y)  return x+y;
    if(tree[x].pri<tree[y].pri) {tree[x].ch[1]=merge(tree[x].ch[1],y),update(x);return x;}
    else {tree[y].ch[0]=merge(x,tree[y].ch[0]),update(y);return y;}
}
int kth(int k,int x)// 查询排名 
{
    if(x<=tree[ls].siz)           return kth(ls,x);
    else if(x==tree[ls].siz+1)    return k;
    else return kth(rs,x-tree[ls].siz-1);
}
int main()
{ 
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else 
    #endif
    srand((unsigned)time(NULL));
    int n=read();
    for(int i=1;i<=n;i++)
    {
        int pre=read(),how=read(),a=read();
        root[i]=root[pre];     
        if(how==1)      split(root[i],a,x,y),root[i]=merge(merge(x,new_node(a)),y);
        else if(how==2) split(root[i],a,x,z),split(x,a-1,x,y),y=merge(tree[y].ch[0],tree[y].ch[1]),root[i]=merge(merge(x,y),z);
        else if(how==3) split(root[i],a-1,x,y),printf("%d\n",tree[x].siz+1),root[i]=merge(x,y);
        else if(how==4) printf("%d\n",tree[kth(root[i],a)].v);
        else if(how==5)    split(root[i],a-1,x,y),printf("%d\n",tree[kth(x,tree[x].siz)].v),root[i]=merge(x,y);
        else if(how==6) split(root[i],a,x,y),printf("%d\n",tree[kth(y,1)].v),root[i]=merge(x,y);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王亚昌的专栏

FFMPEG-如何对视频按时长切片与压缩

本文介绍如何用ffmpeg开源组件按时长进行切片,举一个例子,一个视频网站,拿到一个时长1.5小时的电影,用户点击播放时,常用的技术方案就是把一个完整的大文件,...

17810
来自专栏腾讯技术工程官方号的专栏

后台开发中的时空转换艺术

作者介绍:augustzhang,安全平台部基础架构组员工,先后从事密保、验证码等后台研发工作,现在主要负责安全平台部大数据平台的研发工作,致力于研究每秒GB级...

22170
来自专栏架构说

Effective STL(21) 永远让比较函数对相同元素返回false

问题描述: 昨天一哥们些的程序,在定义比较函数的时候是这样写的 bool cmp(const T& a, const T& b) { if (a >=...

38790
来自专栏漏斗社区

HASH函数烧脑大作战

本期讲解一下hash函数,由于之前在比赛中做到了一题hash有关的题目,引发了此次的深(烧)度(脑)研究,本来想讲讲原理,但是太难,看得很痛苦,所以此次通过结合...

14250
来自专栏小樱的经验随笔

Gym 100952I&&2015 HIAST Collegiate Programming Contest I. Mancala【模拟】

I. Mancala time limit per test:3 seconds memory limit per test:256 megabytes inp...

30340
来自专栏图形学与OpenGL

WebGL画点程序v3

本文程序实现画一个点的任务,如下图。其中,点的颜色由Javascript传到片元着色器程序中。

15120
来自专栏大数据智能实战

tensorflow.models.rnn.rnn_cell.linear在tensorflow1.0版本之后找不到(附tensorflow1.0 API新变化)

由于版本更新关系,从原来的tensorflow低版本到升级到tensorflow1.0以上时,发现有很多API函数变化是很正常的事情,大多碰到的如: 如其中tf...

33170
来自专栏WOLFRAM

用 Wolfram 语言绘制电子轨道

16050
来自专栏Jerry的SAP技术分享

Association, Composition and Aggregation in UI5, CRM, S/4HANA and C4C

比如UI5的转盘控件Carousel: 一旦转盘被析构,里面显示的page当然也没有继续存在的意义了,需要跟着被析构。

31250
来自专栏前端开发

你不知道的console.log

对于前端开发者,使用console.log() 次数绝对很多,但是大部分人认识的 console 对象还不是很全面,其实深入了解这些后,你会发现给开发过程带来很...

59740

扫码关注云+社区

领取腾讯云代金券