F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 3224 >> 其它OJAC,这里WA
ycyzcf @ 2018-01-12 23:58:02
[ Quote ] [ Edit ] [ Delete ] 1#
有没有人帮忙看下代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define Lson(k) (treap[k].Lson)
#define Rson(k) (treap[k].Rson)
const int MAXN = 1e5;
using namespace std;
inline int Read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch == '-')f=-1;ch=getchar();}
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct node{
int Lson,Rson;
int val,size,rnd;//rnd随机数出的优先级
int w;//题目所要求的重复的数值出现的次数
}treap[MAXN+10];
int root,e,ans,N;
inline void update(int k){
treap[k].size=treap[Lson(k)].size+treap[Rson(k)].size+treap[k].w;
}
inline void Zig(int &k){
//cout<<k<<endl;
register int t = treap[k].Rson;
treap[k].Rson=treap[t].Lson,treap[t].Lson=k;
treap[t].size=treap[k].size;
update(k);k=t;
}
inline void Zag(int &k){
register int t = treap[k].Lson;
treap[k].Lson=treap[t].Rson,treap[t].Rson=k;
treap[t].size=treap[k].size;
update(k);k=t;
}
inline void insert(int &k,int x){
if(!k){
k=++e;
treap[k].val=x;
treap[k].size=treap[k].w=1;
treap[k].rnd=rand();
//cout<<k<<" "<<treap[k].val<<endl;
return ;
}
treap[k].size++;
if(x<treap[k].val){
insert(Lson(k),x);
if(treap[Lson(k)].rnd<treap[k].rnd)Zag(k);
return ;
}
if(x>treap[k].val){
insert(Rson(k),x);
//cout<<k<<" "<<treap[k].val<<endl;
if(treap[Rson(k)].rnd<treap[k].rnd)Zig(k);
return ;
}
treap[k].w++;
}
inline void del(int &k,int x){
if(!k)return ;
if(x<treap[k].val){
treap[k].size--;
del(Lson(k),x);
return ;
}
if(x>treap[k].val){
treap[k].size--;
del(Rson(k),x);
return ;
}
if(treap[k].w>1)treap[k].w--;
else{
if(!Lson(k)||!Rson(k)){
k=Lson(k)+Rson(k);
return ;
}
if(treap[Lson(k)].rnd>treap[Rson(k)].rnd)Zag(k),del(k,x);
else Zig(k),del(k,x);
}
}
inline int Rank(int k,int x){
if(!k)return 0;
if(treap[k].val == x)return treap[Lson(k)].size+1;
if(treap[k].val>x) return Rank(Lson(k),x);
if(treap[k].val<x) return treap[Lson(k)].size+treap[k].w+Rank(Rson(k),x);
}
inline int searRank(int k,int x){
if(!k)return 0;
if(treap[Lson(k)].size>=x)return searRank(Lson(k),x);
else if(treap[Lson(k)].size+treap[k].w<x)return searRank(Rson(k),x-treap[Lson(k)].size-treap[k].w);
else return treap[k].val;
}
inline void querypre(int k,int x){
if(!k)return ;
if(treap[k].val<x){
ans=treap[k].val;
querypre(Rson(k),x);
return ;
}else {
querypre(Lson(k),x);
return ;
}
}
inline void querypost(int k,int x){
if(!k)return ;
if(treap[k].val>x){
ans=treap[k].val;
querypost(Lson(k),x);
return ;
}else {
querypost(Rson(k),x);
return ;
}
}
inline void out(int k){
if(Lson(k))out(Lson(k));
printf("%d\n",treap[k].val);
if(Rson(k))out(Rson(k));
}
int main(){
N=Read();
register int opt,x;
while(N--){
//scanf("%d%d",&opt,&x);
opt=Read();
//cout<<root<<endl;
if(opt == 0)out(root);
x=Read();
if(opt == 1)insert(root,x);
if(opt == 2)del(root,x);
if(opt == 3)printf("%d\n",Rank(root,x));
if(opt == 4)printf("%d\n",searRank(root,x));
if(opt == 5){
ans = 0;
querypre(root,x);
printf("%d\n",ans);
}
if(opt == 6){
ans = 0;
querypost(root,x);
printf("%d\n",ans);
}
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back