洛谷 P6136：【模板】普通平衡树（数据加强版） ← Splay树模板题

【题目来源】
https://www.luogu.com.cn/problem/P6136

【算法分析】
Splay 树简介及代码模板：
https://blog.csdn.net/hnjzsyjyj/article/details/138504578

【代码一：含 pushdown() 函数版本】
● 本代码为洛谷 P6136 代码。题目来源为：https://www.luogu.com.cn/problem/P6136
● 洛谷 P6136 的代码一可作为 Splay 树的代码模板，它与洛谷 P3391 代码的差异仅仅在函数 get_val_by_pri() 的定义不同，其他自定义函数 pushup()、pushdown()、rotate()、splay()、insert()、find()、get_pre()、get_suc()、remove()、get_pri_by_val() 完全相同。
● 代码一中 inf 的值按题设定义为 (1<<30)+5，其对应的十进制数为 1073741824。切忌不要定义为传统的 0x3f3f3f3f，因为其对应的十进制数为 7717637477，远超 1073741824。否则，会产生 TLE 和 WA 错误。

#include <bits/stdc++.h>
using namespace std;
 
const int maxn=1.1e6+5;
const int inf=(1<<30)+5;
int n,m;
int root,idx;
 
struct Node {
    int s[2],v,p; //subtree,val,root
    int size,cnt;
    int lazy;
} tr[maxn];
 
void pushup(int x) {
    tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}
 
void pushdown(int x) {
    if(tr[x].lazy) {
        swap(tr[x].s[0],tr[x].s[1]);
        tr[tr[x].s[0]].lazy^=1;
        tr[tr[x].s[1]].lazy^=1;
        tr[x].lazy=0;
    }
}
 
void rotate(int x) {
    int y=tr[x].p;
    int z=tr[y].p;
    int k=(tr[y].s[1]==x);
 
    tr[z].s[tr[z].s[1]==y]=x, tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1], tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y, tr[y].p=x;
 
    pushup(y), pushup(x);
}
 
