首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

LCT

编程知识
2024年09月18日 19:04

\(LCT\),全称 \(Link\) \(Cut\) \(Tree\),可以解决动态树问题。

动态树(LCT)

\(isroot\) 操作

如果一个点不是根,则考虑它既不是父亲的左儿子也不是父亲的右儿子。代码:

bool isroot(int x){
    return tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x;
}

\(rotate\) 操作

假设 \(x\)\(7\)\(y\)\(3\)\(z\)\(1\),也就是说要把 \(7\) 旋上去。考虑旋上去的话,就把父亲转到自己下面。于是先断开与父亲的边,连上与爷爷的边。

接下来发现父亲少了一个儿子,于是把自己的另外一边的儿子给父亲,同时把他连接自己的边断掉。

最后我们只需要链接 \(x\)\(y\),只不过这次 \(x\) 是父亲。

代码:

void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))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);
}

\(splay\) 操作

先分类讨论一下,看 \(x,y,z\) 在不在一条直线上,可以看一下图:

不难发现,如果在一条直线上,则先转 \(y\),再转 \(x\);否则连着转两下 \(x\)。这样一直操作直到 \(x\) 被转到跟上。

但是在进行旋转之前,我们要先把转上去的路径做个 \(pushdown\)。代码:

void splay(int x){
    int top=0,r=x;
    stk[++top]=r;
    while(!isroot(r))stk[++top]=r=tr[r].p;
    while(top)pushdown(stk[top--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
From:https://www.cnblogs.com/zxh923aoao/p/18419085
本文地址: http://www.shuzixingkong.net/article/2109
0评论
提交 加载更多评论
其他文章 OSG开发笔记(三十):OSG加载动力学仿真K模型文件以及测试Demo
前言 Osg需要打开模型文件,但是遇到显示动力学仿真的K模型文件,.k文件是一种描述材料属性的文件,比如密度、弹性模量等,该模型文件不是常规中间开放格式,无法直接支持,需要自定义解析并且重建三维模型。 Demo 实际非常流程,因为视频转gif导致部分看起来不行: 交互流畅性测试 实际研发需要用不同的
OSG开发笔记(三十):OSG加载动力学仿真K模型文件以及测试Demo OSG开发笔记(三十):OSG加载动力学仿真K模型文件以及测试Demo OSG开发笔记(三十):OSG加载动力学仿真K模型文件以及测试Demo
Ubuntu 64系统编译android arm64-v8a 的openssl静态库libssl.a和libcrypto.a
#!/bin/bash # Cross-compile environment for Android on ARM64 and x86 # # Contents licensed under the terms of the OpenSSL license # http://www.openssl
Ubuntu 64系统编译android arm64-v8a 的openssl静态库libssl.a和libcrypto.a
高效打造跨平台桌面应用:Electron加载服务器端JS
在现代桌面应用开发中,使用 Electron 加载远程服务器托管的前端资源,再与本地 API 交互,能够带来灵活的部署和强大的本地功能支持。这种方式不仅提升了开发效率,还能充分利用 PC 端的资源和性能。 本文将深入解析如何使用 Electron 实现这一架构,并探讨其背后的关键技术,包括 ipcM
火山引擎数智平台:高性能ChatBI的技术解读和落地实践
导读:大模型能力的发展和成熟,催生出新一代智能化 BI—— ChatBI,即通过自然语言处理(NLP)与大型语言模型(LLMs)的结合,极大简化数据分析过程,提高效率并降低分析门槛。火山引擎数智平台旗下智能数据洞察产品 DataWind 近期上线 ChatBI 能力,提供智能修复、多语法适用等能力,
火山引擎数智平台:高性能ChatBI的技术解读和落地实践 火山引擎数智平台:高性能ChatBI的技术解读和落地实践 火山引擎数智平台:高性能ChatBI的技术解读和落地实践
手脱upx
其实已经是大一下刚开始的事情了,补个档 手动脱壳の新年快乐 查壳,有壳,UPX X32dbg打开文件,查看初始断点 点击PUSHAD跟进,CTRL+*设置EIP,开始F8步过,寻找ESP寄存器第一次单个变红的地址 此时的内存窗口 开始步过 第一次步过就发现ESP单个变红,右键跟进内存窗口 然后在第一
手脱upx 手脱upx 手脱upx
扩展分析C语言单双引号、反斜杠与注释
目录注释奇怪的注释C风格的注释无法嵌套一些特殊的注释注释的规则建议反斜杠'\'反斜杠有续行的作用,但要注意续行后不能添加空格回车也能起到换行的作用,那续行符的意义在哪?反斜杠的转义功能单引号和双引号字面值,字符串,字符,字符变量的大小为什么sizeof('1')的大小
扩展分析C语言单双引号、反斜杠与注释 扩展分析C语言单双引号、反斜杠与注释 扩展分析C语言单双引号、反斜杠与注释
全面掌握 Jest:从零开始的测试指南(下篇)
在上一篇测试指南中,我们介绍了Jest 的背景、如何初始化项目、常用的匹配器语法以及钩子函数的使用。这一篇篇将继续深入探讨 Jest 的高级特性,包括 Mock 函数、异步请求的处理、Mock 请求的模拟、类的模拟以及定时器的模拟、snapshot 的使用。通过这些技术,我们将能够更高效地编写和维护
全面掌握 Jest:从零开始的测试指南(下篇)
mongo 副本集rs 理解和使用小结
转载请注明出处: 在MongoDB中,rs(通常指的是“replica set”的缩写)是复制集(Replica Set)的标识符或在使用时的一种常见前缀,尤其是在命令行工具和脚本中引用复制集时。复制集是MongoDB用来实现数据冗余和高可用性的一个核心组件。 复制集(Replica Set)的作用