【牛客】国庆集训派对day1 J Princess Principal 栈模拟括号匹配

原题地址

阿尔比恩王国（the Albion Kingdom）潜伏着一群代号“白鸽队（Team White Pigeon）”的间谍。在没有任务的时候，她们会进行各种各样的训练，比如快速判断一个文档有没有语法错误，这有助于她们鉴别写文档的人受教育程度。
这次用于训练的是一个含有n个括号的文档。括号一共有m种，每种括号都有左括号和右括号两种形式。我们定义用如下的方式定义一个合法的文档:
1.一个空的字符串是一个合法的文档。
2.如果A,B都是合法的文档，那么AB也是合法的文档。
3.如果S是合法的文档，那么aSb也是合法的文档，其中a,b是同一种括号，并且a是左括号，b是右括号。
现在给出q个询问，每次询问只考虑文档第l至r个字符的情况下，文档是不是合法的。

输入描述:

第一行两个整数n,m,q(1 ≤ n,m,q ≤ 106)。
第二行有n个空格隔开的整数x，第i个整数xi(0 ≤ xi < m*2)代表文档中的第i个字符是第⌊x2⌋⌊x2⌋种括号。另外，如果xi是偶数，它代表一个左括号，否则它代表一个右括号。
接下来q行，每行两个空格隔开的整数l,r(1 ≤ l ≤ r ≤ n)，代表询问第l至r个字符构成的字符串是否是一个合法的文档。

输出描述:

输出共q行，如果询问的字符串是一个合法的文档，输出"Yes",否则输出"No"。

示例1

输入

6 4 3
0 2 3 1 4 7
1 4
1 5
5 6

输出

Yes
No
No

括号匹配，通过栈来模拟括号依次进入，匹配成功的消除，并记录当前栈顶层元素，这样在后面的查询中只要判断两个字符位置所记录的顶层元素是否相同就可以判断这个区间的括号完全匹配。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
#define maxn 1000005

int a[maxn],l[maxn];
stack<int >s;

int main()
{
	int n,m,q,i,x,y;
	closeio;
	cin>>n>>m>>q;
	while(!s.empty())
		s.pop();
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=n;i++)
	{
		if(s.empty()||!(a[i]%2))
			s.push(i);
		else if(a[s.top()]+1==a[i])
			s.pop();
		else
			s.push(i);
		if(s.empty())
			l[i]=0;
		else
			l[i]=s.top();	
	}
	while(q--)
	{
		cin>>x>>y;
		if(l[x-1]==l[y])
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
	}
	return 0;
}