Invertible Bracket Sequences

看到这种类似的括号匹配的题目，一定要想到卡特兰数的证明过程呀（将(看成\(1\)，)看成\(-1\)，于是不难得出充分条件，虽然这道题目并不是直接这么给的，但是我看没人证明）

剩下的看官方题解就好了，之所以可以删掉官方题解所说的\(x\)，是因为接下来如果\(x\)是\(r_1\)的答案候选项的话，由于\(r_1>r\)，那么肯定会去判断是否有\(x≥bal_r-x\)，而这显然不用判断，肯定不成立，所以可以删除\(x\)

我的赛时做法大致一样，但是我是先二分找到条件一的边界，再利用“蒲公英”这道题目的二分思路去找有多少个数满足条件二

代码见下

int getnum(int x,int l,int r)
{
	if(loc[x][loc[x].size()-1]<l||loc[x][0]>r) return 0;//这个边界条件判断很重要
	int L,R,mid,L1,R1;
	L=0,R=loc[x].size()-1;
	while(L<=R)
	{
		mid=L+R>>1;
		if(loc[x][mid]>=l)
		{
			L1=mid;
			R=mid-1;
		}
		else L=mid+1;
	}
	L=0,R=loc[x].size()-1;
	while(L<=R)
	{
		mid=L+R>>1;
		if(loc[x][mid]<=r)
		{
			R1=mid;
			L=mid+1;
		}
		else R=mid-1;
	}
	return R1-L1+1;
}