无名行者zzz

知识总结

题解(2)

/ 注册

全部文章 / 知识总结（共3篇）

线段树上的类二分查找总结

非严格二分查找：情形一：给定序列a[1]~a[N], 每次询问给定一个数v, 一个位置pos，从a[pos+1]~a[N]中找到第一个大于v的元素的下标考虑建立一棵普通的位置线段树，树上节点维护当前位置区间的最大值；每次查找时从根递归向下查找，对于当前区间 [ l，r ]： ...

2019-08-30

3 2211

前缀和与差分总结

一维：前缀和的建立： sum[i] = sum[i-1] + val[i], 前缀和求解区间和： { val[l] ~ val[r] } = sum[r] - sum[l-1], 差分标记： [l,r]区间每个点增加v ，则tag[l] += v， tag[r...

2019-08-28

0 881

判断某边是否在图中给定两点间的最短路径上(结论)

由于图中给定两点(假设为No.1 & No.n)间的最短路径不止一条，但可以确定一定是简单通路，因此存在一个较为标准的方法找出在1->n的最短路径的所有边：通过对原图跑Dijkstra求出原点到其他所有点的最短距离dis(1,i) (i : 1~n)，通过对原图的...

2019-07-22

0 625