Carpenters' Language(类似括号匹配)

Carpenters' Language

时间限制: 1 Sec 内存限制: 128 MB

题目描述

International Carpenters Professionals Company (ICPC) is a top construction company with a lot of expert carpenters. What makes ICPC a top company is their original language.

The syntax of the language is simply given in CFG as follows:

S -> SS | (S) | )S( | ε
In other words, a right parenthesis can be closed by a left parenthesis and a left parenthesis can be closed by a right parenthesis in this language.

Alex, a grad student mastering linguistics, decided to study ICPC's language. As a first step of the study, he needs to judge whether a text is well-formed in the language or not. Then, he asked you, a great programmer, to write a program for the judgement.

Alex's request is as follows: You have an empty string S in the beginning, and construct longer string by inserting a sequence of '(' or ')' into the string. You will receive q queries, each of which consists of three elements (p,c,n), where p is the position to insert, n is the number of characters to insert and c is either '(' or ')', the character to insert. For each query, your program should insert c repeated by n times into the p-th position of S from the beginning. Also it should output, after performing each insert operation, "Yes" if S is in the language and "No" if S is not in the language.

Please help Alex to support his study, otherwise he will fail to graduate the college.

输入

The first line contains one integer q (1≤q≤105) indicating the number of queries, follows q lines of three elements, pi, ci, ni, separated by a single space (1≤i≤q, ci='('or')', 0≤pi≤ length of S before i-th query, 1≤n≤220). It is guaranteed that all the queries in the input are valid.

输出

For each query, output "Yes" if S is in the language and "No" if S is not in the language.

样例输入

复制样例数据

样例输出

No
No
Yes

气人哦，一开始用了int交了已发，错了，然后我用树状数组开了半天的空间。。。虽然树状数组过了，但是第一次改成long long也对的。！！！

题意就是是否可以匹配。

解法:怎么匹配都行,可以'('匹配')',也可以')'匹配'('，好像你加括号进去也就这两种可能，那么只要知道左右括号是否相等就行了。

法一：

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL num1, num2;
int t;
LL p, num;
char ch;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &t);
	while(t--){
		scanf("%lld %c %lld", &p, &ch, &num);
		if(ch == '(') num1 += num;
		else num2 += num;
		if(num1 == num2) printf("Yes\n");
		else printf("No\n");
	}

	return 0;
}
/**/

法二：树状数组

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int t;
LL q;
int n;
char ch;
const LL maxx = ((1LL << 20) * 100001);
map<LL, LL> c;


LL lowbit(LL x){
	return x & (-x);
}

void add(LL x, int num){
	//if(!x) c[x] += num, x++;
	while(x <= maxx){
		c[x] += num;
		x += lowbit(x);
	}
}

LL sum(LL x){
	LL t = 0;
	while(x){
		t += c[x];
		x -= lowbit(x);
	}
	return t;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &t);
	while(t--){
		scanf("%lld %c %d", &q, &ch, &n);
		if(ch == '(') add(q + 1, n);
		else add(q + 1, -n);
		LL t = sum(q + 105);
		if(t == 0){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}

	return 0;
}
/**/