BZPRO
#4964. 加长的咒语
内存限制:256 MiB
时间限制:20 Sec
提交
提交记录
讨论
题目描述
VictBr发现是他上一次念的咒语是假的!咒语是由且仅由'('和')'构成的一段连续的字符串,一个咒语合法当且仅
当这个咒语的任意一个前缀都满足'('的个数不少于')'的个数,且整个串的'('和')'的个数相等。VictBr的膜法书
上只有一长度为n的仅由'('和')'构成的字符串。长者告诉他世界上所有咒语都在这本膜法书中。在长者的教诲下
,Victbr学会了假的念咒术,然后他向世界上最强的OIer们发出挑战,在欢声笑语中打出GG。为了战胜他们,Vict
br写出了更长的膜法书,并再次向最强的OIer们发出挑战。你能回答出他的问题么?具体的问题是:每次询问膜法
书中的一个片段,求这个片段中最长的咒语的长度。
输入格式
第一行两个正整数n,m,分别表示字符串长度和询问个数。
接下来一行一个长度为n的仅由'('和')'组成的字符串。
接下来m行,每行两个整数x,y,表示询问的片段的左右端点。下标从1开始。
满足1≤n,m≤4×10^5
输出格式
对于每个询问,输出最长的咒语的长度。
样例
样例输入
5 5
(()()
2 4
1 5
1 4
1 3
1 1
样例输出
2
4
2
2
0
数据范围与提示