原题链接

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+7;
char str[MAXN];
struct node{
	int tot,mine;
}tree[MAXN<<2];
int sum[MAXN],cnt[MAXN];
node operator + (const node &x,const node &y){
	node ans;
	ans.tot=x.tot+y.tot;
	ans.mine=min(y.mine,x.mine+y.tot);
	return ans;
}
node query(int p,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return tree[p];
	int mid=(l+r)>>1;
	node ans={0,0};
	if(x<=mid)
		ans=query(p*2,l,mid,x,y)+ans;
	if(mid<y)
		ans=ans+query(p*2+1,mid+1,r,x,y);
	return ans;
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		if(str[l]=='(')
		{
			tree[p].tot--;
			tree[p].mine--;
		}
		if(str[l]==')'||str[l]=='?')
			tree[p].tot++;
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p]=tree[p*2]+tree[p*2+1];
	return ;
}
int main()
{
	int n;
	scanf("%d",&n);
	cin>>(str+1);
	for(int i(1);i<=n;++i)
	{
		sum[i]=sum[i-1]+(str[i]=='?');
		cnt[i]=cnt[i-1]+(str[i]=='(')-(str[i]==')');
	}
	build(1,1,n);
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		if((r-l+1)%2)
		{
			printf("No\n");
			continue;
		}
		int ls=l-1,rs=r,s;
		while(ls<=rs)
		{
			int mid=(ls+rs)>>1;
			if((sum[mid]-sum[l-1])-(sum[r]-sum[mid])+cnt[r]-cnt[l-1]<0)
				ls=mid+1;
			else
			{
				rs=mid-1;
				s=mid;
			}
		}
		node ans=query(1,1,n,s+1,r);
		if(ans.mine>=0&&s!=r)
			printf("Yes\n");
		else
			printf("No\n");
	}
}