弓长九日

线段树

CDQ(1) codeforces(1) DP(9) SSM框架(3) 《算法竞赛进阶指南》杂谈(14) 二分(1) 分块(1) 动态规划(1) 图论(11) 基本算法(5) 字符串(6) 差分(2) 并查集(2) 思维(18) 搜索(7) 数学(16) 数据结构(17) 未归档(128) 树型结构(4) 树套数(1) 模拟(2) 爬虫(6) 系统配置记录(1) 计算机网络(2) 贪心(2) 面试(3) 题解(4) 题集(45)

/ 注册

全部文章 / 线段树（共8篇）

线段树|树状数组+离线处理总结

https://blog.csdn.net/qq_40831340/article/details/91404694 此题博客进阶版本 Different GCD Subarray Query HDU - 5869 问你这个区间有多少不同GCD GCD 最多也就log个对于每个数据我们分别存...

2019-09-21

0 638

[树链剖分] P3313 [SDOI2014]旅行(动态开点线段树)

P3313 [SDOI2014]旅行 https://www.luogu.org/problem/P3313 我们单点修改城市的信仰和开销询问路径上同信仰的城市开销的花费和 or路径上最大值显然我们树链剖分完直接建立 1e5 颗线段树是最方便的而且是单点修改确保了我们时间...

2019-09-03

0 856

树链剖分题型总结二

P1505 [国家集训队]旅游 https://www.luogu.org/problem/P1505 这道题是边剖我们要注意的是我们的一条边上路权可以分配给这条树下深度较深的节点上边权转点权就好而且更要注意的是我们的LCA 这个点的权不应该算入因为他算上了他父亲到他的路 ...

2019-09-03

0 402

树链剖分题型总结一

树链剖分模板题首先是树链剖分模板题一般的我将树按轻重儿子建立DFS序列 dfs1 处理轻重儿子子树大小之后的dfs2 就方便处理轻重链的分离了从而线段数维护 dfs序列将一个树上问题转到区间一维的性质1 如果边 ...

2019-09-03

0 413

[最短路优化] Codeforces 786B. Legacy (线段树优化建图)

这建立图的方式网络流也可以出只能说出题人毒瘤啊图是类似线段树结构动态开点参考来源 https://blog.csdn.net/KIDGIN7439/article/details/83623451 线段树优化建图。建立两棵线段树，其上点的点权分别表示“到达这个区间内所有点的最...

2019-08-21

0 605

2019年牛客多校第八场 Explorer (线段树+可撤销并查集)

线段树上套每个区间可以有哪些并查集一直向下如果已经有大区间的管道到n 这个点覆盖区间线段树往下就不必要走了然后学会了安秩合并(启发式搜索) 不能压缩路径我们把大的合并到小的上面就使得长的被查询的的路径尽可能慢的长这样不压缩路径不超时的完成我们合并和实现撤销的操作 ...

2019-08-19

0 422

线段树进阶总结二 (区间取模开根)

P4145 上帝造题的七分钟2 / 花神游历各国洛谷区间开根最多开几次根就变成1了这里我们选择维护区间和如果区间和等于区间长度不更新不等于更新到底反正最多跟新不了几次正好问的也是区间和。。 #include <iostream> #include <c...

2019-08-17

0 525

线段树进阶总结一 DFS序欧拉序(括号序)

DFS序前置的几道题线段树DFS序 1 单点更新区间查询 https://blog.csdn.net/qq_40831340/article/details/84501232 线段树DFS序 2 区间子树更新单点查 https://blog.csdn.net/qq_40831340/ar...

2019-08-16

0 702