BZOJ1861：[ZJOI2006]书架
2024-08-29 23:45:02
浅谈\(splay\)：https://www.cnblogs.com/AKMer/p/9979592.html
浅谈\(fhq\)_\(treap\)：https://www.cnblogs.com/AKMer/p/9981274.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1861
一道非常好的平衡树题。我们令树上每个点记录两个值，一个是它所记录的书的编号\(val[i]\)，还有一个键值\(key[i]\)满足所有结点按键值从小到大排好序后结点上的书的顺序依次也刚好是书架上书的位置，我们就用平衡树维护这个键值，然后用一个数组\(id[i]\)表示编号为\(i\)的书是被平衡树上第几个点记录的。由于键值之间的大小关系满足书架上的下上关系，所以我们很容易找到第几大的书和某一本书前面有多少本书。
操作\(1\)：
对于\(splay\)
我们删掉记录\(s\)号书的信息的点，然后把它的键值等于整个平衡树里键值最小值\(-1\)，再插入回去。
对于\(fhq\)_\(treap\)
把整棵树分成\(part1\)，\(s\)，\(part2\)三个部分，再按照\(s\)，\(part1\)，\(part2\)的顺序合并起来。
操作\(2\)
与操作\(1\)同理。
操作\(3\)
如果\(t\)等于\(0\)，直接什么也不做。
对于\(splay\)
若\(t\)等于\(-1\)，交换\(id[s]\)与\(id[s]\)的前驱结点\(node\)记录的书的编号\(x\)，然后\(swap(id[s],id[x])\)
若\(t\)等于\(1\)，交换\(id[s]\)与\(id[s]\)的后继结点\(node\)记录的书的编号\(x\)，然后\(swap(id[s],id[x])\)
对于\(fhq\)_\(treap\)
若\(t\)等于\(-1\)，将树分成\(part1\)，\(node\)，\(id[s]\)，\(part2\)四个部分，先\(swap(key[node],key[id[s]])\)，然后按照\(part1\)，\(id[s]\)，\(node\)，\(part2\)的顺序合并。
若\(t\)等于\(1\)，将树分成\(part1\)，\(id[s]\)，\(node\)，\(part2\)四个部分，先\(swap(key[node],key[id[s]])\)，然后按照\(part1\)，\(node\)，\(id[s]\)，\(part2\)的顺序合并。\(node\)的含义见对于splay
因为有键值，所以操作\(4\)和操作\(5\)都是十分简单的，这里就不多赘述了。
时间复杂度：\(O((n+m)logn)\)
空间复杂度：\(O(n)\)
\(splay\)版代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=8e4+5;
int n,m,s;
char ch[25];
int id[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct Splay {
int tot,root,mn,mx;
int fa[maxn],son[maxn][2];
int val[maxn],siz[maxn],key[maxn];
void update(int p) {
siz[p]=siz[son[p][0]]+1+siz[son[p][1]];
}
void build(int l,int r,int lst) {
if(r<l)return;
if(l==r) {
fa[l]=lst,son[lst][l>lst]=l;
siz[l]=1,key[l]=l;return;
}
int mid=(l+r)>>1;
fa[mid]=lst,son[lst][mid>lst]=mid;
build(l,mid-1,mid),build(mid+1,r,mid);
key[mid]=mid;update(mid);
}
int find(int v) {
int u=root;
while(key[u]!=v) {
if(key[u]>v) {if(son[u][0])u=son[u][0];else break;}
if(key[u]<v) {if(son[u][1])u=son[u][1];else break;}
}
return u;
}
void prepare() {
tot=n;build(1,n,0);root=(1+n)>>1;
}
int t(int u) {
return son[fa[u]][1]==u;
}
void rotate(int u) {
int ret=t(u),f=fa[u],s=son[u][ret^1];
son[f][ret]=s;if(s)fa[s]=f;son[u][ret^1]=f;
fa[u]=fa[f];if(fa[f])son[fa[f]][t(f)]=u;
fa[f]=u;update(f);update(u);
}
void splay(int u) {
while(fa[u]) {
if(fa[fa[u]]) {
if(t(fa[u])==t(u))rotate(fa[u]);
else rotate(u);
}
rotate(u);
}
root=u;
}
void del() {
int u=id[s];splay(u);
if(!son[u][0]) {root=son[u][1];fa[root]=0;return;}
if(!son[u][1]) {root=son[u][0];fa[root]=0;return;}
int node=son[u][0];while(son[node][1])node=son[node][1];
fa[son[u][0]]=0,splay(node),son[node][1]=son[u][1];
fa[son[u][1]]=node,root=node,update(node);
}
void ins(int type) {
int node=id[s];
son[node][0]=son[node][1]=0;
if(type)key[node]=++mx;
else key[node]=--mn;
int u=find(key[node]);
fa[node]=u;son[u][key[node]>key[u]]=node;
splay(node);
}
void change(int type) {
int u=id[s],node;
splay(u);
if(type==-1) {
node=son[u][0];
while(son[node][1])node=son[node][1];
}
else {
node=son[u][1];
while(son[node][0])node=son[node][0];
}
if(node)
swap(val[node],val[u]),swap(id[val[node]],id[val[u]]);
}
void Ask() {
int u=id[s];splay(u);
printf("%d\n",siz[son[u][0]]);
}
void Query() {
int u=root;
while(s) {
if(siz[son[u][0]]>=s)u=son[u][0];
if(siz[son[u][0]]+1==s)break;
if(siz[son[u][0]]+1<s)s-=siz[son[u][0]]+1,u=son[u][1];
}
printf("%d\n",val[u]);
}
}T;
int main() {
n=read(),m=read();
for(int i=1;i<=n;i++)
T.val[i]=read(),id[T.val[i]]=i;
T.prepare();T.mn=1,T.mx=n;
for(int i=1;i<=m;i++) {
scanf("%s",ch+1);s=read();
if(ch[1]=='T')T.del(),T.ins(0);
if(ch[1]=='B')T.del(),T.ins(1);
if(ch[1]=='I') {
int t=read();
if(!t)continue;
T.change(t);
}
if(ch[1]=='A')T.Ask();
if(ch[1]=='Q')T.Query();
}
return 0;
}
\(fhq\)_\(treap\)版代码如下：
#include <ctime>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxn=8e4+5;
int n,m,s;
char ch[25];
int id[maxn];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct fhq_treap {
int tot,root,mn,mx;
int fix[maxn],son[maxn][2];
int val[maxn],key[maxn],siz[maxn];
void update(int p) {
siz[p]=siz[son[p][0]]+1+siz[son[p][1]];
}
void build(int l,int r,int lst) {
if(r<l)return;
if(l==r) {
fix[l]=rand(),son[lst][l>lst]=l;
siz[l]=1,key[l]=l;return;
}
int mid=(l+r)>>1;
fix[mid]=rand(),son[lst][mid>lst]=mid;
build(l,mid-1,mid);build(mid+1,r,mid);
key[mid]=mid;update(mid);
}
void prepare() {
tot=n;build(1,n,0);root=(1+n)>>1;
}
int get_rk(int u) {
if(!u)return 0;int ans=0;
if(key[u]>key[id[s]])ans=get_rk(son[u][0]);
else if(key[u]==key[id[s]])return siz[son[u][0]];
else ans=siz[son[u][0]]+1+get_rk(son[u][1]);
return ans;
}
pii split(int u,int rk) {
if(!rk)return make_pair(0,u);
if(rk==siz[u])return make_pair(u,0);
if(siz[son[u][0]]>=rk) {
pii tmp=split(son[u][0],rk);
son[u][0]=tmp.second;update(u);
return make_pair(tmp.first,u);
}
else {
pii tmp=split(son[u][1],rk-siz[son[u][0]]-1);
son[u][1]=tmp.first;update(u);
return make_pair(u,tmp.second);
}
}
int merge(int a,int b) {
if(!a||!b)return a+b;
if(fix[a]>fix[b])return son[a][1]=merge(son[a][1],b),update(a),a;
else return son[b][0]=merge(a,son[b][0]),update(b),b;
}
void replace(int type) {
int rk=get_rk(root)+1;
pii tmp1=split(root,rk);
pii tmp2=split(tmp1.first,rk-1);
if(!type) {
key[tmp2.second]=--mn;
root=merge(merge(tmp2.second,tmp2.first),tmp1.second);
}
else {
key[tmp2.second]=++mx;
root=merge(merge(tmp2.first,tmp1.second),tmp2.second);
}
}
void change(int t) {
int rk=get_rk(root)+1;
if(t==-1) {
if(rk==1)return;
pii tmp1=split(root,rk);
pii tmp2=split(tmp1.first,rk-1);
pii tmp3=split(tmp2.first,rk-2);
int u=tmp2.second,v=tmp3.second;
swap(key[u],key[v]);
root=merge(merge(tmp3.first,u),merge(v,tmp1.second));
}
else {
if(rk==n)return;
pii tmp1=split(root,rk+1);
pii tmp2=split(tmp1.first,rk);
pii tmp3=split(tmp2.first,rk-1);
int u=tmp2.second,v=tmp3.second;
swap(key[u],key[v]);
root=merge(merge(tmp3.first,u),merge(v,tmp1.second));
}
}
void Ask() {
int rk=get_rk(root);
printf("%d\n",rk);
}
void Query() {
int u=root;
while(s) {
if(siz[son[u][0]]>=s)u=son[u][0];
if(siz[son[u][0]]+1==s)break;
if(siz[son[u][0]]+1<s)s-=siz[son[u][0]]+1,u=son[u][1];
}
printf("%d\n",val[u]);
}
}T;
int main() {
srand(time(0));
n=read(),m=read();
for(int i=1;i<=n;i++)
T.val[i]=read(),id[T.val[i]]=i;
T.prepare(),T.mn=1,T.mx=n;
for(int i=1;i<=m;i++) {
scanf("%s",ch+1),s=read();
if(ch[1]=='T')T.replace(0);
if(ch[1]=='B')T.replace(1);
if(ch[1]=='I') {
int t=read();
if(!t)continue;
T.change(t);
}
if(ch[1]=='A')T.Ask();
if(ch[1]=='Q')T.Query();
}
return 0;
}
最新文章
- MySQL函数不能创建的解决方法
- Kali Linux (XFce版本)安装后的一些设置
- arduino 红外遥控器控制LED灯
- Log4net中的RollingFileAppender z
- 【锋利的JQuery-学习笔记】添加提示图片
- Oracle 数据库表空间碎片查询和整理
- vertor容器
- 在ASP.NET Core中使用Apworks快速开发数据服务
- CentOS 6.8下二级域名及目录的绑定
- jQuery 瀑布流插件: Wookmark
- 洛谷P5284 [十二省联考2019]字符串问题 [后缀树]
- PLSQL Developer 远程连接Oracle数据库
- 重新定义Pytorch中的TensorDataset，可实现transforms
- 转://oracle Wallet在expdp/impdp中使用场景
- $Django 路飞之课程下的分类,用户登陆成功前端存cookie,
- thread run 和 start 的区别
- 《RECURRENT BATCH NORMALIZATION》
- SQLServer 删除表中的重复数据
- PHP通过soap调用c#的WebService
- 混淆和加密.NET开发工具
热门文章
- Visual Studio Code v1.17
- python 基础 7.6 sys 模块
- 4276: [ONTAK2015]Bajtman i Okrągły Robin
- EasyPlayerPro Windows播放器实时流进行本地缓冲区即时回放功能实现
- 九度OJ 1081：递推数列 （递归，二分法）
- 九度OJ 1045：百鸡问题 （基础题）
- [Python]Pip换源以及设置代理
- git学习------>"Agent admitted failure to sign using the key." 问题解决方法
- 基础学习笔记之opencv(6)：实现将图片生成视频
- 深入理解Java虚拟机到底是什么（转）