有一个长度为 $n$ 的序列 $a$，现在有一个针对序列 $a$ 的算法。我们设集合 $S_r=\{\text{mex}(l,r)|1\le l\le r\}$，其中 $\text{mex}$ 是区间中最小的没有出现过的自然数，那么这个算法的复杂度为 $\sum_{1\le r\le n}|S_r|$，询问这个算法复杂度的级别，或者换句话说，我们可以将这个算法卡到什么程度？
Blog de OIer_Automation
Blogs
求助复杂度分析
2025-03-30 15:11:22 By
OIer_Automation
Commentaires
Euphoria_
平方级别，考虑从中点处往前放 0,1,2,... 即可
- 2025-03-31 14:00:21
Poster un commentaire
Vous pouvez faire référence à mike en utilisant "@mike", et "mike" sera mis en évidence. Si vous voulez taper le caractère "@", veuillez utiliser "@@" à la place.
Vous pouvez saisir "/kel" pour utiliser l'émoticône "kel". Voici le guide des émoticônes (en chinois).