Codeforces 675D Tree Construction Splay伸展树
2024-08-24 15:58:07
链接:https://codeforces.com/problemset/problem/675/D
题意:
给一个二叉搜索树,一开始为空,不断插入数字,每次插入之后,询问他的父亲节点的权值
题解:
由二叉搜索树的有序性质,
他的父亲节点一定是和他向上和向下最接近的两个中,最后插入的那一个
那么我们对于每一个数字标记其插入的时间,然后维护一棵平衡二叉树用于插值和查找用即可
主要是记录一下我的伸展树代码
据说指针比数组快,但是我这里不仅数组比指针快,甚至用vector和用数组的速度也是一样的
指针:
数组:
1.指针版
#include <bits/stdc++.h>
#define endl '\n'
#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 '\n'
#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;
}
最新文章
- tomcat6配置jndi连接数据库的方式
- linux下如何启动/停止/重启mysql:
- css应对已有class和特殊class的冲突
- linux防火墙启动、停止、查看
- ZYSocket 4.3.5 SOCKET框架组 发布[NEW]
- HDU1069_Monkey and Banana【LCS】
- python 内置函数 进制转换
- Codeforces Round #493 (Div. 2)
- Mudo C++网络库第六章学习笔记
- SpringData分页功能
- JVM优化系列之一(-Xss调整Stack Space的大小)
- JS报错修改日记(1):Uncaught ReferenceError: showQRcode is not defined
- 【Django】关于ORM的使用
- iOS.OpenSource.PopularProject
- Android JNI的使用方法
- [iOS] UICollectionView初始化滚动到中间的bug
- springboots Helloworld
- Centos安装Chrome浏览器失败解决办法
- Linux ${} 变量内容的提取和替换功能等
- 在Oracle中查看客户端连接的IP信息 .
热门文章
- python第三次周末大作业
- Redis之RDB与AOF 笔记
- Synchronous XMLHttpRequest on the main thread is deprecated because of its detrimental effects to the end user&#39;s experience. For more jquery-1.12.4.js:10208
- HDU 6345(子串查询 暴力)
- MySQLMySql免安装版安装配置
- 自学python 6.
- MySQL忘记root密码的解决办法
- Baidu 人脸识别FireFly 与PC连接调试
- ****** 四十 ******、软设笔记【网络基础】-Internet和Intranet基础
- C# WinForm开发系列 - Crystal Report水晶报表