CodeForces - 368C Sereja and Algorithm （找规律&模拟）

Submit Status

Description

Sereja loves all sorts of algorithms. He has recently come up with a new algorithm, which receives a string as an input. Let's represent the input string of the algorithm as q = q₁q₂... q_k. The algorithm consists of two steps:

1. Find any continuous subsequence (substring) of three characters of string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2.
2. Rearrange the letters of the found subsequence randomly and go to step 1.

Sereja thinks that the algorithm works correctly on string q if there is a non-zero probability that the algorithm will be terminated. But if the algorithm anyway will work for infinitely long on a string, then we consider the algorithm to work incorrectly on this string.

Sereja wants to test his algorithm. For that, he has string s = s₁s₂... s_n, consisting of n characters. The boy conducts a series of m tests. As the i-th test, he sends substring s_lis_li + 1... s_ri(1 ≤ l_i ≤ r_i ≤ n) to the algorithm input. Unfortunately, the implementation of his algorithm works too long, so Sereja asked you to help. For each test (l_i, r_i) determine if the algorithm works correctly on this test or not.

Input

The first line contains non-empty string s, its length (n) doesn't exceed 10⁵. It is guaranteed that string s only contains characters: 'x', 'y', 'z'.

The second line contains integer m(1 ≤ m ≤ 10⁵) — the number of tests. Next m lines contain the tests. The i-th line contains a pair of integers l_i, r_i(1 ≤ l_i ≤ r_i ≤ n).

Output

For each test, print "YES" (without the quotes) if the algorithm works correctly on the corresponding test and "NO" (without the quotes) otherwise.

Sample Input

Hint

In the first example, in test one and two the algorithm will always be terminated in one step. In the fourth test you can get string "xzyx" on which the algorithm will terminate. In all other tests the algorithm doesn't work correctly.

//题意：先输入一个字符串，再输入一个n（表示询问次数），接下来n行每行输入两个数（l，r），表示子字符串的左端点和右端点，对于每个子字符串判断它是否是合格的。

对于给定的一个字符串，每次对这个字符串进行重新排列，如果每次都能找出一个连续子串（包含三个字符）s，并且这个s不是"zyx", "xzy", "yxz",那么这个字符串是不合格的（因为会一直在重排、查找），则输出NO，否则，输出YES。

//思路：

用一个二维数组dp来存放x,y,z的个数，具体为：

dp[i][1]表示前i位中x字符的个数；

dp[i][2]表示前i位中y字符的个数;

dp[i][3]表示前i位中z字符的个数；

接着运用找到的规律就可以解题了：

1、当字符数少于3时，肯定是合格的字符串；

2、当字符数大于3时，判断三种字符中最多的个数与最少的个数的差是否小于2，是的话就是个合格的，否则就不是合格的字符串。

知道这些，这个题就可以解决了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
#define IN __int64
#define N 100010
#define M 1000000007
using namespace std;
char s[N];
int dp[N][4];
int a[5];
int main()
{
	int t,n,i,j,k,m;
	while(scanf("%s",s)!=EOF)
	{
		int len=strlen(s);
		dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;
		for(i=0;i<len;i++)
		{
			if(s[i]=='x')
			{
				dp[i+1][1]=dp[i][1]+1;
				dp[i+1][2]=dp[i][2];
				dp[i+1][3]=dp[i][3];
			}
			else if(s[i]=='y')
			{
				dp[i+1][1]=dp[i][1];
				dp[i+1][2]=dp[i][2]+1;
				dp[i+1][3]=dp[i][3];
			}
			else
			{
				dp[i+1][1]=dp[i][1];
				dp[i+1][2]=dp[i][2];
				dp[i+1][3]=dp[i][3]+1;
			}
		}
		scanf("%d",&n);
		while(n--)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			l--;
			a[1]=dp[r][1]-dp[l][1];
			a[2]=dp[r][2]-dp[l][2];
			a[3]=dp[r][3]-dp[l][3];
			sort(a+1,a+4);
			int s=a[1]+a[2]+a[3];
			if(s<3)
				printf("YES\n");
			else
			{
				if(a[3]-a[1]>=2)
					printf("NO\n");
				else
					printf("YES\n");
			}
		}
	}
	return 0;
}