WC2016鏖战表达式一题,松爷(王逸松,鏖战表达式出题人)在WC上讲了复杂度为每次操作$O(k + \log n)$的做法,即所谓的树(套树)$^*$。然而民间流行一种直接用treap维护的,并把优先级比较定为比较运算符,运算符相同则根据子树大小用概率比较的做法,复杂度为$O(k\log n)$,为什么呢,因为我们先加入一堆1,再加入一堆2,一直到一堆k,每一次新加入一堆运算符,不能改变前面运算符的形态,因此复杂度是$O(k \log n)$,直接提交会得到七十到八十的分数,由于此题数据强度不大,因此稍微根据数据进行修改一些实现细节即可水过。
松爷与我曾多次提到过此事,我也认为此事十分不妥,作为一个很好的数据结构题,留下的却是一堆的水过,以及不断的有新人抱着以为这是正确的做法的心态去写,最后却死活过不去而只能跟着水过的事情。幸运的是考场上并没有人水过。
本题作为一道特殊的题,难以像现在大部分UOJ上的题一样支持hack和extra test,甚至考场数据和grader都使用了特殊的方法加密,因此想要阻止这种现象只要两条路,一是通过@vfleaking等管理员来手工添加一些extra tests强行卡掉复杂度错误的算法,二是靠大家的理解和自觉,理解这种算法的不正确性,并自觉不使用这种算法。
这里我提醒一下大家不要再陷入错误做法的泥潭中。
对于那个$O(k \log n)$的做法,本人也进行了一些改进,可以参见http://uoj.ac/submission/50137 。注意,提交统计里面显示的我的提交是我之前跟着大家水过的程序,并不是这份代码。
我大概是在merge和split的时候进行了一些rotate,具体复杂度无法给出详细证明,但是感觉是$O(k + \log n)$的可能性还是比较大的(当然也有可能是$O(k\log n)$,或者甚至$O(\sqrt{k}\log n)$, $O(k \log k + \log n)$, $O(k \log \log n + \log n)$这些鬼畜的复杂度233,大家还可以继续脑洞),大家可以感受一下我改动的地方。如果觉得我的做法也不靠谱可以学习松爷std程序的做法。如果有谁卡掉了我的做法或者是证明了我的做法的复杂度的确是$O(k + \log n)$,欢迎与我讨论。