type rec=record
lc,rc,v,rnd,size,w,fa:longint;
end; var
n,root,tot,ans,opt,x,i,po:longint;
tr:array[..] of rec; procedure rotl(po:longint);
var
y:longint;
begin
y:=tr[po].rc;
tr[po].rc:=tr[y].lc;
if tr[y].lc> then tr[tr[y].lc].fa:=po;
tr[y].fa:=tr[po].fa;
if tr[po].fa= then root:=y else
if po=tr[tr[po].fa].lc then
tr[tr[po].fa].lc:=y else tr[tr[po].fa].rc:=y;
tr[y].lc:=po;
tr[po].fa:=y;
tr[y].size:=tr[po].size;
tr[po].size:=tr[tr[po].lc].size+tr[tr[po].rc].size+tr[po].w;
end; procedure rotr(po:longint);
var
y:longint;
begin
y:=tr[po].lc;
tr[po].lc:=tr[y].rc;
if tr[y].rc> then tr[tr[y].rc].fa:=po;
tr[y].fa:=tr[po].fa;
if tr[po].fa= then root:=y else
if po=tr[tr[po].fa].lc then
tr[tr[po].fa].lc:=y else tr[tr[po].fa].rc:=y;
tr[y].rc:=po;
tr[po].fa:=y;
tr[y].size:=tr[po].size;
tr[po].size:=tr[tr[po].lc].size+tr[tr[po].rc].size+tr[po].w;
end; procedure ins(x,po:longint);
begin
inc(tr[po].size);
if x=tr[po].v then
begin
inc(tr[po].w);
exit;
end; if x<tr[po].v then
begin
if tr[po].lc= then
begin
inc(tot);
tr[tot].fa:=po;
tr[tot].v:=x;
tr[tot].size:=;
tr[tot].w:=;
tr[tot].rnd:=random()+;
tr[po].lc:=tot;
if tr[tot].rnd<tr[po].rnd then rotr(po);
end else
begin
ins(x,tr[po].lc);
if tr[tr[po].lc].rnd<tr[po].rnd then rotr(po);
end;
end; if x>tr[po].v then
begin
if tr[po].rc= then
begin
inc(tot);
tr[tot].fa:=po;
tr[tot].v:=x;
tr[tot].size:=;
tr[tot].w:=;
tr[tot].rnd:=random()+;
tr[po].rc:=tot;
if tr[tot].rnd<tr[po].rnd then rotl(po);
end else
begin
ins(x,tr[po].rc);
if tr[tr[po].rc].rnd<tr[po].rnd then rotl(po);
end;
end;
end; function find(x,po:longint):longint;
begin
dec(tr[po].size);
if x<tr[po].v then exit(find(x,tr[po].lc));
if x>tr[po].v then exit(find(x,tr[po].rc));
if x=tr[po].v then exit(po);
end; procedure del(po:longint);
begin
while(tr[po].lc>) or (tr[po].rc>) do
begin
if tr[po].lc= then
begin
rotl(po);
tr[tr[po].fa].size:=tr[tr[tr[po].fa].rc].size+tr[tr[po].lc].size+tr[tr[po].rc].size+tr[tr[po].fa].w;
continue;
end; if tr[po].rc= then
begin
rotr(po);
tr[tr[po].fa].size:=tr[tr[tr[po].fa].lc].size+tr[tr[po].lc].size+tr[tr[po].rc].size+tr[tr[po].fa].w;
continue;
end; if tr[tr[po].lc].rnd>tr[tr[po].rc].rnd then
begin
rotl(po);
tr[tr[po].fa].size:=tr[tr[tr[po].fa].rc].size+tr[tr[po].lc].size+tr[tr[po].rc].size+tr[tr[po].fa].w;
end
else
begin
rotr(po);
tr[tr[po].fa].size:=tr[tr[tr[po].fa].lc].size+tr[tr[po].lc].size+tr[tr[po].rc].size+tr[tr[po].fa].w;
end;
end; if tr[tr[po].fa].lc=po then
begin
tr[tr[po].fa].lc:=;
tr[tr[po].fa].size:=tr[tr[tr[po].fa].rc].size+tr[tr[po].fa].w;
end
if tr[tr[po].fa].rc=po then
begin
tr[tr[po].fa].rc:=;
tr[tr[po].fa].size:=tr[tr[tr[po].fa].lc].size+tr[tr[po].fa].w;
end; tr[po].size:=;tr[po].w:=; end; procedure num(x,po:longint);
begin
if x<=tr[tr[po].lc].size then
begin
num(x,tr[po].lc);
exit;
end; if x>tr[tr[po].lc].size+tr[po].w then
begin
num(x-tr[tr[po].lc].size-tr[po].w,tr[po].rc);
exit;
end; writeln(tr[po].v);
end; procedure rank(x,po:longint);
begin
if x<tr[po].v then
begin
rank(x,tr[po].lc);
exit;
end; if x>tr[po].v then
begin
ans:=ans+tr[tr[po].lc].size+tr[po].w;
rank(x,tr[po].rc);
exit;
end; ans:=ans+tr[tr[po].lc].size+;
end; procedure pre(x,po:longint);
begin
if po= then exit;
if (tr[po].v<x) then
begin
ans:=tr[po].v;
pre(x,tr[po].rc);
end else pre(x,tr[po].lc);
end; procedure suc(x,po:longint);
begin
if po= then exit;
if (tr[po].v>x) then
begin
ans:=tr[po].v;suc(x,tr[po].lc);
end else suc(x,tr[po].rc);
end; begin randomize;
read(n); for i:= to n do
begin
read(opt,x);
if opt= then
begin
if tr[root].w= then
begin
inc(tot);
tr[tot].v:=x;tr[tot].size:=;tr[tot].w:=;
tr[tot].rnd:=random()+;
root:=tot;
end else ins(x,root);
end;
if opt= then begin po:=find(x,root);if tr[po].w> then begin dec(tr[po].w);continue;end;del(po); end;
if opt= then begin ans:=;rank(x,root); writeln(ans);end;
if opt= then num(x,root);
if opt= then begin pre(x,root); writeln(ans); end;
if opt= then begin suc(x,root); writeln(ans); end;
end; end.
------------------------------------------------------
非旋treap
CODECHEF LTIME16 CHEFC
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std; int a[],T,n,root,q; struct treenode{
int lc,rc,lv,rv,v,ans,size;
}tr[]; void update(int po){
if (!tr[po].lc) tr[po].lv=tr[po].v;else tr[po].lv=tr[tr[po].lc].lv;
if (!tr[po].rc) tr[po].rv=tr[po].v;else tr[po].rv=tr[tr[po].rc].rv; tr[po].ans=tr[tr[po].lc].ans+tr[tr[po].rc].ans;
if (tr[po].lc) tr[po].ans+=tr[po].v!=tr[tr[po].lc].rv;
if (tr[po].rc) tr[po].ans+=tr[po].v!=tr[tr[po].rc].lv; tr[po].size=tr[tr[po].lc].size+tr[tr[po].rc].size+;
} int build(int l,int r){
int mid=(l+r)>>;
tr[mid].v=a[mid];tr[mid].size=tr[mid].ans=;tr[mid].lc=tr[mid].rc=;
if (l==r){
tr[mid].lv=tr[mid].rv=tr[mid].v;tr[mid].size=;
return(mid);
} if (l!=mid) tr[mid].lc=build(l,mid-);
if (r!=mid) tr[mid].rc=build(mid+,r);
update(mid);
return(mid);
} void split(int po,int &root1,int &root2,int k){
if (tr[tr[po].lc].size==k){
root1=tr[po].lc;root2=po;
tr[po].lc=;
update(po);
return;
}
if (tr[tr[po].lc].size==k-){
root1=po;root2=tr[po].rc;
tr[po].rc=;
update(po);
return;
} if (k<=tr[tr[po].lc].size){
split(tr[po].lc,root1,root2,k);
tr[po].lc=root2;
update(po);
root2=po;
}else{
split(tr[po].rc,root1,root2,k-tr[tr[po].lc].size-);
tr[po].rc=root1;
update(po);
root1=po;
}
} int merge(int po1,int po2){
if (po1==||po2==) return(po1|po2); if ((LL)rand()*tr[po1].size>(LL)rand()*tr[po2].size){
tr[po1].rc=merge(tr[po1].rc,po2);
update(po1);
return(po1);
}else{
tr[po2].lc=merge(po1,tr[po2].lc);
update(po2);
return(po2);
}
} void dfs_show(int po){
if (tr[po].lc) dfs_show(tr[po].lc);
printf("%d ",tr[po].v);
if (tr[po].rc) dfs_show(tr[po].rc);
} int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
root=build(,n); scanf("%d",&q);
for (int i=;i<=q;i++){
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
int root1,root2,root3;
split(root,root1,root2,l-); split(root2,root2,root3,r-l+); if (opt==){
root1=merge(root1,root3);
root=merge(root2,root1);
}else{
printf("%d\n",tr[root2].ans+);
root2=merge(root2,root3);
root=merge(root1,root2);
}
}
}
}