解题报告
线段树套平衡树裸题，瞎XX打，轻松1A
别问我为啥BZOJ上RE了一次，srand有毒
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
int sum(),f();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar())
if(ch=='-')
f=-;
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum*f;
}
#define get_size(x) (x?x->size:0)
struct node{
node *lch,*rch;
int size,key,fix;
node(int x=):lch(NULL),rch(NULL),size(),key(x),fix(rand()){}
inline void pushup(){
this->size=get_size(this->lch)+get_size(this->rch)+;
}
}*tr[];
inline void left_rotate(node *&x){
node *tmp(x->rch);
x->rch=tmp->lch;
tmp->lch=x;
x->pushup();
tmp->pushup();
x=tmp;
}
inline void right_rotate(node *&x){
node *tmp(x->lch);
x->lch=tmp->rch;
tmp->rch=x;
x->pushup();
tmp->pushup();
x=tmp;
}
inline void insert(node *&x,int v){
if(!x){
x=new node(v);
return;
}
if(v<=x->key){
insert(x->lch,v);
x->pushup();
if(x->lch->fix<x->fix)
right_rotate(x);
}
else{
insert(x->rch,v);
x->pushup();
if(x->rch->fix<x->fix)
left_rotate(x);
}
}
inline void del(node *&x,int v){
if(x->key==v){
if(x->lch&&x->rch){
if(x->lch->fix<x->rch->fix){
right_rotate(x);
del(x->rch,v);
}
else{
left_rotate(x);
del(x->lch,v);
}
}
else{
node *tmp(NULL);
if(x->lch)
tmp=x->lch;
else
tmp=x->rch;
delete x;
x=tmp;
}
}
else{
if(v<=x->key)
del(x->lch,v);
else
del(x->rch,v);
}
if(x)
x->pushup();
}
inline int Rank(node *now,int x){
int ret();
while(now){
if(x<=now->key)
now=now->lch;
else
ret+=get_size(now->lch)+,now=now->rch;
}
return ret;
}
inline int kth(node *now,int k){
while(now){
if(get_size(now->lch)+==k)
return now->key;
if(get_size(now->lch)+>=k)
now=now->lch;
else
k-=get_size(now->lch)+,now=now->rch;
}
}
int n,m;
int a[];
inline void build(int l,int r,int rt){
for(int i=l;i<=r;++i)
insert(tr[rt],a[i]);
if(l==r)return;
int mid((l+r)>>);
build(l,mid,rt<<);
build(mid+,r,rt<<|);
}
inline int Rank(int ll,int rr,int k,int l,int r,int i){
if(ll<=l&&r<=rr)
return Rank(tr[i],k);
int mid((l+r)>>),ret();
if(ll<=mid)
ret+=Rank(ll,rr,k,l,mid,i<<);
if(mid<rr)
ret+=Rank(ll,rr,k,mid+,r,i<<|);
return ret;
}
inline int kth(int l,int r,int k){
int ll(),rr(1e8);
while(ll<=rr){
int mid((ll+rr)>>);
int jud(Rank(l,r,mid,,n,)+);
if(jud<=k)
ll=mid+;
else
rr=mid-;
}
return rr;
}
inline void update(int pos,int w,int l,int r,int i){
del(tr[i],a[pos]);
insert(tr[i],w);
if(l==r)return;
int mid((l+r)>>);
if(pos<=mid)
update(pos,w,l,mid,i<<);
else
update(pos,w,mid+,r,i<<|);
}
inline int gg(){
// freopen("psh.in","r",stdin);
// freopen("psh.out","w",stdout);
// srand(time(NULL));
n=read(),m=read();
for(int i=;i<=n;++i)
a[i]=read();
build(,n,);
while(m--){
int op(read());
if(op==){
int x(read()),y(read()),z(read());
printf("%d\n",Rank(x,y,z,,n,)+);
}
if(op==){
int x(read()),y(read()),z(read());
printf("%d\n",kth(x,y,z));
}
if(op==){
int x(read()),y(read());
update(x,y,,n,);
a[x]=y;
}
if(op==){
int x(read()),y(read()),z(read());
printf("%d\n",kth(x,y,Rank(x,y,z,,n,)));
}
if(op==){
int x(read()),y(read()),z(read());
printf("%d\n",kth(x,y,Rank(x,y,z+,,n,)+));
}
}
return ;
}
int K(gg());
int main(){;}