QOJ.ac

QOJ

The 3rd Universal Cup Finals is coming! Join our Warm-up Game and Prediction Game and win the prizes! Learn more...

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2026-04-05 16:29:52

Last updated: 2026-04-05 16:29:56

Back to Problem

因为将左括号看作 $1$，右括号看作 $-1$ 时，合法括号序列总和一定为 $0$，所以当选择的区间总和非 $0$ 时，长度一定有上界。当总和等于 $0$ 时，端点选择前缀和最小值的位置即可找到任意长度的合法括号序列。只需要前缀和判断，时间复杂度 $O(N+Q)$。

No comments yet.