P2590 「ZJOI2008」树的统计
重剖后线段树单点修改,区间查询总和或最大值。
P3178 「HAOI2015」树上操作
子树内 DFS 序显然连续。重剖后线段树单点修改,区间查询总和。
因为只查询从根结点开始的链,所以可以不使用树剖。
单点修改相当于修改子树内所有结点答案。
以结点 \(x\) 为根的子树增加 \(a\),对于子树内的某个结点 \(y\),其答案增加了 \((dep_y-dep_x+1)\times a\)。
\((1-dep_x)\times a\) 这一项是共有的,直接子树修改;\(dep_y\times a\) 这一项我们只需要记录 \(a\) 的和,查询时乘上 \(dep_y\) 即可,同样是子树修改。
P2486 「SDOI2011」染色
重剖,线段树上维护区间颜色段数量和两端颜色,区间合并时如果左区间右端点和右区间左端点颜色相同则颜色段数量减一。链与链之间同样如此。
P3976 「TJOI2015」旅游
因为必须先买入再卖出,所以不能只维护最值,必须直接维护求的这个东西。
因为顺序是先从某个点上去到 LCA 再下去到另一个点,所以区间从前往后和从后往前这两种都得维护。合并的时候分三种情况讨论:买卖只在左区间、买卖只在右区间、买卖跨越左右两区间。
显然整个区间增加并不会影响差价,所以可以直接线段树。
P5838 「USACO19DEC」Milk Visits G
重剖,查询序列中某个区间是否存在某个数。
对于每种数开一个 vector 存储其出现的位置,查询时二分即可。
GSS7 - Can you answer these queries VII
重剖后线段树维护最大子段和。
维护区间最大子段和和最大前缀/后缀和,合并时分类讨论。
P1505 「国家集训队」旅游
额外维护一个相反数标记即可。码量较大。
P3313 「SDOI2014」旅行
重剖,查询序列中某个区间内某种教的信息。
前面那题的加强版,对于每种教将 vector 换成一棵动态开点线段树即可。
标签:结点,剖分,dep,线段,查询,区间,维护,树链 From: https://www.cnblogs.com/landsol/p/17250918.html