HDU-5861 Road 区间更新+DFS遍历

题目大意:有N个点,N-1条带权线段,每条线段只能开关各一次,每天要从点a到点b,求每天的最少花费.
总结:为了使得花费最小,对于一段路来说,它的打开时间就是最早一次被用到到最后一次被用到这段时间.对于每一个操作a,b,在两个点上打上标记,从左至右做一遍扫描,可知道每段路当前有哪些操作会用到它,取出最大值和最小值,在这两个位置打上标记,最后对结果再进行一次扫描即可.

POJ-3177 Redundant Paths 求割边数

题目大意:求割边数

UVA-796 Critical Links 求割边

题目大意:求连通图删除边后图不连通的边集,即割边(桥)

UVA-315 Critical Links 求割点数

题目大意:求删除某个点可使得无向连通图变为多个连通块的点集个数,即割点数。

HDU-5372 Segment Game 离散化+单点

题目大意:有0,1两种操作,0为增加一条线段,并求新增的线段共完全覆盖多少旧线段,1为删除第b条新增的线段。
思路:维护tot,代表新增线段前的边数,每个节点维护lsum,rsum,分别记录左端点个数和与右端点个数和,求得每次新增线段[L,INF]的lsum与[1,R]的rsum,利用容斥的思想,得答案即为lsum+rsum-tot。建树前需要离线将端点先离散化。

SPOJ-DQUERY D-query 主席树

题目大意:查询区间内不同数字个数
思路:记录每个数字最后出现的位置,未出现过则插入,出现过则删除之前的再插入。

HDU-5792 World is Exploding 树状数组

题目大意:给出一个数列,现求四元组(Aa, Ab, Ac, Ad)的个数,其中a,b,c,d互不相等,且1≤aAd。
思路:树状数组维护,首先计算出顺序和逆序的对数并相乘,但是当ac相等,ad相等,bc相等,cd相等的情况时存在重复的情况,可以通过维护以i结尾左边比他大、小的个数,以i结尾右边比他大的个数、小的个数来减去重复的部分。

POJ-1236 Network of Schools 强联通分量

题目大意:有N个按序编号的分发站点,N行,每行包括多个接受站点(以0结尾),第一问至少要分发给多少个站点才能连通所有,第二问要再建几条边才可以使整个图成为强联通图。
思路:第一问显然是缩点后,求入度为0的强联通分量个数。第二问,计算出度入度,发现答案即为出度入度二者大的那个。

SGU-180 Inversions 树状数组+离散化

题目大意:求逆序对个数
思路:树状数组

HDU-1255 覆盖的面积 扫描线

题目大意:计算n个矩形并重叠超过1次的部分面积。
思路:维护一个flag表示区间是否被全部覆盖, 维护sum1表示区间被覆盖一次以上的线段长度, 维护sum2表示区间被覆盖2次以上的线段长度.如果flag > 1表示全部被覆盖至少2次, 如果flag = 1并不是表示被覆盖了一次, 被覆盖的次数需要从孩子节点获取(当前sum2 = ls.sum1 + rs.sum1, 孩子覆盖了一次以上同时当前区间也至少被覆盖一次以上, 那么就表明当前区间被覆盖了至少两次以上), 如果flag = 0并不是表示区间没被覆盖至少两次, 还需要从孩子节点获取信息。