kczno1的博客

博客

2018-06-30 22:19:32 By kczno1

令$ans_{l}(r)$表示$[l,r]$的答案,$dy(l)$表示$\min r$满足$[l+1,r-1]$可以消除

当$dy(l)$不存在时,$ans_{l}(r)=ans_{l+1}(r)$

否则,当$r < dy(l)$时,$ans_{l}(r)=ans_{l+1}(r)$;当$r \ge dy(l)$时,$ans_{l}(r)=ans_{dy(l)+1}(r)+ r-l+1$

可持久化线段树即可.

时间$O((n+q)log_{2}n)$

xiaoyao

@kczno1 请问求dy的效率为什么是对的呢？如果直接跳链的话有组数据应该开卡的掉：1 1 2 2 3 3 4 4 5 5 1 1 2 2 3 3 4 4 5 5，类似的大数据可以卡到O(n^2)

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。