线段树合并 题目链接 Problem$n$个点的树上进行$m$次操作,每次操作$(x,y,z)$,表示$x,y$的路径上所有点获得一个数$z$。求$m$次操作后每个点获得的数最多为哪一个? Data Range$1\leq n,m,x,y,z\leq 2022-04-20 数据结构 线段树合并 树链剖分
可持久化Trie (Codeforces 781 E. MinimizOR) 题目链接 Problem定义$f\{A\}=min\{x | y,x,y\in{A}\}$ $a$为一个长度为$n$的非负整数序列,有$q$次询问,对于每次询问$(l,r)$,子序列$f\{a_l,a_{l + 1},…{a_r} 2022-04-19 数据结构 可持久化Trie
【图论基础】 tarjan算法 割点与桥算法简介如果无向图中删除某个点$u$,连通块数量增加,则$u$为图的一个割点;本算法用来找到图中所有割点;如果删除无向图的一条边 $e$,连通块数量增加,则称 $e$ 为桥。 算法思想利用时间戳概念在图中建立一个DFS树,用$dfn 2022-04-14 图论 割点 桥 tarjan
【图论基础】 最短路算法 dijkstra算法算法简介单源最短路算法 算法思想记已经访问过的点集合为$S$,未被访问过的点集合为$T$。 算法步骤: 每次找到$T$中距离源点最近的点$x$ 将$x$点加入$S$集合,此时$x$到源点的距离$dis[x]$即为最短路 2022-04-06 图论 dijkstra floyed SPFA
2018ACM-ICPC 焦作区域赛H题 题目链接 Problem一段序列的映射值为序列的最大值,求一个长度为$n$整数序列$a$的所有本质不同的连续子序列的映射值之和。 Data Range$1\leq n \leq 2\times10^5$ $1\leq a_i\leq 10^ 2022-04-05 字符串 后缀数组 Segment Tree Beats
Codeforces 1656 F. Parametric MST 题目链接 Problem给定$n$个参数$a_1,a_2,\cdots,a_n$,对于$n$个点的无向完全图,令$K_n(t)$表示图上的最小生成树,对于图上任意两点$i,j$的边边权为$w_{ij}(t) = a_ia_j + 2022-04-03 codeforces 思维 最小生成树