关于此题暴力赋值的复杂度
查看原帖
关于此题暴力赋值的复杂度
138400
chenxia25楼主2021/2/28 20:56

关于此题的操作 2,如果我们不像题解一样把整段的值记录在最右边的位置上,而是直接线段树区间赋值并按照只有操作 1、3 的版本进行 seg-beats,这样复杂度上界是多少。总感觉无法证明该解法的复杂度,但这种写法的确能通过此题,并且感觉也找不出什么反例出来。所以有大佬给出这种解法复杂度的证明,或者给出一种 hack 吗? 这种写法的 AC 代码:https://codeforces.ml/contest/679/submission/97743972

2021/2/28 20:56
加载中...