链接:https://codeforces.com/problemset/problem/675/D
题意:
给一个二叉搜索树,一开始为空,不断插入数字,每次插入之后,询问他的父亲节点的权值
题解:
由二叉搜索树的有序性质,
他的父亲节点一定是和他向上和向下最接近的两个中,最后插入的那一个
那么我们对于每一个数字标记其插入的时间,然后维护一棵平衡二叉树用于插值和查找用即可
主要是记录一下我的伸展树代码
据说指针比数组快,但是我这里不仅数组比指针快,甚至用vector和用数组的速度也是一样的
指针:
数组:
1.指针版
#include <bits/stdc++.h>
#define endl '
'
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=1e6+10,maxm=2e6+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double PI=acos(-1.0);
//head
int casn,n,m,k;
int num[maxn];
class splaytree{
public:
struct splaynode{
splaynode *son[2],*pre;
ll val;
splaynode(int x=0,splaynode *fa=NULL){
pre=fa;
son[0]=son[1]=NULL;
val=x;
}
};
typedef struct splaynode* nodep;
int cnt;
nodep root;
vector<splaynode> node;
void rotate(nodep now,int d){
nodep fa=now->pre;
fa->son[!d]=now->son[d];
if(now->son[d]) now->son[d]->pre=fa;
now->pre=fa->pre;
if(fa->pre){
if(fa->pre->son[0]==fa) fa->pre->son[0]=now;
else fa->pre->son[1]=now;
}else root=now;
now->son[d]=fa;
fa->pre=now;
}
void splay(nodep now,nodep dst){
while(now->pre!=dst){
if(now->pre->pre==dst)rotate(now,now->pre->son[0]==now);
else{
nodep fa=now->pre;
int d=(fa->pre->son[0]==fa);
if(fa->son[d]==now){
rotate(now,!d);
rotate(now,d);
}else {
rotate(fa,d);
rotate(now,d);
}
}
}
if(!dst) root=now;
}
int insert(int val){
if(!root) {
node[cnt]=splaynode(val);
root=&node[cnt++];
return 0;
}
nodep now=root;
int flag=(now->val)<val;
while(now->son[flag]){
if((now->val)==val){
splay(now,NULL);
return 0;
}
now=now->son[flag];
flag=((now->val)<val);
}
node[cnt]=splaynode(val,now);
now->son[flag]=&node[cnt++];
splay(now->son[flag],NULL);
return 1;
}
int bound(int d){
nodep now=root->son[d];
if(!now) return INF;
while(now->son[d^1]) now=now->son[d^1];
return now->val;
}
splaytree(int n){
cnt=0;
node.resize(n+7);
root=NULL;
}
};
map<int,int> vis;
int main() {
IO;
cin>>n;
splaytree tree(n);
while(n--){
int a;
cin>>a;
vis[a]=maxn-n;
if(!tree.insert(a)) continue;
int mn=tree.bound(0);
int mx=tree.bound(1);
if(vis[mn]>vis[mx]) cout<<mn<<' ';
else cout<<mx<<' ';
}
return 0;
}
2.数组版
#include <bits/stdc++.h>
#define endl '
'
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=1e6+10,maxm=2e6+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
class splaytree{
#define nd node[now]
public:
struct splaynode{
int son[2],pre;
ll val;
splaynode(int x=0,int fa=0){
pre=fa;
son[0]=son[1]=0;
val=x;
}
};
int cnt;
int root;
vector<splaynode> node;
void rotate(int now,int d){
int fa=nd.pre;
node[fa].son[!d]=nd.son[d];
node[nd.son[d]].pre=fa;
if(node[fa].pre){
node[node[fa].pre].son[node[node[fa].pre].son[1]==fa]=now;
}else root=now;
nd.pre=node[fa].pre;
nd.son[d]=fa;
node[fa].pre=now;
}
void splay(int now,int dst){
while(nd.pre!=dst){
if(node[nd.pre].pre==dst)rotate(now,node[nd.pre].son[0]==now);
else{
int fa=nd.pre;
int d=(node[node[fa].pre].son[0]==fa);
if(node[fa].son[d]==now){
rotate(now,!d);
rotate(now,d);
}else {
rotate(fa,d);
rotate(now,d);
}
}
}
if(!dst) root=now;
}
int insert(int val){
if(!root) {
node[cnt]=splaynode(val);
root=cnt++;
return 0;
}
int now=root;
int flag=nd.val<val;
while(nd.son[flag]){
if(nd.val==val){
splay(now,0);
return 0;
}
now=nd.son[flag];
flag=nd.val<val;
}
node[cnt]=splaynode(val,now);
nd.son[flag]=cnt++;
splay(nd.son[flag],0);
return 1;
}
int bound(int d){
int now=node[root].son[d];
if(!now) return INF;
while(nd.son[d^1]) now=nd.son[d^1];
return nd.val;
}
splaytree(int n){
cnt=1,root=0;
node.resize(n+7);
}
};
map<int,int> vis;
int main() {
IO;
cin>>n;
splaytree tree(n);
while(n--){
int a;
cin>>a;
vis[a]=maxn-n;
if(!tree.insert(a)) continue;
int mn=tree.bound(0);
int mx=tree.bound(1);
if(vis[mn]>vis[mx]) cout<<mn<<' ';
else cout<<mx<<' ';
}
return 0;
}