void splay(int x,int k) {
    while(tr[x].p!=k) {
        int y=tr[x].p;
        int z=tr[y].p;
        if(z!=k) {
            if((tr[y].s[0]==x)^(tr[z].s[0]==y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k) root=x;
}
 
void insert(int x) {
    int u=root, p=0;
    while(u && tr[u].v!=x) {
        p=u;
        u=tr[u].s[x>tr[u].v];
    }
    if(u) tr[u].cnt++;
    else {
        u=++idx;
        if(p) tr[p].s[x>tr[p].v]=u;
        tr[u].p=p, tr[u].v=x, tr[u].size=1;
        tr[u].cnt=1;
    }
    splay(u,0);
}
 
void find(int x) {
    int u=root;
    while(tr[u].s[x>tr[u].v] && tr[u].v!=x) u=tr[u].s[x>tr[u].v];
    splay(u,0);
}
 
int get_pre(int x) {
    find(x);
    if(tr[root].v<x) return root;
    int u=tr[root].s[0];
    while(tr[u].s[1]) u=tr[u].s[1];
    splay(u,0);
    return u;
}
 
int get_suc(int x) {
    find(x);
    if(tr[root].v>x) return root;
    int u=tr[root].s[1];
    while(tr[u].s[0]) u=tr[u].s[0];
    splay(u,0);
    return u;
}
 
void remove(int x) {
    int pre=get_pre(x), suc=get_suc(x);
    splay(pre,0), splay(suc,pre);
    int del=tr[suc].s[0];
    if(tr[del].cnt>1) tr[del].cnt--, splay(del,0);
    else tr[suc].s[0]=0, splay(suc,0);
}
 
int get_pri_by_val(int x) {
    insert(x);
    int ans=tr[tr[root].s[0]].size;
    remove(x);
    return ans;
}
 
int get_val_by_pri(int x) { //apply to P6136
    int u=root;
    while(true) {
        if(x<=tr[tr[u].s[0]].size) u=tr[u].s[0];
        else if(x<=tr[tr[u].s[0]].size+tr[u].cnt) break;
        else x-=tr[tr[u].s[0]].size+tr[u].cnt, u=tr[u].s[1];
    }
    splay(u,0);
    return tr[u].v;
}
 
/*int get_val_by_pri(int x) { //apply to P3391
    int u=root;
    while(true) {
        pushdown(u);
        if(x<=tr[tr[u].s[0]].size) u=tr[u].s[0];
        else if(x==tr[tr[u].s[0]].size+1) return u;
        else x-=tr[tr[u].s[0]].size+1, u=tr[u].s[1];
    }
    return -1;
}*/
 
int main() {
    insert(-inf);
    insert(inf);
 
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        int x;
        cin>>x;
        insert(x);
    }
 
    int ans=0, last=0;
 
    while(m--) {
        int op,x;
        cin>>op>>x;
        x^=last;
        if(op==1) insert(x);
        else if(op==2) remove(x);
        else if(op==3) ans^=(last=get_pri_by_val(x));
        else if(op==4) ans^=(last=get_val_by_pri(x+1));
        else if(op==5) ans^=(last=tr[get_pre(x)].v);
        else ans^=(last=tr[get_suc(x)].v);
    }
 
    cout<<ans<<endl;
 
    return 0;
}
 
/*
in:
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
out:
6
*/


【代码二：不含 pushdown() 函数版本】

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=1.1e6+5;
const int inf=(1<<30)+5;
int n,m;
int root,idx;
 
struct Node {
    int s[2],v,p; //subtree,val,root
    int size,cnt;
    int lazy;
} tr[maxn];
 
void pushup(int u) {
    tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+tr[u].cnt;
}
 
void rotate(int x) {
    int y=tr[x].p;
    int z=tr[y].p;
    int k=(tr[y].s[1]==x);
 
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
 
    pushup(y);
    pushup(x);
}
 
void splay(int x, int k) {
    while(tr[x].p!=k) {
        int y=tr[x].p;
        int z=tr[y].p;
 
        if(z!=k) {
            if((tr[z].s[1]==y) ^ (tr[y].s[1]==x)) rotate(x);
            else rotate(y);
        }
 
        rotate(x);
    }
 
    if(!k) root=x;
}
 
void insert(int x) {
    int u=root, p=0;
    while(u && tr[u].v!=x) {
        p=u;
        u=tr[u].s[x>tr[u].v];
    }
    if(u) tr[u].cnt++;
    else {
        u=++idx;
        if(p) tr[p].s[x>tr[p].v]=u;
        tr[u].p=p,tr[u].v=x,tr[u].size=1;
        tr[u].cnt=1;
    }
    splay(u,0);
}
 
void find(int x) {
    int u=root;
    while(tr[u].s[x>tr[u].v] && tr[u].v!=x) u=tr[u].s[x>tr[u].v];
    splay(u,0);
}
 
int get_pre(int x) {
    find(x);
    if(tr[root].v<x) return root;
    int u=tr[root].s[0];
    while(tr[u].s[1]) u=tr[u].s[1];
    splay(u,0);
    return u;
}
 
int get_suc(int x) {
    find(x);
    if(tr[root].v>x) return root;
    int u=tr[root].s[1];
    while(tr[u].s[0]) u=tr[u].s[0];
    splay(u,0);
    return u;
}
 
void remove(int x) {
    int pre=get_pre(x);
    int suc=get_suc(x);
 
    splay(pre,0);
    splay(suc,pre);
 
    int del=tr[suc].s[0];
    if(tr[del].cnt>1) tr[del].cnt--, splay(del,0);
    else tr[suc].s[0]=0, splay(suc,0);
}
 
int get_pri_by_val(int x) {
    insert(x);
    int ans=tr[tr[root].s[0]].size;
    remove(x);
    return ans;
}
 
int get_val_by_pri(int k) {
    int u=root;
    while(true) {
        if(k<=tr[tr[u].s[0]].size) u=tr[u].s[0];
        else if(k<=tr[tr[u].s[0]].size+tr[u].cnt) break;
        else k-=tr[tr[u].s[0]].size+tr[u].cnt, u=tr[u].s[1];
    }
    splay(u,0);
    return tr[u].v;
}
 
int main() {
    insert(-inf);
    insert(inf);
 
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        int x;
        cin>>x;
        insert(x);
    }
 
    int ans=0, last=0;
 
    while(m--) {
        int op,x;
        cin>>op>>x;
        x^=last;
        if(op==1) insert(x);
        else if(op==2) remove(x);
        else if(op==3) ans^=(last=get_pri_by_val(x));
        else if(op==4) ans^=(last=get_val_by_pri(x+1));
        else if(op==5) ans^=(last=tr[get_pre(x)].v);
        else ans^=(last=tr[get_suc(x)].v);
    }
 
    cout<<ans<<endl;
 
    return 0;
}
 
/*
in:
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4
out:
6
*/




【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/138504578
https://blog.csdn.net/hnjzsyjyj/article/details/138522947



 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/599053.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

预定类小程序源码搭建包含各行业+源码开源可二开+详细图文搭建部署教程

预定类小程序源码搭建包含各行业+源码开源可二开+详细图文搭建部署教程

在数字化浪潮席卷的今天&#xff0c;各行各业都急需找到与顾客连接的新方式。为了满足这一需求&#xff0c;很多店铺和企业都推出了预定类小程序&#xff0c;分享一款开源版预订类小程序源码&#xff0c;一站式解决方案&#xff0c;覆盖餐饮、旅游、美容、医疗、教育等多个行业…
阅读更多...
《架构思维：从程序员到CTO》：通往顶级架构师之路

《架构思维：从程序员到CTO》：通往顶级架构师之路

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…
阅读更多...
让我们把Domino变成SFTP服务器

让我们把Domino变成SFTP服务器

大家好&#xff0c;才是真的好。 远程共享文件有很多办法&#xff0c;其中值得注意的是SFTP方式。SFTP即SSH文件传输协议&#xff0c;通过使用SSH传输层&#xff0c;SFTP可以通过Internet连接安全地访问和移动大量数据文件。 今天我们就介绍使用Domino中的HTTP OSGI方式来实现…
阅读更多...
智慧监测IN！计讯物联筑牢高速滑坡预警“安全锁”

智慧监测IN！计讯物联筑牢高速滑坡预警“安全锁”

在现代社会&#xff0c;高速公路以其高速、便捷的特性&#xff0c;早已成为连接城市与地区之间的重要纽带&#xff0c;承载着日益增长的车流和人流。然而&#xff0c;随着车流量的激增&#xff0c;高速公路面临的运营压力和安全挑战也随之加大&#xff0c;其中滑坡风险尤为突出…
阅读更多...
软考中级-软件设计师（十）网络与信息安全基础知识

软考中级-软件设计师（十）网络与信息安全基础知识

一、网络概述 1.1计算机网络的概念 计算机网络的发展&#xff1a;具有通信功能的单机系统->具有通信功能的多机系统->以共享资源为目的的计算机网络->以局域网及因特网为支撑环境的分布式计算机系统 计算机网络的功能&#xff1a;数据通信、资源共享、负载均衡、高…
阅读更多...
Echarts柱状图横坐标不显示

Echarts柱状图横坐标不显示

本人遇到的问题&#xff1a;折线图横坐标可以正常显示 柱状图接收一样的数据在横坐标却显示不了 1.在前端打印是否能够正常接收数据、数据类型是否有误以及数据是否有内容 console.log(typeof optionbar.xAxis.data)console.log(optionbar.xAxis.data) 2.如上确定能够接收到数…
阅读更多...
ue引擎游戏开发笔记（32）——为游戏添加新武器装备

ue引擎游戏开发笔记（32）——为游戏添加新武器装备

1.需求分析&#xff1a; 游戏中角色不会只有一种武器&#xff0c;不同武器需要不同模型&#xff0c;甚至可能需要角色持握武器的不同位置&#xff0c;因此需要添加专门的武器类&#xff0c;方便武器后续更新&#xff0c;建立一个武器类。 2.操作实现&#xff1a; 1.在ue5中新建…
阅读更多...
艺术的新领域——探索元宇宙艺术展带来的沉浸式艺术体验

艺术的新领域——探索元宇宙艺术展带来的沉浸式艺术体验

在数字化的浪潮中&#xff0c;元宇宙艺术展成为了一种全新的展览形式&#xff0c;它通过虚拟现实、3D建模技术和互动平台&#xff0c;将传统艺术与现代科技巧妙结合&#xff0c;提供了一种前所未有的艺术欣赏方式。此类展览不仅展示了艺术作品的新颖呈现&#xff0c;还为参观者…
阅读更多...
翻译《The Old New Thing》 - Understanding the consequences of WAIT_ABANDONED

翻译《The Old New Thing》 - Understanding the consequences of WAIT_ABANDONED

Understanding the consequences of WAIT_ABANDONED - The Old New Thing (microsoft.com)https://devblogs.microsoft.com/oldnewthing/20050912-14/?p34253 Raymond Chen 2005年09月12日 理解 WAIT_ABANDONED 的后果 简要 文章讨论了在多线程同步中&#xff0c;如果一个线程…
阅读更多...
【贪心算法】最小生成树Kruskal算法Python实现

【贪心算法】最小生成树Kruskal算法Python实现

文章目录 [toc]问题描述最小生成树的性质证明 Kruskal算法Python实现时间复杂性 问题描述 设 G ( V , E ) G (V , E) G(V,E)是无向连通带权图&#xff0c; E E E中每条边 ( v , w ) (v , w) (v,w)的权为 c [ v ] [ w ] c[v][w] c[v][w]如果 G G G的一个子图 G ′ G^{} G′是…
阅读更多...
中国居民消费新特征：中枢回落，即时满足，去地产化

中国居民消费新特征：中枢回落，即时满足，去地产化

随着收入预期和财富效应的转变&#xff0c;居民更倾向于通过短期集中式的消费来获得即时满足的快乐&#xff0c;服务消费表现出了更强的韧性。服务消费强于商品消费、消费去地产化、汽车挑大梁的特征延续。 特征一&#xff1a;消费倾向高于2020-22年&#xff0c;低于2017-19年…
阅读更多...
AI技术赋能下的视频监控方案是如何解决新能源汽车充电难问题的？

AI技术赋能下的视频监控方案是如何解决新能源汽车充电难问题的？

一、方案背景 刚刚结束的第十八届北京车展异常火爆&#xff0c;其中一组与汽车有关的数字让人格外关注。根据乘联会2024年4月19日公布的最新数据&#xff0c;全国乘用车市场零售达到51.6万辆&#xff0c;其中新能源车的销量约为26万辆&#xff0c;市场渗透率达到50.39%。 这意味…
阅读更多...
如何让CANoe或Wireshark自动解析应用层协议

如何让CANoe或Wireshark自动解析应用层协议

当我们使用CANoe软件或Wireshark工具抓取以太网总线上的报文时，网卡首先会把以太网总线上的模拟信号解析成以太网帧数据。数据链路层根据二层头部中的Type字段值确定上层的协议。 如果以太网使用的是TCP/IP协议栈，那么Type值要么是0x0800(IPv4)，要么是0x0806(ARP)，要么是0x…
阅读更多...
SOL链DApp智能合约代币质押挖矿分红系统开发

SOL链DApp智能合约代币质押挖矿分红系统开发

随着区块链技术的不断发展和普及&#xff0c;越来越多的项目开始探索基于区块链的去中心化应用&#xff08;DApp&#xff09;。Solana&#xff08;SOL&#xff09;作为一条高性能、低成本的区块链网络&#xff0c;吸引了众多开发者和项目&#xff0c;其中包括了各种类型的DApp&…
阅读更多...
Ansible自动化工具模块调用与playbook编写

Ansible自动化工具模块调用与playbook编写

目录 一、Ansible工作机制与特点 &#xff08;一&#xff09;Ansible工作机制 1. 初始化与配置 2. 编写Playbook 3. 调用模块 4. 加密敏感数据 5. 执行Playbook 6. 收集执行结果 7. 错误处理与回滚 8. 反馈与报告 &#xff08;二&#xff09;Ansible 的主要特点包括…
阅读更多...
信锐交换机简介及应用说明（1）

信锐交换机简介及应用说明（1）

交换机关键参数及分类 1.线速 线速是指交换机的端口上每秒钟传输的bit数&#xff0c;单位为bps&#xff08;bit per second&#xff0c;即每秒传输多少bit&#xff0c;一个bit也就是一个二进制数0或者1&#xff09;。以我们常见的例子来说明的话&#xff0c;比如100M的网卡就…
阅读更多...
ComfyUI中图像亮度/对比度/饱和度处理

ComfyUI中图像亮度/对比度/饱和度处理

用上面这个节点可以同时设置图片的亮度、对比度和饱和度。 【保姆级教程】一口气分享在ComfyUI中常用的30多种基本图像处理方式 更多好玩且实用AIGC工作流和节点 星球号&#xff1a;32767063 本期资料链接 往期学习资料 整理AI学习资料库
阅读更多...
【容器】k8s获取的节点oom事件并输出到node事件

【容器】k8s获取的节点oom事件并输出到node事件

在debug k8s node不可用过程中&#xff0c;有可能会看到: System OOM encountered, victim process: xx为了搞清楚oom事件是什么&#xff0c;以及如何产生的&#xff0c;我们做了一定探索&#xff0c;并输出了下面的信息。&#xff08;本文关注oom事件是如何生成&传输的&a…
阅读更多...
uniapp的app端软件更新弹框

uniapp的app端软件更新弹框

1&#xff1a;使用html PLUS实现&#xff1a;地址HTML5 API Reference (html5plus.org)&#xff0c;效果图 2&#xff1a;在app.vue的onLaunch生命周期中&#xff0c;代码如下&#xff1a; onLaunch: function() {let a 0let view new plus.nativeObj.View(maskView, {backg…
阅读更多...
mib browser读取mib文件的oid(飞塔防火墙为例)

mib browser读取mib文件的oid(飞塔防火墙为例)

在配置zabbix监控的时候，配置监控项最为麻烦，一般我们都会套用模板，这种方式比较简单，但是有些设备就是没有现成的zabbix模板，怎么办？ 今天我们使用MIB Browser来获取设备SNMP的OID，然后加入zabbix 。 1.什么是MIB Browser SNMP客户端工具MIB Browser， 全名iReasonin…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站