OIer_Automation 的博客

博客

求助复杂度分析

2025-03-30 15:11:22 By OIer_Automation

有一个长度为 $n$ 的序列 $a$,现在有一个针对序列 $a$ 的算法。我们设集合 $S_r=\{\text{mex}(l,r)|1\le l\le r\}$,其中 $\text{mex}$ 是区间中最小的没有出现过的自然数,那么这个算法的复杂度为 $\sum_{1\le r\le n}|S_r|$,询问这个算法复杂度的级别,或者换句话说,我们可以将这个算法卡到什么程度?

评论

Euphoria_
平方级别,考虑从中点处往前放 0,1,2,... 即可
  • 2025-03-31 14:00:21
  • Reply

发表评论

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

可以用/kel来使用表情 kel。