非旋treap没有旋转操作，而是变成了分裂和合并两个部分。
例①：P3369 【模板】普通平衡树：
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1。插入x数
2。删除x数(若有多个相同的数，因只删除一个)
3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4。查询排名为xx的数
5。求x的前驱(前驱定义为小于x，且最大的数)
6。求x的后继(后继定义为大于x，且最小的数)
输入格式
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1≤opt≤6 )
输出格式
对于操作3,4,5,63,4,5,6每行输出一个数，表示对应答案
输入输出样例
输入 #1 复制
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出 #1 复制
106465
84185
492737
说明/提示
时空限制：1000ms,128M
1.n的数据范围： n≤100000
2.每个数的数据范围： [-{10} ^ 7, {10} ^ 7]
来源：Tyvj1728 原名：普通平衡树
在此鸣谢
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr pair<int,int>
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=100100;
const int mod=1e9+7;
struct Treap
{
int l,r;//左右子节点在数组中的下标
int val,dat;//节点关键码，权值
int si;//子树大小
}t[maxn];
int tot=0,root=0,n;
int New(int val)
{
t[++tot].val=val;
t[tot].dat=rand();
t[tot].si=1;
t[tot].l=t[tot].r=0;
return tot;
}
void update(int p)
{
t[p].si=t[t[p].l].si+t[t[p].r].si+1;
}
int _merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].dat<t[y].dat)
{
t[x].r=_merge(t[x].r,y);
update(x);
return x;
}
else
{
t[y].l=_merge(x,t[y].l);
update(y);
return y;
}
}
pr split(int x,int k)
{
if(!x) return pr(0,0);
pr y;
if(t[t[x].l].si<k)
{
y=split(t[x].r,k-t[t[x].l].si-1);
t[x].r=y.first;
update(x);
y.first=x;
}
else
{
y=split(t[x].l,k);
t[x].l=y.second;
update(x);
y.second=x;
}
return y;
}
int get_rank_by_val(int rt,int val)
{
int ans=inf,res=0;
int x=rt;
while(x)
{
if(val==t[x].val) ans=min(ans,res+t[t[x].l].si+1);
if(val>t[x].val) res+=t[t[x].l].si+1,x=t[x].r;
else x=t[x].l;
}
return ans==inf?res:ans;
}
int get_val_by_rank(int k)
{
pr x=split(root,k-1),y=split(x.second,1);
root=_merge(_merge(x.first,y.first),y.second);
return t[y.first].val;
}
void _insert(int val)
{
int k=get_rank_by_val(root,val);
pr x=split(root,k);
int rt=New(val);
root=_merge(_merge(x.first,rt),x.second);
}
void del(int val)
{
int k=get_rank_by_val(root,val);
pr x=split(root,k-1),y=split(x.second,1);
root=_merge(x.first,y.second);
}
int get_pre(int val)
{
int ans=-inf;
int p=root;
while(p)
{
if(t[p].val<val) ans=max(ans,t[p].val),p=t[p].r;
else p=t[p].l;
}
return ans;
}
int get_next(int val)
{
int ans=inf;
int p=root;
while(p)
{
if(t[p].val>val) ans=min(ans,t[p].val),p=t[p].l;
else p=t[p].r;
}
return ans;
}
int main(void)
{
int n;
int pos,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&pos,&x);
if(pos==1) _insert(x);
else if(pos==2) del(x);
else if(pos==3) printf("%d\n",get_rank_by_val(root,x));
else if(pos==4) printf("%d\n",get_val_by_rank(x));
else if(pos==5) printf("%d\n",get_pre(x));
else if(pos==6) printf("%d\n",get_next(x));
}
return 0;
}
例②：P3391 【模板】文艺平衡树（Splay）：
题目背景
这是一道经典的Splay模板题——文艺平衡树。
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
输入格式
第一行为n,m n表示初始序列有n个数，这个序列依次是 (1,2,⋯n−1,n) m表示翻转操作次数
接下来m行每行两个数 [l,r] 数据保证 1≤l≤r≤n
输出格式
输出一行n个数字，表示原始序列经过m次变换后的结果
输入输出样例
输入 #1 复制
5 3
1 3
1 3
1 4
输出 #1 复制
4 3 2 1 5
说明/提示
n,m≤100000
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr pair<int,int>
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=100100;
const int mod=1e9+7;
struct Treap
{
int l,r;//左右子节点在数组中的下标
int val,dat;//节点关键码，权值
int si;//子树大小
int rev;
}t[maxn];
int tot=0,root=0,n;
int newnode(int val)
{
t[++tot].val=val;
t[tot].dat=rand();
t[tot].si=1;
t[tot].l=t[tot].r=t[tot].rev=0;
return tot;
}
void update(int p)
{
t[p].si=t[t[p].l].si+t[t[p].r].si+1;
}
void re(int x)
{
if(!x) return ;
swap(t[x].l,t[x].r);
t[x].rev^=1;
}
void pushdown(int x)
{
if(!x) return ;
if(t[x].rev)
{
re(t[x].l);
re(t[x].r);
t[x].rev=0;
}
}
int _merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].dat<t[y].dat)
{
pushdown(x);
t[x].r=_merge(t[x].r,y);
update(x);
return x;
}
else
{
pushdown(y);
t[y].l=_merge(x,t[y].l);
update(y);
return y;
}
}
pr split(int x,int k)
{
if(!x) return pr(0,0);
pr y;
pushdown(x);
if(t[t[x].l].si<k)
{
y=split(t[x].r,k-t[t[x].l].si-1);
t[x].r=y.first;
update(x);
y.first=x;
}
else
{
y=split(t[x].l,k);
t[x].l=y.second;
update(x);
y.second=x;
}
return y;
}
void build(int n)
{
for(int i=1;i<=n;i++)
root=_merge(root,newnode(i));
}
void _reverse(int l,int r)
{
pr x=split(root,l-1),y=split(x.second,r-l+1);
re(y.first);
root=_merge(_merge(x.first,y.first),y.second);
}
void dfs(int now)
{
if(!now) return ;
pushdown(now);
dfs(t[now].l);
printf("%d ",t[now].val);
dfs(t[now].r);
}
int main(void)
{
int n,m;
int x,y;
scanf("%d%d",&n,&m);
build(n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
_reverse(x,y);
}
dfs(root);
return 0;
}
例③：P3835 【模板】可持久化平衡树：
题目背景
本题为题目 普通平衡树 的可持久化加强版。
数据已经经过强化
感谢@Kelin 提供的一组hack数据
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作（对于各个以往的历史版本）：
1。插入x数
2。删除x数(若有多个相同的数，因只删除一个，如果没有请忽略该操作)
3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4。查询排名为x的数
5。求x的前驱(前驱定义为小于x，且最大的数，如不存在输出-2147483647)
6。求x的后继(后继定义为大于x，且最小的数，如不存在输出2147483647)
和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化）
每个版本的编号即为操作的序号（版本0即为初始状态，空树）
输入格式
第一行包含一个正整数N，表示操作的总数。
接下来每行包含三个整数，第 i 行记为 v opt, x
v表示基于的过去版本号（0≤v <i ），opt 表示操作的序号( 1≤opt≤6 )， x表示参与操作的数值
输出格式
每行包含一个正整数，依次为各个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
说明/提示
数据范围：
对于100%的数据满足： 1≤n≤5⋅10e5
经实测，正常常数的可持久化平衡树均可通过，请各位放心
样例说明：
共10次操作，11个版本，各版本的状况依次是：
0。[]
1。[9]
2。[3, 9]
3。[9, 10]
4。[3, 9]
5。[9, 10]
6。[2, 9, 10]
7。[2, 9, 10]
8。[2, 10]
9。[2, 10]
10。[3, 9]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr pair<int,int>
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=500100;
const int mod=1e9+7;
struct Treap
{
int l,r;//左右子节点在数组中的下标
int val,dat;//节点关键码，权值
int si;//子树大小
}t[maxn*50];
int tot=0,root[maxn],n;
int newnode(int val)
{
t[++tot].val=val;
t[tot].dat=rand();
t[tot].si=1;
t[tot].l=t[tot].r=0;
return tot;
}
void update(int p)
{
t[p].si=t[t[p].l].si+t[t[p].r].si+1;
}
int _merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].dat<t[y].dat)
{
int p=++tot;
t[p]=t[x];
t[p].r=_merge(t[p].r,y);
update(p);
return p;
}
else
{
int p=++tot;
t[p]=t[y];
t[p].l=_merge(x,t[p].l);
update(p);
return p;
}
}
pr split(int x,int val)
{
if(!x) return pr(0,0);
pr y;
if(t[x].val<=val)
{
int p=++tot;
t[p]=t[x];
y=split(t[p].r,val);
t[p].r=y.first;
update(p);
y.first=p;
}
else
{
int p=++tot;
t[p]=t[x];
y=split(t[p].l,val);
t[p].l=y.second;
update(p);
y.second=p;
}
return y;
}
void del(int &root,int val)
{
pr x=split(root,val-1),y=split(x.second,val);
root=_merge(t[y.first].l,t[y.first].r);
root=_merge(_merge(x.first,root),y.second);
}
void _insert(int &root,int val)
{
pr x=split(root,val);
int rt=newnode(val);
root=_merge(_merge(x.first,rt),x.second);
}
int get_val_by_rank(int p,int rk)
{
if(rk==t[t[p].l].si+1) return t[p].val;
else if(t[t[p].l].si>=rk) return get_val_by_rank(t[p].l,rk);
else return get_val_by_rank(t[p].r,rk-t[t[p].l].si-1);
}
int get_rank_by_val(int &root,int val)
{
pr x=split(root,val-1);
int ans=t[x.first].si+1;
root=_merge(x.first,x.second);
return ans;
}
int get_pre(int &root,int val)
{
pr x=split(root,val-1);
if(x.first==0) return -2147483647;
int ans=get_val_by_rank(x.first,t[x.first].si);
root=_merge(x.first,x.second);
return ans;
}
int get_next(int &root,int val)
{
pr x=split(root,val);
if(x.second==0) return 2147483647;
int ans=get_val_by_rank(x.second,1);
root=_merge(x.first,x.second);
return ans;
}
int main(void)
{
int n;
int vi,pos,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&vi,&pos,&x);
root[i]=root[vi];
if(pos==1) _insert(root[i],x);
else if(pos==2) del(root[i],x);
else if(pos==3) printf("%d\n",get_rank_by_val(root[i],x));
else if(pos==4) printf("%d\n",get_val_by_rank(root[i],x));
else if(pos==5) printf("%d\n",get_pre(root[i],x));
else if(pos==6) printf("%d\n",get_next(root[i],x));
}
return 0;
}
实际上分裂的时候复制过节点了，合并的时候就没有必要再复制一次了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr pair<int,int>
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=500100;
const int mod=1e9+7;
struct Treap
{
int l,r;//左右子节点在数组中的下标
int val,dat;//节点关键码，权值
int si;//子树大小
}t[maxn*30];
int tot=0,root[maxn],n;
int newnode(int val)
{
t[++tot].val=val;
t[tot].dat=rand();
t[tot].si=1;
t[tot].l=t[tot].r=0;
return tot;
}
void update(int p)
{
t[p].si=t[t[p].l].si+t[t[p].r].si+1;
}
int _merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].dat<t[y].dat)
{
t[x].r=_merge(t[x].r,y);
update(x);
return x;
}
else
{
t[y].l=_merge(x,t[y].l);
update(y);
return y;
}
}
pr split(int x,int val)
{
if(!x) return pr(0,0);
pr y;
if(t[x].val<=val)
{
int p=++tot;
t[p]=t[x];
y=split(t[p].r,val);
t[p].r=y.first;
update(p);
y.first=p;
}
else
{
int p=++tot;
t[p]=t[x];
y=split(t[p].l,val);
t[p].l=y.second;
update(p);
y.second=p;
}
return y;
}
void del(int &root,int val)
{
pr x=split(root,val-1),y=split(x.second,val);
root=_merge(t[y.first].l,t[y.first].r);
root=_merge(_merge(x.first,root),y.second);
}
void _insert(int &root,int val)
{
pr x=split(root,val);
int rt=newnode(val);
root=_merge(_merge(x.first,rt),x.second);
}
int get_val_by_rank(int p,int rk)
{
if(rk==t[t[p].l].si+1) return t[p].val;
else if(t[t[p].l].si>=rk) return get_val_by_rank(t[p].l,rk);
else return get_val_by_rank(t[p].r,rk-t[t[p].l].si-1);
}
int get_rank_by_val(int &root,int val)
{
pr x=split(root,val-1);
int ans=t[x.first].si+1;
root=_merge(x.first,x.second);
return ans;
}
int get_pre(int &root,int val)
{
pr x=split(root,val-1);
if(x.first==0) return -2147483647;
int ans=get_val_by_rank(x.first,t[x.first].si);
root=_merge(x.first,x.second);
return ans;
}
int get_next(int &root,int val)
{
pr x=split(root,val);
if(x.second==0) return 2147483647;
int ans=get_val_by_rank(x.second,1);
root=_merge(x.first,x.second);
return ans;
}
int main(void)
{
int n;
int vi,pos,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&vi,&pos,&x);
root[i]=root[vi];
if(pos==1) _insert(root[i],x);
else if(pos==2) del(root[i],x);
else if(pos==3) printf("%d\n",get_rank_by_val(root[i],x));
else if(pos==4) printf("%d\n",get_val_by_rank(root[i],x));
else if(pos==5) printf("%d\n",get_pre(root[i],x));
else if(pos==6) printf("%d\n",get_next(root[i],x));
}
return 0;
}
例④：P5055 【模板】可持久化文艺平衡树：
题目背景
这是一道模板题。
题目描述
您需要写一种数据结构，来维护一个序列，其中需要提供以下操作（对于各个以往的历史版本）：
1。在第 p 个数后插入数 x 。
2。删除第 p 个数。
3。翻转区间 [l,r]，例如原序列是{5,4,3,2,1}，翻转区间 [2,4]后，结果是 {5,2,3,4,1}。
4。查询区间 [l,r] 中所有数的和。
和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 4 即保持原版本无变化），新版本即编号为此次操作的序号。
本题强制在线。
输入格式
第一行包含一个正整数 N，表示操作的总数。
接下来 N 行，每行前两个整数 vi,opti,
vi表示基于的过去版本号 (0≤vi<i)，
opti表示操作的序号(1≤opti≤4)。
若 opti=1，则接下来两个整数 pi,xi,表示操作为在第 pi个数后插入数 x 。
若 opti=2，则接下来一个整数 pi,表示操作为删除第 pi个数。
若 opti=3, 则接下来两个整数 li,ri，表示操作为翻转区间 [li,ri]。
若 opti=4，则接下来两个整数 li,ri，表示操作为查询区间 [li,ri]的和。
强制在线规则：
令当前操作之前的最后一次 4 操作的答案为 lastanslastans（如果之前没有 4 操作，则 lastans=0）。
则此次操作的 pi,xi或 li,ri均按位异或上 lastanslastans 即可得到真实的 pi,xi或 li,ri
输出格式
对于每个序号为 4 的查询操作，输出一行一个数表示区间的和。
输入输出样例
输入 #1 复制
10
0 1 0 1
1 1 1 2
2 4 1 2
3 1 2 0
4 4 2 1
5 3 5 7
6 4 5 6
4 1 7 1
8 3 4 6
9 4 4 1
输出 #1 复制
3
4
5
10
说明/提示
强制在线：以下针对 pi,xi,li,ri的限制均是按位异或 lastanslastans 后的限制。
对于 100% 的数据，1≤N≤2×1e5 ，-106<xi<106
假设基于的历史版本的序列长度为 len≥1，有：
若 opti=1，则 0≤pi≤len。
若 opti=2，则 1≤pi≤len。
若 opti=3，则 1≤li≤ri≤len。
若 opti=4，则 1≤li≤ri≤len。
假设基于的历史版本的序列长度为 0，有：
opti=1，pi=0。
思路：大体思路都一样。为了保证每次操作对历史版本不产生影响，在pushdown()和split()的操作时复制节点。因为每次merge()前都会split()，所以merge()时就不需要复制节点了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
#define pr pair<int,int>
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=200100;
const int mod=1e9+7;
struct Treap
{
int l,r;
int val,dat;
int si;
int rev;
ll sum;
}t[maxn*200];
int tot=0,root[maxn],n;
int newnode(int val)
{
t[++tot].val=val;
t[tot].sum=val;
t[tot].dat=rand();
t[tot].si=1;
t[tot].l=t[tot].r=t[tot].rev=0;
return tot;
}
int copy_node(int p)
{
int now=++tot;
t[now]=t[p];
return now;
}
void pushup(int p)
{
t[p].si=t[t[p].l].si+t[t[p].r].si+1;
t[p].sum=t[t[p].l].sum+t[t[p].r].sum+t[p].val;
}
void pushdown(int p)
{
if(!t[p].rev) return ;
if(t[p].l) t[p].l=copy_node(t[p].l),t[t[p].l].rev^=1;
if(t[p].r) t[p].r=copy_node(t[p].r),t[t[p].r].rev^=1;
swap(t[p].l,t[p].r);
t[p].rev=0;
}
int _merge(int x,int y)
{
if(!x||!y) return x|y;
if(t[x].dat<t[y].dat)
{
pushdown(x);
t[x].r=_merge(t[x].r,y);
pushup(x);
return x;
}
else
{
pushdown(y);
t[y].l=_merge(x,t[y].l);
pushup(y);
return y;
}
}
pr split(int x,int k)
{
if(!x) return pr(0,0);
pr y;
pushdown(x);
if(t[t[x].l].si<k)
{
int p=copy_node(x);
y=split(t[p].r,k-t[t[x].l].si-1);
t[p].r=y.first;
pushup(p);
y.first=p;
}
else
{
int p=copy_node(x);
y=split(t[p].l,k);
t[p].l=y.second;
pushup(p);
y.second=p;
}
return y;
}
void del(int &root,int k)
{
pr x=split(root,k-1),y=split(x.second,1);
root=_merge(x.first,y.second);
}
void _insert(int &root,int k,int val)
{
pr x=split(root,k);
int rt=newnode(val);
root=_merge(_merge(x.first,rt),x.second);
}
void _revserve(int &root,int l,int r)
{
pr x=split(root,l-1),y=split(x.second,r-l+1);
t[y.first].rev^=1;
root=_merge(_merge(x.first,y.first),y.second);
}
ll ask(int &root,int l,int r)
{
pr x=split(root,l-1),y=split(x.second,r-l+1);
ll ans=t[y.first].sum;
root=_merge(_merge(x.first,y.first),y.second);
return ans;
}
int main(void)
{
int n;
int vi,pos,x,y;
scanf("%d",&n);
ll last=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&vi,&pos);
root[i]=root[vi];
if(pos==1)
{
scanf("%d%d",&x,&y);
_insert(root[i],x^last,y^last);
}
else if(pos==2)
{
scanf("%d",&x);
del(root[i],x^last);
}
else if(pos==3)
{
scanf("%d%d",&x,&y);
_revserve(root[i],x^last,y^last);
}
else
{
scanf("%d%d",&x,&y);
last=ask(root[i],x^last,y^last);
printf("%lld\n",last);
}
}
return 0;
}
京公网安备 11010502036488号