题目分析

本题要求我们通过与系统的交互，找出一个由 $N$ 个字符组成的密码序列，其中恰好有 $N/2$ 个左括号 ( 和 $N/2$ 个右括号 )。我们可以向系统询问任意区间 $[a,b]$ 内的括号序列是否为合法的括号序列，最多可以询问 $Q$ 次。

关键观察

$1$. 括号匹配的本质：

在一个合法的括号序列中，每个左括号必须与一个右括号匹配。当我们从左到右扫描时，需要保证右括号的数量不超过左括号的数量，且最终左右括号数量相等。

$2$. 栈的性质：

括号匹配问题通常可以用栈来解决。扫描序列时，遇到左括号入栈，遇到右括号则与栈顶的左括号匹配。如果最终栈为空，说明括号完全匹配。

$3$. 本题的特殊性：

序列长度 $N$ 为偶数，且恰好有 $N/2$ 个左括号和 $N/2$ 个右括号。这意味着如果序列是合法的括号序列，那么它必须完全匹配。

算法思路

$1$. 核心思想：

使用一个栈来模拟括号匹配过程。我们不知道每个位置具体是左括号还是右括号，但可以通过询问相邻两个位置的子序列是否为合法括号序列来判断它们的匹配关系。

$2$. 匹配过程：

从左到右遍历每个位置 $i$（从 $1$ 到 $N$）

将当前位置的索引 $i$ 压入栈中

如果栈中至少有两个元素，询问栈顶两个位置（记为 $f[top-1]$ 和 $f[top]$）组成的长度为 $2$ 的子序列是否合法

如果返回结果为 $1$（合法），说明这两个位置的括号能够匹配，那么 $f[top-1]$ 位置一定是左括号 (，$f[top]$ 位置一定是右括号 )

将这两个位置从栈中弹出（因为它们已经匹配成功）

$3$. 最终处理：

遍历结束后，栈中剩下的位置是无法通过两两匹配确定的括号。由于序列中左括号和右括号数量各占一半，且我们已经确定了一些匹配的括号对，可以推断出：

栈中前半部分的剩余位置是右括号 )

栈中后半部分的剩余位置是左括号 (

算法步骤

$1$. 初始化：

读取 $N$ 和 $Q$（虽然 $Q$ 在本算法中不需要使用），初始化空栈。

$2$. 遍历匹配：

对于 $i = 1$ 到 $N$：

将 $i$ 压入栈

如果栈中元素 $\ge 2$，询问栈顶两个位置组成的子序列是否合法

如果合法，则这两个位置分别标记为 ( 和 )，并将它们从栈中弹出

$3$. 处理剩余位置：

设栈中剩余 $m$ 个位置：

前 $m/2$ 个位置标记为 )

后 $m/2$ 个位置标记为 (

$4$. 输出答案：

输出完整的括号序列。

时间复杂度

• 时间复杂度：$O(N)$，每个位置最多入栈一次、出栈一次

• 询问次数：最多 $N/2$ 次询问，因为每成功匹配一对括号需要一次询问

正确性证明

$1$. 两位置合法的条件：

对于两个相邻的位置 $i$ 和 $j$（$j = i+1$），子序列 $[i,j]$ 合法的充要条件是：

• 位置 $i$ 是左括号 (

• 位置 $j$ 是右括号 ) 因为长度为 $2$ 的括号序列只有 () 是合法的。

$2$. 栈中剩余位置的处理：

设最终栈中有 $m$ 个位置。由于序列中左括号和右括号各占一半，且我们已经匹配了一些括号对，所以栈中剩余的括号也必然满足左括号和右括号数量相等。又因为栈中位置是按照遍历顺序入栈的，所以前半部分对应的是需要右括号来匹配的位置，后半部分对应的是需要左括号来匹配的位置。

$3$. 询问次数保证：

算法最多进行 $N/2$ 次询问，符合题目要求（$Q \ge N/2$ 在本题中保证成立）。

代码实现

#include <cstdio>
#include <iostream>
using namespace std;

int n, f[100010], top, i, s; // f数组作为栈
char ans[100010]; // 存储答案序列

int main() {
    // 读取N和Q（Q在算法中不需要使用）
    cin >> n >> i;
    
    // 遍历每个位置
    for (i = 1; i <= n; i++) {
        // 将当前位置索引压入栈
        top++;
        f[top] = i;
        
        // 如果栈中至少有两个元素，检查栈顶两个位置是否能匹配
        if (top > 1) {
            // 询问栈顶两个位置组成的长度为2的子序列是否合法
            cout << "? " << f[top - 1] << " " << f[top] << endl;
            cin >> s;
            
            // 如果合法，则这两个位置是匹配的括号对
            if (s == 1) {
                ans[f[top - 1]] = '('; // 前一个位置是左括号
                ans[f[top]] = ')';     // 当前位置是右括号
                top = top - 2;         // 弹出这两个已匹配的位置
            }
        }
    }
    
    // 处理栈中剩余的位置
    // 栈中前半部分是右括号，后半部分是左括号
    for (i = 1; i * 2 <= top; i++)
        ans[f[i]] = ')';
    
    for (; i <= top; i++)
        ans[f[i]] = '(';
    
    // 输出最终答案
    cout << "! " << ans + 1 << endl;
    
    return 0;
}