三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 洛谷P3835 【模板】可持久化平衡树 -> 正文阅读
 

[C++]洛谷P3835 【模板】可持久化平衡树

洛谷P3835 【模板】可持久化平衡树 题目背景
本题为题目 普通平衡树 的可持久化加强版。
数据已经经过强化
题目描述
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):
插入x数
删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)
查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)
求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个版本,各版本的状况依次是:
[][]
[9][9]
[3, 9][3,9]
[9, 10][9,10]
[3, 9][3,9]
[9, 10][9,10]
[2, 9, 10][2,9,10]
[2, 9, 10][2,9,10]
[2, 10][2,10]
[2, 10][2,10]
[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;
}

  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
1267 老鼠的旅行 2012年CCC加拿大高中生信息
项目中进度条实现臆想
遗传算法
简单的传球游戏(矩阵)
上一篇文章      下一篇文章      查看所有文章
加:2017-12-09 23:28:03  更:2017-12-09 23:28:09 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-20 7:12:04
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库