突发奇想搞个专题

静态树问题，其实没有什么实际作用，只是一些idea。。

一般来说这种题都可以用链剖直接秒= =（不过这些做法数据都可以出到50W)

no.1 不带修改链上第k大问题，强制在线

no.2 带修改链上和问题

no.3 带修改子树最大、和问题

no.1 函数式线段树，每个点建他父亲上，然后就变成线段树上查询第k大了

no.2 考虑括号序列，左括号为该点点权，右括号是点权的相反数，然后发现括号序列的前缀和就是树的前缀和！然后就没了

no.3 最简单，考虑dfs序，子树都是连续的，题目转化为区间rmq和区间和

简单实用的小技巧。。（然而并没有什么卵用。。

每天搞些无聊的东西。。上次在uoj群问一题怎么用dfs序搞被D了55555

不知道在干嘛。。发现括号序列可以解决的问题。dfs序基本都可以完成。因为对于负的其实没必要新建出一个点。

考试的时候blog看看呐。。然后现在改编了一下那题。出了出来。

你以为我会放题解？。。链上修改，单点、子树询问。

想多了。。树状数组复合即可。常熟太大，只能把树剖卡到标算两倍。。

我才没那么SB呢。。看上去小朋友树剖都不会写的样子。。是不是可以直接拿来出题了。。

你以为我是你么。。满二叉树是不是卡树剖很资磁啊。。？但是感觉这样会被暴力草。。

唉。。找题解不好少年。。。所以就变成了一条10W的链+满二叉树。成功把树剖卡到60分。。