2016年湖南省第12回大学生コンピュータプログラム設計コンテスト:G-parathesis

2523 ワード

データ構造---RMQ プレフィックスと

テーマリンク:転送ゲート
Description
Bobo has a balanced parenthesis sequence P=p
1 p
2…p
n of length n and q questions.
The i-th question is whether P remans balanced after p
ai and p
bi. swapped.Note that questions are individual so that they have no affect on others.
Parthesis sequence S is balanced if and only if:
1.
S is empty;
2.
or there exists
balanced parenthesis sequence A、B such that S=AB;
3.
or there exists
balanced parenthesis sequence S'such that S=(S')
Input
The input contains at most 30 sets.For each set:
The first line contains two integers n,q(2≦n≦10
5,1≦q≦10
5)
The second line contains n characters p
1 p
2…p
n.
The i-th of the last q lines contains 2 integers a
i,b
i (1≦a
i,b
i≦n,a
イ≠b
i)
Output
For each question,output"
Yes「if P remans balanced,or」
No"others wise.
Sample Input

4 2
(())
1 3
2 3
2 1
()
1 2

Sample Output

No
Yes
No

問題解決の考え方:プレフィックスと+RMQ
aで'('+1,')'-1を格納する.
マッチングを満たすと、任意のa[i]=0があります.
二つの位置の括弧を交換します.「(」と「()」と「)」、「)」と「(」はシーケンスのマッチングに影響しません.
‘(’と‘)’の場合のみ、a[i]からa[J-1]までの最小値が2以下であると、シーケンスが一致しない

#include   
#include   
#include   
#include   
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;  
typedef unsigned long long ll;
const int N = 100100;
const int M = 20;
const int mod = 1e9+7;
const int INF = 0x3fffffff;
int dp[N][M];
int a[N];

void RMQ( int  n )
{
	for( int i = 1 ; i <= n ; ++i ) dp[i][0] = a[i];
	for( int j = 1 ; (1<> b;
		int sz = b.size();
		a[0] = 0;
		for( int i = 1 ; i <= sz ; ++i ){
			if( b[i-1] == '(' ) a[i] = a[i]+a[i-1]+1;
			else a[i] = a[i]+a[i-1]-1;
		}
		RMQ( sz );
		for( int i = 0 ; i < q ; ++i ){
			int flag = 0;
			scanf("%d%d",&t1,&t2);
			if( t1 > t2 ) swap( t1 , t2 );
			if( b[t1-1] == '(' && b[t2-1] == ')' ){
				int t = solve(t1,t2-1);
				if( t<2 ) flag = 1;
			}
			if( flag ) printf("No
");
			else printf("Yes
");
		}
	}
	return 0;
}

洛谷P 986[USACO 10 MAR]偉大な乳牛が集まるグリアCow Gat…