观察：只要值域大于数的个数，那么就一定存在一个数没有出现。
我们可以根据这一点对值域进行二分，二分的轮数恰好是 $\lceil\log_2(n+1)\rceil=8$。每一轮我们需要记录当前的左右端点以及在左半边的数的个数，总的状态数是 $O(n)$ 的，因此 $\log n$ 轮总共的状态数是 $O(n\log n)$。
QOJ.ac
QOJ
Discussion #1213 for Problem #17162. Missing Number
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2026-03-06 00:35:52
Last updated: 2026-03-06 00:36:00
题解
Comments
No comments yet.