题解

这道题要求通过交互方式恢复一个合法的括号序列，其核心在于利用括号序列的匹配性质和区间性质。

基本思路

已知原始程序是合法的括号序列，意味着：

1. 序列长度为 $n$ 且由 ( 和 ) 组成
2. 整个序列是平衡的：任意前缀的高度 $\ge 0$，最终高度 $= 0$
3. 对于任意区间 $[l, r]$，询问结果为 Yes 当且仅当该子区间本身也是一个合法的括号序列

关键性质

对于一个合法的括号序列，我们可以观察到以下重要性质：

性质 1：如果 $[l, r]$ 是一个合法的括号序列，那么 $s[l]$ 和 $s[r]$ 一定是一对匹配的括号。

证明： 考虑区间 $[l, r]$ 的括号序列。由于它是合法的，第一个字符必须是 (（否则从一开始高度就变为负数）。最后一个字符必须是 )（否则高度无法归零）。而且，第一个 ( 一定和最后一个 ) 匹配。因为如果第一个 ( 和中间的某个 ) 匹配，那么剩下的部分无法形成合法序列。

性质 2：对于任意位置 $i$，设 $L_i$ 是与 $i$ 匹配的左括号位置，那么区间 $[L_i, i]$ 一定是合法的。

证明： 这是由括号匹配的定义直接得到的。

算法设计

基于上述性质，我们可以设计如下算法：

1. 从左到右扫描所有位置 $i = 1, 2, \ldots, n$
2. 维护一个栈，用于存放尚未确定匹配的候选左括号位置
3. 对于每个位置 $i$：
   • 如果栈为空，则直接将 $i$ 入栈
   • 否则，询问区间 $[\text{栈顶}, i]$ 是否合法
     • 如果回答是 Yes，则栈顶位置的字符为 (，$i$ 位置的字符为 )，弹出栈顶
     • 如果回答是 No，则将 $i$ 入栈

正确性分析：

• 当询问 $[\text{栈顶}, i]$ 得到 Yes 时，根据性质 1，这两个位置一定匹配
• 由于我们从左到右扫描，栈中存放的都是可能作为左括号的位置
• 算法结束后，栈中剩余的 $2k$ 个位置构成了 $k$ 对连续的匹配括号

最终处理

设最终栈中有 $2t$ 个位置，这些位置一定形如：

其中前 $t$ 个位置是左括号，后 $t$ 个位置是右括号。

这是因为：

1. 这些位置无法与外部位置匹配
2. 它们必须内部匹配形成合法序列
3. 最自然的匹配方式就是前半部分为 (，后半部分为 )

复杂度分析

• 询问次数：最坏情况下每个位置最多询问一次（当栈不为空时），共 $n-1$ 次询问
• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

满足题目限制：

• 子任务 1：$n \le 16$，$k=150$ ✓
• 子任务 2：$n \le 100$，$k=10^4$ ✓
• 子任务 3：$n \le 1000$ ✓
• 子任务 4：$n \le 5\times 10^4$，$k=10^5$ ✓

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string ans;  // 存储最终答案
    ans.resize(n);
    stack<int> stk;  // 存储未匹配的候选左括号位置
    
    for (int i = 0; i < n; i++) {
        if (stk.empty()) {
            // 栈为空，当前位置可能是左括号
            stk.push(i);
            continue;
        }
        
        // 询问区间 [栈顶位置+1, 当前位置+1] 是否合法
        // 注意：题目中位置从1开始，代码中从0开始
        cout << "? " << stk.top() + 1 << ' ' << i + 1 << endl;
        string response;
        cin >> response;
        
        if (response == "Yes") {
            // 匹配成功：栈顶为'('，当前位置为')'
            ans[stk.top()] = '(';
            ans[i] = ')';
            stk.pop();  // 弹出已匹配的左括号
        } else {
            // 不匹配，当前位置可能是新的左括号
            stk.push(i);
        }
    }
    
    // 处理栈中剩余的位置
    // 栈中剩余 2t 个位置，前 t 个为'('，后 t 个为')'
    int t = stk.size() / 2;
    
    // 前 t 个位置设为 '('
    for (int i = 0; i < t; i++) {
        ans[stk.top()] = '(';
        stk.pop();
    }
    
    // 后 t 个位置设为 ')'
    for (int i = 0; i < t; i++) {
        ans[stk.top()] = ')';
        stk.pop();
    }
    
    // 输出最终答案
    cout << "! " << ans << endl;
    return 0;
}

算法总结

本算法巧妙利用了括号序列的区间合法性与匹配关系之间的等价性：

• 通过询问判断两个位置是否能形成合法的括号区间
• 利用栈结构自然地维护候选匹配
• 最终只需 $O(n)$ 次询问即可恢复整个序列

这是一种在线构造算法，基于栈的贪心匹配策略，充分利用了交互式问题的特性。