[BZOJ 3224] [CODEVS 4543] 일반 밸 런 스 트 리 splay
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 5884 Solved: 2421 [Submit][Status][Discuss] Description
데이터 구조 (제목 참조) 를 써 서 몇 가지 수 를 유지 해 야 합 니 다. 그 중에서 다음 과 같은 동작 을 제공 해 야 합 니 다. 1. x 수 를 삽입 합 니 다.(전구 정 의 는 x 보다 작고 가장 큰 수) 6. x 의 후계 (후계 정 의 는 x 보다 크 고 가장 작은 수)
Input
첫 번 째 행위 n 은 조작의 개 수 를 나타 내 고 아래 n 줄 마다 두 개의 수 opt 와 x 가 있 으 며 opt 는 조작의 번호 (1 < = opt < = 6) 를 나타 낸다.
Output
조작 3, 4, 5, 6 줄 마다 하나의 수 를 출력 하여 대응 하 는 답 을 나타 낸다.
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
HINT
1. n 의 데이터 범위: n < = 100000
2. 각 수의 데이터 범위: [- 1e7, 1e7] Source
밸 런 스 트 리
제목: AS ABOVE; 제목: ALL KINDS OF STRUCTURES, AS FOLLOWS 1.0 번 노드 의 sz, find 의 특 판;
#include<iostream>
#include<stdio.h>
#include<queue>
#define N 20000005
#define inf 1000000000
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
int ch[N][2];
int sz[N];
int val[N];
int flag=0;
int n;
int fa[N];
int rt;
int pp;
int an;
int tot=0;
int num[N];
inline void pu(int x)
{
// if(flag==1) cout<<" "<<x<<" "<<ls<<" "<<rs<<endl;
sz[x]=0;
if(ls!=0) sz[x]+=sz[ls];
if(rs!=0) sz[x]+=sz[rs];
sz[x]+=num[x];
}
inline int is(int x)
{
return ch[fa[x]][1]==x;
}
inline void link(int y,int x,int d)
{
fa[x]=y; ch[y][d]=x;
}
inline void rotate(int x,int d)
{
int y=fa[x];
int z=fa[y];
link(y,ch[x][d],!d);
link(z,x,is(y));
link(x,y,d);
pu(y);
}
void zag(int x)
{
rotate(x,0);
}
void zig(int x)
{
rotate(x,1);
}
inline void splay(int x,int goal=0)
{
while(fa[x]!=goal)
{
int y=fa[x];
int z=fa[y];
if(z==goal)
{
rotate(x,!is(x));
break;
}
if(ch[z][0]==y)
{
if(ch[y][0]==x) zig(y),zig(x);
else zag(x),zig(x);
}
else
{
if(ch[y][1]==x) zag(y),zag(x);
else zig(x),zag(x);
}
}
if(goal==0) rt=x;
pu(x);
}
inline void newnode(int &x,int father,int v)
{
x=++tot;
fa[x]=father;
val[x]=v;
num[x]=1;
sz[x]=1;
}
inline int nex(int x)
{
if(!ch[x][1]) return 0;
x=ch[x][1];
while(ch[x][0]) x=ch[x][0];
return x;
}
inline int pre(int x)
{
int oo;
int tmp=rt;
if(val[tmp]<x) oo=val[tmp];
while(ch[tmp][val[tmp]<x])
{
tmp=ch[tmp][val[tmp]<x];
if(val[tmp]<x) oo=val[tmp];
}
return oo;
}
inline int hou(int x)
{
int oo;
int tmp=rt;
if(val[tmp]>x) oo=val[tmp];
while(ch[tmp][val[tmp]<=x])
{
tmp=ch[tmp][val[tmp]<=x];
if(val[tmp]>x) oo=val[tmp];
}
return oo;
}
inline int find (int x,int k)
{
// if(flag)
// {
// cout<<x<<" "<<sz[ls]<<" "<<k<<endl;pp++;
// if(pp==3) while(1);
// }
int tmp=sz[ls];
if(ls==0) tmp=0;
if(tmp+1<=k&&tmp+num[x]>=k) return x;
if(tmp+1>k) return find(ls,k);
return find(rs,k-num[x]-tmp);
}
inline int query_rank(int x)
{
int oo=0;
int tmp=rt;
while(ch[tmp][val[tmp]<x])
{
// <<" "<<val[ch[tmp][val[tmp]<x]]<<endl;
if(val[tmp]==x) break;
if(val[tmp]<x)
{
if(ch[tmp][0]) oo+=sz[ch[tmp][0]];
oo+=num[tmp];
}
tmp=ch[tmp][val[tmp]<x];// cout<<" "<<val[tmp]<<" "<<val[ch[tmp][val[tmp]<x]]<<endl;
}
// cout<<endl;
x=tmp;
an=tmp;
if(ch[tmp][0]) oo+=sz[ch[tmp][0]];
return oo+1;
}
inline void del(int x)
{
query_rank(x);
x=an;
splay(x);
if(num[x]>1)
{
num[x]--,pu(x);
return ;
}
else
{
int y=nex(x);
if(y!=0)
{
splay(y,x);
link(y,ch[x][0],0);
link(0,y,is(x));
rt=y;
}
else
{
if(ch[x][0])
{
link(0,ch[x][0],is(x));
rt=ch[x][0];
}
else rt=ch[0][0]=ch[0][1]=0;
}
pu(y);
}
}
inline void insert(int k)
{
int x=rt;
while(ch[x][val[x]<k])
{
if(val[x]==k)
{
num[x]++;
splay(x);
return;
}
x=ch[x][val[x]<k];
}
newnode(ch[x][val[x]<k],x,k);
splay(ch[x][val[x]<k]);
}
int main()
{
int aa,bb;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
// cout<<" "<<rt<<endl;
scanf("%d%d",&aa,&bb);
if(bb==-104772509) flag=1;
if(aa==1)
{
insert(bb);
}
else if(aa==2)
{
del(bb);
}
else if(aa==3)
{
printf("%d
",query_rank(bb));
}
else if(aa==4)
{
// for(int i=1;i<=10;i++)
// {
// cout<<i<<" "<<val[i]<<" "<<sz[i]<<" "<<ch[i][0]<<" "<<ch[i][1]<<endl;
// }cout<<endl<<endl<<endl;while(1);
printf("%d
",val[find(rt,bb)]);
}
else if(aa==5)
{
printf("%d
",pre(bb));
}
else if(aa==6)
{
printf("%d
",hou(bb));
}
// cout<<" "<<rt<<endl;
// for(int i=1;i<=10;i++)
// {
// cout<<i<<" "<<val[i]<<" "<<sz[i]<<" "<<ch[i][0]<<" "<<ch[i][1]<<endl;
// }cout<<endl<<endl<<endl;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.