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)