Z_L_G

分类

总结(20) 训练赛(18) 题解(129)

/ 注册

全部文章（共8篇）

算法入门-[HAOI2015]树上操作

#dfs序 #线段树题意 1为根的树，n个节点，每个点有点权处理m个操作，操作有三种给某个点的点权+a 给某个点的的子树中所有结点点权+a 询问结点x到根的路径上所有点的权值和思路前两个操作都好处理，借助dfn序把树变为线性结构即可对于询问，dfn无法直接解决到根的路径和，可...

线段树 dfs序

2025-08-23

0 20

算法入门-CF383C

#线段树 #树状数组 #dfn 题意 n个结点，n-1条边，根为1 给定每个点的权值v_i 有m个操作，两种 1 a x 将结点a的权值+x，结点a的儿子权值-x，结点a的孙子权值+x，以此类推 2 a 求a节点的权值思路对于每一个点的修改，在这个点的子树中，所有和它奇偶性相同的点操...

线段树 dfn 树状数组

2025-08-20

0 15

算法入门-求和

#线段树 #树状数组 #dfn序题意 n个结点，n-1条边给定根k和每个点的权值v_i 有m个操作，两种 1 a x 将结点a的权值+x 2 a 求a节点所在的子树的所有结点的权值和思路用dfn把树转化成链线段树or树状数组维护单点修改区间查询代码 #include<...

线段树树状数组 dfn

2025-08-20

0 27

算法入门-华华和月月种树

题意 m个操作，起始只有结点0，有如下三种操作 1 i——在结点i下开一个新点，序号为最大编号 2 i a——给结点i的子树全部加上a 3 i——查询结点i的值思路先把操作记录下来，建出树对整颗子树的操作其实就是对dfn的一段区间操作，所以，所有的操作都可以在按dfn顺序的线段树上...

线段树 dfn

2025-08-18

0 21

总结-扫描线

用途求矩形面积并，面积交，周长并思路用一条假想的线从图形的上方扫到下方，分析扫描线被图形截获的线段就能得到所求结果，过程可以用线段树进行加速面积并从上往下扫，每次扫到和扫描线平行的线就更新线段树线段树一共记录n-1个区间，记录的内容是每个区间被覆盖的次数此时被覆盖的区间数就是...

线段树扫描线

2025-08-09

0 27

算法入门-[SCOI2010]序列操作

题意给定一个长为n的01序列，有五种操作，总共操作m次(n,m<=1e5) 0. 把[a,b]区间内的所有数全变成0 把[a,b]区间内的所有数全变成1 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 询问[a,b]区间内总共有多少个1 询问[a,b]区间...

线段树

2025-08-09

0 21

算法入门-牛牛的最美味和最不美味的零食

题意给定长为n的序列，每个位置有权值两种操作删除第k个，右边的都往左挪一位查询第i个到第j个的最大和最小值思路结构体维护最大最小和区间内的个数删除的时候区间个数-1 查询的时候按照区间个数查询注意查询的时候，直接弹出当且仅当，查询的区间左界比1小右界比个数大不开读写优化...

线段树妙妙题

2025-08-05

0 26

算法入门-数据结构

题意对于一个长为n的序列a，你需要完成q次询问，每次询问有四种情况输出(l,r)区间和输出(l,r)区间平方和 (l,r)所有元素+=x (l,r)所有元素*=x 其中n为1e4量级，m为2e5量级思路线段树变种对于区间和，维护第一个线段树对于区间平方和，维护第二个线段树 ...

线段树妙妙题

2025-08-03

0 36