动态树LCT 模板

2024-04-14 23:48
文章标签 动态 模板 lct

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

题目描述:
这里写图片描述

输入:
第一行两个整数n和m;
接下来一行中n个整数表示初始点权;
接下来m行每行一个操作如上表所示。

输出:
对于每一个连接操作,若p和q不连通,输出YES,并添加这条边;否则输出NO;
对于每一个删除操作,若p和q间有边,输出YES,并删除这条边,否则输出NO;
对于每一个查询最大及查询和,若p和q连通,输出一行包含一个整数为对应的答案;否则输出一个整数-1。

样例输入:
5 10
1 3 5 4 6
LINK 1 2
LINK 1 3
LINK 2 3
MAX 2 3
UPDATE 1 6
MAX 2 3
LINK 3 5
SUM 3 5
CUT 1 3
SUM 1 5

样例输出:
YES
YES
NO
5
6
YES
11
YES
-1

代码如下:

#include <cstdio>
#include <algorithm>
#define N 50000
using namespace std;
inline int Max(int x,int y) { return x>y?x:y; }
int n,m,x,y;
char s[10];
struct splay{splay *ch[2],*fa;int val,sum,max_val;bool mark;splay(int x);void maintain();int dir();void Reverse();void push_down();void push_up();
}*null=new splay(0),*root[N];
splay :: splay(int x)
{val=sum=max_val=x;ch[0]=ch[1]=fa=null;mark=false;
}
void splay :: maintain()
{sum=ch[0]->sum+ch[1]->sum+val;max_val=Max(val,Max(ch[0]->max_val,ch[1]->max_val));
}
int splay :: dir()
{return fa->ch[0]==this?0:(fa->ch[1]==this?1:-1);
}
void splay :: Reverse()
{if(this==null) return ;mark=!mark;swap(ch[0],ch[1]);return ;
}
void splay :: push_down()
{if(this==null) return;if(mark){ch[0]->Reverse();ch[1]->Reverse();mark=false;}return;
}
void splay :: push_up()
{if(~dir()) fa->push_up();push_down();
}
void turn(splay *c,int d)
{splay *y=c->ch[d^1];c->ch[d^1]=y->ch[d];if(y->ch[d]!=null) y->ch[d]->fa=c;y->ch[d]=c;y->fa=c->fa;int k;if(~(k=c->dir())) c->fa->ch[k]=y;c->fa=y;c->maintain();y->maintain();
}
void splaying(splay *c)
{c->push_up();int d;while(~(d=c->dir())){if(d==c->fa->dir()) turn(c->fa->fa,d^1);turn(c->fa,d^1);}return;
}
void Access(splay *c)
{splay *tmp=null;while(c!=null){splaying(c);c->ch[1]=tmp; c->maintain();tmp=c;c=c->fa;}return;
}
void Move_to_root(splay *c)
{Access(c),splaying(c);c->Reverse();return;
}
void Link(splay *x,splay *y)
{Move_to_root(x);Access(y),splaying(y);if(x->fa!=null) { printf("NO\n"); return; }printf("YES\n");x->fa=y;return;
}
void Cut(splay *x,splay *y)
{Move_to_root(x);Access(y),splaying(y);if(y->ch[0]!=x || x->ch[1]!=null) { printf("NO\n"); return; }printf("YES\n");y->ch[0]=null; y->maintain();x->fa=null;return;
}
void query_Max(splay *x,splay *y)
{Move_to_root(x);Access(y); splaying(y);if(x->fa==null) printf("-1\n");else printf("%d\n",y->max_val);return;
}
void query_Sum(splay *x,splay *y)
{Move_to_root(x);Access(y); splaying(y);if(x->fa==null) printf("-1\n");else printf("%d\n",y->sum);return;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&x);root[i]=new splay(x);}while(m--){scanf("%s%d%d",s,&x,&y);switch(s[0]){case 'U':splaying(root[x]);root[x]->val=y;root[x]->maintain();break;case 'L':Link(root[x],root[y]);break;case 'C':Cut(root[x],root[y]);break;case 'M':query_Max(root[x],root[y]);break;case 'S':query_Sum(root[x],root[y]);break;}}return 0;
}

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



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

相关文章

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

基于Java实现模板填充Word

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

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表