何事秋。

主席树/线段树

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 主席树/线段树（共14篇）

“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学) E. 小花梨的数组（线段树）

题目链接题面：题解：线段树上每个节点维护该节点上的数唯一分解之后的 p 和 e 因为除***使其不同的质因子减少，乘法不会。所以遇到有可能使质因子减少的情况就一直更改到底即可。因为质因子总个数不会超过20个，所以，遇到质因子减少的情况就往下更改，每个点被更改的次数的期望不超过20次 ...

2020-09-04

0 764

P2468 [SDOI2010]粟粟的书架（主席树）

题目链接题面：代码： #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<...

2020-09-04

0 622

P3157 [CQOI2011]动态逆序对（树状数组，线段树）

题目链接题面：代码： #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<...

2020-09-04

0 632

P3168 [CQOI2015]任务查询系统（主席树）

题目链接题面：题解：将 ( s , e , p) 拆分为（s，p）和（e+1，-p）按照第一键值升序排序，对于每一个（t，p）的二元组，在第 t 棵主席树上的abs（p）位置加上p。查询时，在第 xi 棵主席树上查询前 ki 个数的和。代码： #include<iostr...

2020-09-04

0 440

P3302 [SDOI2013]森林（树上主席树+启发式合并）

题目链接题面：题解：路径上第 k 大用树上主席树完成。合并的时候直接小树往大树上合并（启发式合并）。时间复杂度大概O（n logn logn），也不太会算。 #include<iostream> #include<cstdio> #include<al...

2020-09-04

0 534

2020牛客暑期多校训练营（第四场） A、Ancient Distance（dfs序、线段树）

题目链接题面：题意：给定一棵有根树，根节点是1号节点，在上面选择k个关键点。每个点的权值定义为该点与其最近关键祖先的距离（其祖先中是关键点且距离该点最近的那一个），若其祖先中没有关键点则权值为正无穷，若其本身就是关键点则权值为0。整棵树的权值定义为所有点的权值的最大值。问通过某种方法安排...

2020-09-04

0 321

#121. 「离线可过」动态图连通性（线段树分治）

题目链接题面：题解：线段树分治。（1）有一些操作，每个操作只在 l − r ...

2020-09-04

0 413

HDU - 5390 tree （可持久化字典树+线段树）

题目vj链接题面：题意：给定一棵有根树，根节点为1，节点 i i i 的权值为 ...

2020-09-04

0 348

2020 Multi-University Training Contest 3---- HDU--6793、Tokitsukaze and Colorful Tree（离线+树状数组）

题目链接题面：题意：给定一棵树，根节点为1，每个点有颜色和权值两个属性。我有两种操作，更改某个点的颜色或者更改某个点的权值。询问每次更改之后 <munder> ∑ ...

2020-09-04

0 514

Codeforces Round #406 (Div. 1)--B. Legacy （线段树优化建图，最短路）

题目链接题面：题意：给定一张图，求 S S S 点到其他点的最短路。图以以下形式给出：（1） ...

2020-09-04

0 420