精锐
线段树\(\big/\)平衡树综合题目五步取首
1、每个节点需要维护的信息有？
可从题目要求的目标或经推导后得到的要求的目标得到
如对于括号序列这一题，将"("转化为-1，")"转化为1后，要求的答案就变成了最大前缀和和最小后缀和
然后就变成了平衡树板题（区间赋值，反转，翻转）
2、需要的标记有？
一般的标记有：区间赋值，区间翻转，特殊标记，从要维护的信息可以得到
3、如何下传标记？
这里要考虑标记更新的优先级：如取反>覆盖，在对区间进行取反时要将覆盖标记也取反
平衡树下传标记与线段树类似
4、如何整体修改区间？
在对应子树根上打标记，因为可以通过下传标记进行区间赋值
5、如何合并区间？
考虑如何对该区间需维护的值进行更新即可
经验谈
1、设置标记时，可从要维护的量进行步步分析，如想维护某个量，就要想这个量如何从子区间合并过来，再想如果要用别的量辅助区间量的维护，那么那个辅助量该如何维护，以此类推，直到封闭
2、设置标记用于区间修改时，只用考虑该操作是否符合结合律，\(pushdown\)是具有即时性的，每次打标记前都会对当前标记进行下传，因而标记的操作先后顺序是按操作发生的时间进行排序的，新的操作总是衔接在旧操作之后，所以像区间历史最值这样的，完全可行
3、对于区间历史最值问题，需要酌情考虑每一个标记具体的作用、下传时间以及维护时的先后顺序，不然很容易挂，可以从“若一个\(fath\)正在向儿子\(pushdown\)，此时\(fath\)中的标记一定是在儿子的标记之后打上去的，每一个\(pushdown\)本质上是在儿子的操作序列后加上一个操作序列”进行考虑，对每一个节点进行操作时都要考虑这样是否对下传标记时会造成影响，所以思考这一类问题时，思路一定要清晰，稍微乱起来就会很恶心，可以考虑将各个标记的更新分成几个函数打出来，这里可以参考经典老题CPU监控题解做法
标签：26,标记,97th,取反,2024,区间,操作,维护,考虑 From： https://www.cnblogs.com/tlz-place/p/18440819