简单splay模板

2024-05-29 03:18
文章标签 简单 模板 splay

本文主要是介绍简单splay模板,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

splay(x,y)表示将点x旋转到y的下面
fa[x]表示点x的父亲
t[x][0/1]表示点x的左/右儿子
updata用来维护需要维护的东西
标程均为求最大值

单点修改

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int n,a[N],b[N],fa[N],t[N][2];
void updata(int x){a[x]=max(b[x],max(a[t[x][0]],a[t[x][1]]));}
bool lr(int x){return x==t[fa[x]][1];}
void rotate(int x)
{
    int k=lr(x),y=fa[x];
    t[y][k]=t[x][1-k];
    if(t[x][1-k]) fa[t[x][1-k]]=y;
    fa[x]=fa[y];
    if(fa[y]) t[fa[y]][lr(y)]=x;
    t[x][1-k]=y;fa[y]=x;
    updata(y);updata(x);
}
void splay(int x,int y)
{
    while(fa[x]!=y)
    {
        if(fa[fa[x]]!=y)
            if(lr(fa[x])==lr(x)) rotate(fa[x]);
            else rotate(x);
        rotate(x);
    }
}
int main()
{
    scanf("%d",&n);
    fo(i,1,n)
    {
        scanf("%d",&b[i+1]);
        fa[i]=i+1;t[i+1][0]=i;updata(i+1);
    }
    fa[n+1]=n+2;t[n+2][0]=n+1;updata(n+2);
    int m;
    for(scanf("%d",&m);m;m--)
    {
        int x,y,z;scanf("%d%d%d",&z,&x,&y);x++;
        if(z==1)
        {
            splay(x,0);b[x]=y;updata(x);
        }
        else
        {
            y++;splay(x-1,0);
            splay(y+1,x-1);printf("%d\n",a[t[y+1][0]]);
        }
    }
}

区间修改

lz为懒标记
xc和down为下传

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 101000
using namespace std;
int a[N],t[N][2],fa[N],lz[N],b[N],n,s[N];
int lr(int x){return x==t[fa[x]][1];}
void updata(int x){a[x]=max(b[x],max(a[t[x][0]],a[t[x][1]]));}
void down(int x,int v)
{
    a[x]+=v;lz[x]+=v;b[x]+=v;
}
void xc(int x,int y)
{
    while(x!=y){s[++s[0]]=x;x=fa[x];}
    for(;s[0];s[0]--)
    {
        int z=s[s[0]];
        if(lz[z])
        {
            if(t[z][0]) down(t[z][0],lz[z]);
            if(t[z][1]) down(t[z][1],lz[z]);
        }
        lz[z]=0;
    }
}
void rotate(int x)
{
    int k=lr(x),y=fa[x];
    t[y][k]=t[x][1-k];if(t[x][1-k]) fa[t[x][1-k]]=y;
    fa[x]=fa[y];if(fa[y]) t[fa[y]][lr(y)]=x;
    t[x][1-k]=y;fa[y]=x;
    updata(y);updata(x);
}
void splay(int x,int y)
{
    xc(x,y);
    while(fa[x]!=y)
    {
        if(fa[fa[x]]!=y)
            if(lr(x)==lr(fa[x])) rotate(fa[x]);
            else rotate(x);
        rotate(x);
    }
}
int main()
{
    freopen("splay.in","r",stdin);
    freopen("splay.out","w",stdout);
    scanf("%d",&n);
    memset(a,-127,sizeof(a));
    fo(i,1,n)
    {
        fa[i]=i+1;t[i+1][0]=i;
        scanf("%d",&b[i+1]);updata(i+1);
    }
    fa[n+1]=n+2;t[n+2][0]=n+1;updata(n+2);
    int ac;
    for(scanf("%d",&ac);ac;ac--)
    {
        int x,y,z;scanf("%d%d%d",&z,&x,&y);x++;y++;
        splay(x-1,0);splay(y+1,x-1);
        if(z==1)
        {
            int add;scanf("%d",&add);
            down(t[y+1][0],add);
        }
        else printf("%d\n",a[t[y+1][0]]);
    }
}

这篇关于简单splay模板的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012495

相关文章

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav

利用Python编写一个简单的聊天机器人

《利用Python编写一个简单的聊天机器人》这篇文章主要为大家详细介绍了如何利用Python编写一个简单的聊天机器人,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 使用 python 编写一个简单的聊天机器人可以从最基础的逻辑开始,然后逐步加入更复杂的功能。这里我们将先实现一个简单的

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

使用IntelliJ IDEA创建简单的Java Web项目完整步骤

《使用IntelliJIDEA创建简单的JavaWeb项目完整步骤》:本文主要介绍如何使用IntelliJIDEA创建一个简单的JavaWeb项目,实现登录、注册和查看用户列表功能,使用Se... 目录前置准备项目功能实现步骤1. 创建项目2. 配置 Tomcat3. 项目文件结构4. 创建数据库和表5.

使用PyQt5编写一个简单的取色器

《使用PyQt5编写一个简单的取色器》:本文主要介绍PyQt5搭建的一个取色器,一共写了两款应用,一款使用快捷键捕获鼠标附近图像的RGB和16进制颜色编码,一款跟随鼠标刷新图像的RGB和16... 目录取色器1取色器2PyQt5搭建的一个取色器,一共写了两款应用,一款使用快捷键捕获鼠标附近图像的RGB和16

四种简单方法 轻松进入电脑主板 BIOS 或 UEFI 固件设置

《四种简单方法轻松进入电脑主板BIOS或UEFI固件设置》设置BIOS/UEFI是计算机维护和管理中的一项重要任务,它允许用户配置计算机的启动选项、硬件设置和其他关键参数,该怎么进入呢?下面... 随着计算机技术的发展,大多数主流 PC 和笔记本已经从传统 BIOS 转向了 UEFI 固件。很多时候,我们也

基于Qt开发一个简单的OFD阅读器

《基于Qt开发一个简单的OFD阅读器》这篇文章主要为大家详细介绍了如何使用Qt框架开发一个功能强大且性能优异的OFD阅读器,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 目录摘要引言一、OFD文件格式解析二、文档结构解析三、页面渲染四、用户交互五、性能优化六、示例代码七、未来发展方向八、结论摘要

MyBatis框架实现一个简单的数据查询操作

《MyBatis框架实现一个简单的数据查询操作》本文介绍了MyBatis框架下进行数据查询操作的详细步骤,括创建实体类、编写SQL标签、配置Mapper、开启驼峰命名映射以及执行SQL语句等,感兴趣的... 基于在前面几章我们已经学习了对MyBATis进行环境配置,并利用SqlSessionFactory核