刷题记录:牛客NC23051华华和月月种树 树链剖分+离线加点
传送门:牛客
题目描述:
华华看书了解到,一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了,所以他们种的树是信息学意义下的。
华华和月月一起维护了一棵动态有根树,每个点有一个权值。刚开存档的时候,树上只有 0 号节点,权值为 0 。接下来有两种操作:
操作 1:输入格式1 i,表示月月氪金使节点 i 长出了一个新的儿子节点,权值为0,编号为当前最大编号 +1(也可以理解为,当前是第几个操作 1,新节点的编号就是多少)。
操作 2:输入格式2 i a,表示华华上线做任务使节点 i 的子树中所有节点(即它和它的所有子孙节点)权值加 a 。
但是月月有时会检查华华有没有认真维护这棵树,会作出询问:
询问 3:输入格式3 i,华华需要给出 i 节点此时的权值。
华华当然有认真种树了,不过还是希望能写个程序以备不时之需。
输入:
9
1 0
2 0 1
3 0
3 1
1 0
1 1
2 0 2
3 1
3 3
输出:
1
1
3
2
树上操作,使用树链剖分+线段树进行解决
对于操作2和操作3,我们可以将树形结构分解成线性结构然后使用线段树进行维护区间修改即可.对于分解树形结构的算法可以使用dfs序进行解决,也可以使用树链剖分进行解决.两者相比,dfs序的代码量更短,但是树链剖分能解决的情况更为普遍,所以对于本题来说,博主使用的树链剖分算法
对于操作一,我们发现我们需要动态的对树进行加点操作,对于这种操作,我们发现很难进行维护.所以我们考虑进行离线维护.对于所有的加点操作,我们都假设全部都已经完成.建一颗最终的树.然后对于这些树来说,我们对此每一个节点使用操作2.
此时肯定会发现这种做法存在这样的一个问题,因为我们此时对uuu的所有节点增加了一个权值,但是对于uuu的一些节点(假设为v)来说,可以本来是在这个操作之后才产生的,所以此时我们的操作是错误的.所幸的是此时我们需要统计的只是单点的全职,所以此时当我们v还未出现之前,我们直接将v的权值改变了对于我们的查询来说并没有问题,因为我们此时根本不会查询这个点.然后当我们的这个点出现之后,只要将这个点的权值归0即可,此时我们的v节点就可以保证正确性了
为了操作方便,可以将所有节点的编号加一
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int fa[maxn],dep[maxn],max_son[maxn],Size[maxn];
vector<int>edge[maxn];
void dfs1(int u,int pre_u) {Size[u]=1;for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==pre_u) continue;dep[v]=dep[u]+1;dfs1(v,u);fa[v]=u;Size[u]+=Size[v];if(Size[v]>Size[max_son[u]]) {max_son[u]=v;}}
}
int top[maxn],id[maxn],rev[maxn],tot=0;
void dfs2(int u,int t) {top[u]=t;id[u]=++tot;rev[tot]=u;if(!max_son[u]) return ;dfs2(max_son[u],t);for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==fa[u]||v==max_son[u]) continue;dfs2(v,v);}
}
struct Segment_tree{int l,r,sum,lazy;
}tree[maxn*4];int w[maxn];
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;tree[rt].sum=tree[rt].lazy=0;if(l==r) return ;int mid=(l+r)>>1;build(lson);build(rson);
}
void pushup(int rt) {tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void change(int rt,int val) {int len=tree[rt].r-tree[rt].l+1;tree[rt].sum+=len*val;tree[rt].lazy+=val;
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy=0;
}
void update(int l,int r,int rt,int val) {if(tree[rt].l==l&&tree[rt].r==r) {change(rt,val);return ;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) update(l,r,ls,val);else if(l>mid) update(l,r,rs,val);else update(l,mid,ls,val),update(mid+1,r,rs,val);pushup(rt);
}
int query(int pos,int rt) {if(tree[rt].l==pos&&tree[rt].r==pos) {return tree[rt].sum;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) return query(pos,ls);else return query(pos,rs);
}
struct OPT{int opt,pos,Date;
}opt[maxn];
int main() {int m=read();int cnt=1;for(int i=1;i<=m;i++) {opt[i].opt=read(); if(opt[i].opt==1) {opt[i].pos=read();edge[opt[i].pos+1].push_back(++cnt);opt[i].Date=cnt;}else if(opt[i].opt==2) {opt[i].pos=read();opt[i].Date=read();}else {opt[i].pos=read();}}dfs1(1,0);dfs2(1,1);build(1,tot,1);for(int i=1;i<=m;i++) {if(opt[i].opt==1) {int u=opt[i].Date;int t=query(id[u],1);update(id[u],id[u],1,-t);}else if(opt[i].opt==2) {int u=opt[i].pos+1;update(id[u],id[u]+Size[u]-1,1,opt[i].Date);}else {int u=opt[i].pos+1;printf("%d\n",query(id[u],1));}}return 0;
}
相关文章:
刷题记录:牛客NC23051华华和月月种树 树链剖分+离线加点
传送门:牛客 题目描述: 华华看书了解到,一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了,所以他们种的树是信息学意义下的。 华华和月月一起维护了一棵动态有根树,每个点有一个权值。刚…...
年薪20W软件测试工程师必备的6大技能(建议收藏)
软件测试 随着软件开发行业的日益发展,岗位需求量和行业薪资都不断增长,想要入行的人也是越来越多,但不知道从哪里下手,今天,就给大家分享一下,软件测试行业都有哪些必会的方法和技术知识点,作…...
【存储】RAID2.0+、多路径技术、磁盘可靠性技术
RAID2.0RAID 2.0技术RAID技术发展RAID 2.0软件逻辑对象RAID 2.0基本原理硬盘域Storage Pool & TierDisk Group(DG)LD(逻辑磁盘)Chunk(CK)Chunk Group(CKG)ExtentGrainVolume &am…...
Vue 2
文章目录1. 简介2. 第一个Vue程序3. 指令3.1 判断循环3.2 操作属性3.3 绑定事件3.4 表单中数据双向绑定3.5 其他内置指令3.6 自定义指令4. 组件4.1 全局注册4.2 局部注册4.3 组件通讯4.4 单文件组件5. 组件插槽5.1 单个插槽5.2 具名插槽5.3 作用域插槽6. 内置组件6.1 component…...
Ubuntu 安装 Docker Engine
【参考】Install Docker Engine on Ubuntu | Docker Documentation: https://docs.docker.com/engine/install/ubuntu/ 【参考】Docker CE 镜像源站-阿里云开发者社区 https://developer.aliyun.com/article/110806 【规范】模仿 Docker 文档,Ubuntu, Docker 首字母…...
SpringBoot入门 - 添加内存数据库H2
上文我们展示了通过学习经典的MVC分包结构展示了一个用户的增删查改项目,但是我们没有接入数据库;本文将在上文的基础上,增加一个H2内存数据库,并且通过Spring 提供的数据访问包JPA进行数据查询。准备知识点在介绍通过Spring JPA接…...
高质量数字化转型创新发展大会暨中国信通院“铸基计划”年度会议成功召开
2023年3月3日,由中国信通院主办的高质量数字化转型创新发展大会暨中国信通院“铸基计划”年度会议在北京成功召开。本次大会深度展示了中国信通院在数字化领域的工作成果,并全面展望了2023年行业的数字化发展趋势。同时,大会发布了中国信通院…...
2023年如何通过软考初级程序员?
初级的考试难度不大,稍微有点编程基础,认真备考应该没什么大问题。 先清楚大纲: 高效备考!理清考点,针对性复习 科目一:综合知识 75道单项选择题,1题1分,时长150分钟;…...
视频自动播放的实现与问题解决
一、前言 页面加载一个视频并且自动播放,这个需求看起来非常简单,实现起来感觉也非常简单;但是,实际做起来还是有几处容易产生问题的地方卡住进度。本文讨论基于Vue3的项目在实现页面加载视频后的自动播放遇到的几个问题。 二、页面实现 页面实现非常简单。在页面上放置一个…...
ThreadLocal 理解及面试
一、ThreadLocal 引用关系 图解关系说明: 每个线程拥有自己的 ThreadLocalMap 属性;ThreadLocalMap 的存储结构为 Entry[] 数组;Entry的Key是ThreadLocal类型且弱引用指向ThreadLocal对象,Value是我们自己定义的泛型值对象&#…...
巾帼绽芬芳 一起向未来(中篇)
编者按:为了隆重纪念纪念“三八”国际妇女节113周年,快来与你全方位、多层次分享交流“三八”国际妇女节的前世今生。分上篇(节日简介、节日发展和节日意义)、中篇(节日活动宗旨和世界各国庆祝方式)和下篇&…...
Qt学习2-Qt Creator新建项目小tips(哔站视频学习记录)
放送两个小tips: 1、MinGW和MSVC的区别 QT学习笔记(二):QT MinGW 和 MSVC 编译方式_Leon_Chan0的博客-CSDN博客 2、如何安装QT对应版本的MSVC (1)问题描述:Qt5.12.8支持MSVC2015和MSVC2017,但是系统安装的是Visual…...
React-高阶组件
认识高级组件 高阶函数的维基百科定义:至少满足以下条件之一 1、接受一个或多个函数作为输入; 2、输出一个函数; JavaScript中比较常见的 filter、map、reduce 都是高阶函数 那么说明是高阶组件呢? 高阶组件的英文是 Higher-Order Components,简称为 HOC;官方的…...
python学习——【第一弹】
前言 Python是一种跨平台的计算机程序设计语言,是ABC语言的替代品,属于面向对象的动态类型语言,最初被设计用于编写自动化脚本,随着版本的不断更新和语言新功能的添加,越来越多被用于独立的、大型项目的开发。 从这篇…...
数据结构——链表讲解(1)
作者:几冬雪来 时间:2023年3月3日 内容:数据结构链表讲解 目录 前言: 链表的概念: 1.为什么要有链表: 2.链表的运行原理: 3.链表的形态多少: 4.单链表的代码书写࿱…...
docker部署MySQL主从服务
一.主从同步流程关于MySQL主从复制主要同步的是binlog日志,涉及到三个线程,一个运行在主节点(log dump thread),其余两个(I/O thread, SQL thread)运行在从节点,如下图所示:当主库数据发生变更时࿰…...
儿童护目台灯哪种好用?几款真的保护视力的台灯品牌推荐
儿童眼睛还未发育完全,眼睛比较脆弱,但是现在的小孩子学习任务也比较繁重,经常晚上看书写字,所以选择合适的护眼台灯来保护眼睛很重要。 选择儿童护目台灯需要注意以下几个方面: (一)色温和亮…...
游戏逆向基础之OD找CALL实践
在逆向中除了分析数据之外,另外一个重要的工作就是找算法,找CALL 例如各种功能函数:攻击CALL,走路CALL,喊话CALL等等 以及加密解密等算法需要我们先锁定其位置,然后进行逆向分析。 最常见方法一 API函数下断,例如send …...
File 文件操作
File 文件操作: 一、常用方法: 方法类型描述public File(String pathname)构造给定一个要操作文件的完整路径public File(File parent, String child)构造给定要操作文件的父路径和子文件名称public boolean createNewFile() throws IOExce…...
QT基础(18)- QAbstractSocket
QT基础(18)- QAbstractSocket1 创建简单的客户端2 QAbstractSocket2.1 简介2.2 枚举2.2.1 BingFlag2.2.2 NetworkLayerProtocol2.2.3 PauseMode2.2.4 SocketError2.2.5 SocketOption2.2.6 SocketType2.2.7 SocketState2.3 公有函数2.3.1 构造函数2.3.2 a…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
