平衡树的裸题，操作都相当简单
写了一个FHQ，但是奈何常数太大，实在过不去
最后写了一个Treap开O2水过
TREAP代码
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
struct node{
int sz,key,ran,l,r,re;
}tr[500100<<2];
int maxsize=0,ans=0,root1=0,root2=0,fir[500100],back[500100],min3=0x3f3f3f3f;
void update(int k){
tr[k].sz=tr[tr[k].l].sz+tr[tr[k].r].sz+tr[k].re;
}
void roratel(int &o){
int k=tr[o].r;
tr[o].r=tr[k].l;
tr[k].l=o;
tr[k].sz=tr[o].sz;
update(o);
o=k;
}
void rorater(int &k){
int o=tr[k].l;
tr[k].l=tr[o].r;
tr[o].r=k;
tr[o].sz=tr[k].sz;
update(k);
k=o;
}
void insert(int &k,int x){
if(k==0){
++maxsize;
k=maxsize;
tr[k].sz=1;
tr[k].re=1;
tr[k].key=x;
tr[k].ran=rand();
return;
}
tr[k].sz++;
if(tr[k].key==x){
tr[k].re++;
}
else{
if(x>tr[k].key){
insert(tr[k].r,x);
if(tr[tr[k].r].ran<tr[k].ran)
roratel(k);}
else{
insert(tr[k].l,x);
if(tr[tr[k].l].ran<tr[k].ran)
rorater(k);}
}
}
void del(int &k,int x){
if(k==0)
return;
if(tr[k].key==x){
if(tr[k].re>1){
tr[k].re--;
tr[k].sz--;
return;
}
if(tr[k].l*tr[k].r==0){
k=tr[k].l+tr[k].r;
return;
}
else{
if(tr[tr[k].l].ran<tr[tr[k].r].ran){
rorater(k);
del(k,x);
}
else{
roratel(k);
del(k,x);
}
}
}
else{
if(x>tr[k].key){
tr[k].sz--;
del(tr[k].r,x);
}
else{
tr[k].sz--;
del(tr[k].l,x);
}
}
}
int rank1(int k,int x){
if(k==0)
return 0;
if(tr[k].key==x){
return tr[tr[k].l].sz+1;
}
else{
if(x>tr[k].key)
return rank1(tr[k].r,x)+tr[k].re+tr[tr[k].l].sz;
else
return rank1(tr[k].l,x);
}
}
int rank2(int k,int x){
if(k==0)
return 0;
if(x<=tr[tr[k].l].sz){
return rank2(tr[k].l,x);
}
else if(x>(tr[tr[k].l].sz+tr[k].re))
return rank2(tr[k].r,x-tr[tr[k].l].sz-tr[k].re);
else
return tr[k].key;
}
void pre(int k,int x){
if(k==0)
return;
if(tr[k].key<x){
ans=k;
pre(tr[k].r,x);
}
else if(tr[k].key==x&&tr[k].re>1){
ans=k;
return;
}
else
pre(tr[k].l,x);
}
void beh(int k,int x){
if(k==0)
return;
if(tr[k].key>x){
ans=k;
beh(tr[k].l,x);
}
else if(tr[k].key==x&&tr[k].re>1){
ans=k;
return;
}
else
beh(tr[k].r,x);
}
//root1 - 2 root2 - 3
int main(){
// freopen("9.in","r",stdin);
// freopen("test.out","w",stdout);
srand(19260817);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&back[i]),fir[i]=back[i];
for(int i=1;i<=n-1;i++){
insert(root1,abs(back[i]-back[i+1]));
insert(root2,back[i]);
}
// printf("%d %d
",root1,root2);
insert(root2,back[n]);
insert(root2,0x3f3f3f3f);
insert(root2,-0x3f3f3f3f);
for(int i=1;i<=n;i++){
// printf("pre=%d beh=%d val=%d
",pre(back[i],root2),beh(back[i],root2),back[i]);
beh(root2,back[i]);
int behans=tr[ans].key;
pre(root2,back[i]);
int preans=tr[ans].key;
min3=min(min3,min(abs(behans-back[i]),abs(preans-back[i])));
}
char opt[20];
for(int i=1;i<=m;i++){
scanf("%s",opt);
if(opt[0]=='I'){
int poi,addx;
scanf("%d %d",&poi,&addx);
insert(root2,addx);
beh(root2,addx);
int behans=tr[ans].key;
pre(root2,addx);
int preans=tr[ans].key;
min3=min(min3,min(abs(behans-addx),abs(preans-addx)));
del(root1,abs(fir[poi+1]-back[poi]));
insert(root1,abs(fir[poi+1]-addx));
insert(root1,abs(addx-back[poi]));
back[poi]=addx;
}
else{
if(opt[4]=='G'){
printf("%d
",rank2(root1,1));
}
else
printf("%d
",min3);
}
}
return 0;
}
FHQ-TREAP代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct Node{
int sz,w,ran,lson,rson;
}FHQ[501000<<2];
int Nodecnt,back[501000],root1,root2,min3=0x3f3f3f3f,fir[501000];
int newNode(int w){
++Nodecnt;
FHQ[Nodecnt].sz=1;
FHQ[Nodecnt].w=w;
FHQ[Nodecnt].ran=rand();
FHQ[Nodecnt].lson=FHQ[Nodecnt].rson=0;
return Nodecnt;
}
void pushup(int o){
FHQ[o].sz=FHQ[FHQ[o].lson].sz+FHQ[FHQ[o].rson].sz+1;
}
void split_val(int now,int k,int &x,int &y){
if(!now){
x=y=0;
return;
}
if(FHQ[now].w<=k){
x=now;
split_val(FHQ[now].rson,k,FHQ[now].rson,y);
}
else{
y=now;
split_val(FHQ[now].lson,k,x,FHQ[now].lson);
}
pushup(now);
}
int merge(int x,int y){//X.W < Y.W
if(!x||!y)
return x+y;
pushup(x);
pushup(y);
if(FHQ[x].ran<FHQ[y].ran){
FHQ[x].rson=merge(FHQ[x].rson,y);
pushup(x);
return x;
}
else{
FHQ[y].lson=merge(x,FHQ[y].lson);
pushup(y);
return y;
}
}
void insert(int x,int &root){
int mergeroot=newNode(x),a,b;
split_val(root,x,a,b);
root=merge(merge(a,mergeroot),b);
}
void erase(int x,int &root){
int a,b,c,d;
split_val(root,x,a,b);
split_val(a,x-1,c,d);
root=merge(merge(c,merge(FHQ[d].lson,FHQ[d].rson)),b);
}
int findkth(int now,int kth){
if(now==0)
return 0;
if(kth==FHQ[FHQ[now].lson].sz+1)
return now;
if(kth<=FHQ[FHQ[now].lson].sz)
return findkth(FHQ[now].lson,kth);
else
return findkth(FHQ[now].rson,kth-FHQ[FHQ[now].lson].sz-1);
}
int findrank(int &now,int wx){
int a,b;
split_val(now,wx-1,a,b);
int ans = FHQ[a].sz+1;
now=merge(a,b);
return ans;
}
int pre(int x,int &root){
int a,b;
split_val(root,x,a,b);
int ans=FHQ[findkth(a,FHQ[a].sz-1)].w;
root=merge(a,b);
return ans;
}
int beh(int x,int &root){
int a,b;
split_val(root,x-1,a,b);
int ans=FHQ[findkth(b,2)].w;
root=merge(a,b);
return ans;
}
//root1 - 2 root2 - 3
int main(){
// freopen("9.in","r",stdin);
// freopen("test.out","w",stdout);
srand(19260817);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&back[i]),fir[i]=back[i];
for(int i=1;i<=n-1;i++){
insert(abs(back[i]-back[i+1]),root1);
insert(back[i],root2);
}
// printf("%d %d
",root1,root2);
insert(back[n],root2);
insert(0x3f3f3f3f,root2);
insert(-0x3f3f3f3f,root2);
for(int i=1;i<=n;i++){
// printf("pre=%d beh=%d val=%d
",pre(back[i],root2),beh(back[i],root2),back[i]);
min3=min(min3,min(abs(beh(back[i],root2)-back[i]),abs(pre(back[i],root2)-back[i])));
}
char opt[20];
for(int i=1;i<=m;i++){
scanf("%s",opt);
if(opt[0]=='I'){
int poi,addx;
scanf("%d %d",&poi,&addx);
insert(addx,root2);
min3=min(min3,min(abs(beh(addx,root2)-addx),abs(pre(addx,root2)-addx)));
erase(abs(fir[poi+1]-back[poi]),root1);
insert(abs(fir[poi+1]-addx),root1);
insert(abs(addx-back[poi]),root1);
back[poi]=addx;
}
else{
if(opt[4]=='G')
printf("%d
",FHQ[findkth(root1,1)].w);
else
printf("%d
",min3);
}
}
return 0;
}