蒟蒻第一篇题解。

自己不会做，看了官方题解才做出来的。

题义简述

• 这是一道交互题。
• 有一个长度为 $n$ 的括号序列，$n$ 为偶数，其中一半是左括号，一半是右括号。
• 你能进行 $Q$ 次询问，每次询问给出一个 $l$ 和 $r$，询问 $l$ 到 $r$ 间的括号序列是否合法。
• 目标是求出这个括号序列。
• $n\leqslant 10^{5}$，$n-1\leqslant Q$。

解题方法

拿到这样一道题，没什么头绪，于是可以反过来思考。

对于一个括号序列，我们可以用 $n-1$ 个什么来区别它和其他括号序列呢？

结合本题要求线性（或稍劣）的时间，我们想到了线性的数据结构。

再结合括号序列，我们想到了用栈判定括号序列的合法性。

那么，我们就考虑用栈来重现这个括号序列。

如果不会用栈判定括号序列的合法性，请移步至表达式括号匹配。

从左到右依次入栈，入栈后，当栈内至少有两个元素时，询问栈顶的两个是否合法。

合法即确定两个位置分别为(和)，弹出这对括号。

如果最后栈不为空（整个序列不合法），则左边一半为)，右边一半为(。

考虑这样做的正确性。

如果栈顶是(和)，那么它们其中的所有括号都被弹走了，也就是说，这是一对括号包含一个合法的括号序列（或者这是一对相邻的括号），显然合法。

如果栈顶不是(和)，显然不合法。

如果最后栈不为空，因为左括号和右括号一样多，而弹出的括号都是成对的，所以最后剩下的左括号和右括号也一样多，又因为它们都还在栈中（没有匹配的括号），则只能是左边一半为右括号，右边一半为左括号了。

除了第一个元素以外，每个元素入栈时至多询问 $1$ 次，所以至多只会询问 $n-1$ 次。

时间复杂度：$\Theta(n)$。

参考代码

# include <bits/stdc++.h>
using namespace std;
int stk[100010];
char s[100010];
int main()
{
	int n,tp=0;
	scanf("%d%*d",&n);
	for(int i=1;i<=n;i++)
		if(!tp) stk[++tp]=i;
		else
		{
			int t;
			printf("? %d %d\n",stk[tp],i);fflush(stdout);
			scanf("%d",&t);
			if(t) s[stk[tp--]]='(',s[i]=')';
			else stk[++tp]=i;
		}
	for(int i=1;i<=tp/2;i++) s[stk[i]]=')';
	for(int i=tp/2+1;i<=tp;i++) s[stk[i]]='(';
	printf("! %s\n",s+1);fflush(stdout);
	return 0;
}