T4
题意
一共进行k轮比赛
每轮的第G场有一个标签,表示擂主是编号小的还是大的那个
擂主的获胜条件为能力值大于等于当前的轮数
求最后所有可能的胜者的编号之和
每场比赛人数必须为2的次幂,不足的可以补过来任意能力值的人
一共报名了n个人,给定m个c,求只有前c个人报名时的最终答案
分析
不难发现这实际上是一个满二叉树
特殊性质A
8pts
发现如果c本身就是2的幂次，那么所有人的能力值我都是知道的，对于这一整场的最终胜者也是知道的，那么对于一个c也就只有一个ans，这一部分是好做的,直接模拟即可。code
16pts
注意到，如果所给的c是2的幂次，由于n只有1e5，所以大部分c都是重复的,需要算的c很少,开一个桶存一下即可。code
正解
这个特殊性质告诉了我们不少信息，算是启发正解的第一步，那么接下来就要考虑如何一步步推出正解
\(O(Tmnlogn)\)
受到特殊性质A的启发，我们发现对于能力值已知的选手，他们之间进行的比赛结果是固定的，这个可以预处理出来；对于能力值未知的选手，他们之间的比赛结果不重要，因为这种情况下谁都可以赢，所以谁都可以赢，这点也可以预处理出来。
那么现在较为复杂的部分就是左边是能力值已知的，右边是能力值未知的。
考虑进行分类讨论：
1.当能力值已知的选手是擂主时，这个可以直接判断，如果能力值大于等于当前轮次，那么另一个选手就寄了，否则自己就寄了。
2.当能力值未知的选手是擂主时，我既可以使自己赢也可以使另一个人赢，怎么办呢？
这时不妨先想一想我们最后该如何统计答案，由于我已经预处理好了每一轮每一场谁会赢，那我枚举每个点往上跳，如果我输了那我就不会对答案产生贡献，如果我一路跳到根节点，那我就可以计入答案里。
那么对于第二种情况解决方案也就出来了。
如果擂主能力值未知，我直接让另一个人赢就好了，那如果我到最后也有机会赢怎么办？
对于这种情况是很难处理的，但是不妨转换一下视角，现在对于那些能力值已知的选手，我已经可以判断其会不会赢，只剩下那些能力值未知的选手了，由于一路上我把他们都删了，所以除非有能力的小于当前轮次，不然能力值未知的一定不会赢。
我们来分析一下那些能力值未知的人都是怎么输的，一种是别人当擂主赢了，我就输了，那么这种情况我就一定不会赢，另一种是我是擂主，但是我故意输了，那么这种情况我其实还有机会赢，直到与我对战的这个人是因为作为非擂主输掉后我才会真正的输，否则如果与我对战的这个一路赢下去了，我也可以跟着一块赢。
那么我只需要在未知的人必输的点上打一个tag,那么我就可以判断这个未知点是否可以赢,只要一路上都没有tag,那么我就有机会赢。
那么考虑一下这个复杂度，预处理时访问了树上的所有点，是\(O(n)\)的,枚举每个点往上跳最多\(logn\)次,一共m组询问,T组测试点,所以总复杂度为\(O(Tmnlogn)\),预期过掉\(n \le 5000\)那档分。
虽然理论如此，不过这档分本质上还是一个模拟，而且这个模拟也是异常困难，导致照着40pts写了很久只能得32pts，很难评，真的实在不想再调了。
\(O(T(m+nlogn))\)
由于上档分的细节特别多，而且复杂度也不优，所以考虑对其进行优化。
注意到一个问题，如果我对每个c去看每个i是否能成为答案是非常不优秀的，如果我们可以对每个i看看我可以对哪些c产生贡献，那么这个复杂度一下子就下来了，那么，我们该如何实现呢？
其实我们早就应该注意到了一件事,对于一个左子树,无论我的c多小,我原来会赢的现在依然会赢。
举个例子吧，比如在节点1，8号赢了，那么当c=4时，显然我记录的1号点的胜者就是8，而当我的c不断减小，会变的只有已知变为未知，由于我未知的自动认输，所以9，10变不变不影响我8会不会赢，而如果8也未知了那我就更能赢了。所以对于已知选手我是可以对很多个c一起做贡献的。
那么还是和上面一样的问题，未知选手该怎么办？其实上面的已知选手已经作了铺垫，还是刚才的例子，这次我们考虑当c=3时10号点的情况，只要9不是必赢那么我的10就能赢，而当c不断减小时10号依然能赢，所以对于每个未知选手都会有一个最大的\(c\)，使得当\(c_i\le c\)时,该未知选手会对答案产生贡献。因此未知选手也会对很多c一起做贡献。
那么此时我们就可以重新设计状态了。上一部分我们用f[x]表示x号点的胜者，规则为未知选手让已知选手，最后用tag来计算未知选手的情况，这样的话对于每个\(c_i\)我们都需要从头来算,实在太慢了。而我们刚才已经分析过了,已知和未知都可以对许多\(c_i\)作出贡献。首先还是先看已知选手,根据刚才的分析,随着\(c_i\) 的减小,我原来的获胜者现在也一定可以获胜。
所以不妨设f[x]表示:当\(c_i==n\)时,节点x的获胜者,那么此时我的f就会对多个\(c_i\)产生贡献,这时的f就和上面的规则大不相同了,上面我们优先让未知选手赢,但现在全是已知的了,只有最后一次合并才会遇到未知的,所以我就按照正常的比赛规则,将未知选手能力值设为正无穷,那么直到最后一次合并之前我的状态都是很对的,并且这样的话对于每一个左子树我都能很轻易的找到胜者，那么这些贡献算起来也很容易(应该早就看出来并不是所有的比赛都会直到到达0号点才会结束吧？)。
那么再来考虑未知选手，我们也是根据对未知选手的分析，设g[x]表示:若使x号节点有未知选手获胜,我的\(c_i\)最大是多少。那么当\(c_i \le g[x]\)时,我的未知选手就可以对答案产生贡献,并且当\(c_i > g[x]\)时,我的未知选手是一定不会赢的,这点在上面已经提到了,那么这时候也可以根据g来等效实现上一档分里未知选手认输的情况,因为我的\(c_i \le g[x]\)只是表示存在未知选手可以获胜,并不代表此时他一定获胜。此外,g数组也可以作为一些已知选手的可能获胜的限制,因为当\(c_i>g[x]\)时,已知选手的胜负是固定的,就不存在多种情况了,这时候就需要用到f而不是g了(伏笔)。
那么现在只剩计算答案的环节了。这个做法还是需要模拟每个点往上跳的，所以还是有一个log的，每次跳的时候，维护一个maxn，表示点i可以赢的最大\(c_i\)值,对于未知选手显然就是g数组,对于已知选手,如果是擂主会很好计算,否则需要和兄弟的g取min(伏笔回收)。实际上所有的答案应该都是在一个左子树(其父节点所在子树也必须是左子树)的根节点上,这点刚才也提过了,所以枚举每个点往上跳的时候,只要跳到一个左子树(同上)上,我就可以对一个区间做出贡献,而对于已知选手i,需要将这个区间与[i,n]取交,对于未知选手,需要和[1,i)取交,这是为了避免重复计算的情况,并且最后还要对[1,maxn]取交,这是其可以获胜的条件。那么一个点的贡献是一个区间，可用差分优化。那么至此，这道黑题你就有了80pts。(虽然这档分没写,不过听起来非常有道理对吧)
\(O(T(n+m))\)
终于到最后一步了,这也太困难了吧。不过没关系,上一档分是最难理解的,这一档还是挺容易的。
由于我们从下往上跳，复杂度会多带一个log，那么如何优化呢？
其实很简单，我们刚才统计答案是每个点都要跳，导致会有的点重复经过，那么如果我从上往下跳不就可以了吗？
对，没错，这样就做完了，每个点只会遍历一次，存储的fg以及最后的差分都是一样的，复杂度从\(O(T(nlogn+m))\)变成了\(O(T(n+m))\),于是乎,这道黑题就被你秒掉了。
（看完题面之后，整个比赛过程像不像线段树，听说利用线段树也可以优化掉这个log，我就不写了，大家应该都会bushi）