会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
进站占优段要求每个前缀里 0 的个数都严格大于 1 的个数。因此任何进站占优段的左端点都必须是 0。
先考虑弱化条件：每个前缀中 0 的个数不少于 1 的个数。这等价于每个 1 都能在它左边找到一个尚未配对的 0。从右往左扫描，用栈存放尚未配对的 1 的位置；遇到 1 入栈，遇到 0 则弹出一个 1。扫描到位置 i 时，栈顶就是从 i 出发、在弱化意义下第一个非法右端点 p[i]。
原问题比弱化条件更严格。左端点 i 必须是 0：若 i 已是最后一个位置，贡献为 1；否则弱化最长合法段是 [i+1,p[i+1]]，加上左端这个额外的 0 后，严格最长合法段是 [i,p[i+1]]，贡献为 p[i+1]−i。对所有 0 位置累加即得答案。
实现时不必显式求出整个 p 数组，栈模拟过程中直接累加即可。
