题目链接

https://acm.bnu.edu.cn/v3/contest_show.php?cid=8506#problem/A

problem description

As we know, the NTU Final PK contest usually tends to be pretty hard. Many teams got frustrated when participating NTU Final PK contest. So I decide to make the first problem as “easy” as possible. But how to know how easy is a problem? To make our life easier, we just consider how easy is a string. Here, we introduce a sane definition of “easiness”. The easiness of a string is the maximum times of “easy” as a subsequence of it. For example, the easiness of “eeaseyaesasyy” is 2. Since “easyeasy” is a subsequence of it, but “easyeasyeasy” is too easy. How to calculate easiness seems to be very easy. So here is a string s consists of only ‘e’, ‘a’, ‘s’, and ‘y’. Please answer m queries. The i-th query is a interval [li , ri ], and please calculate the easiness of s[li ..ri ].

Input

The first line contains a string s. The second line contains an integer m. Each of following m lines contains two integers li , ri . • 1 ≤ |s| ≤ 105 • 1 ≤ m ≤ 105 • 1 ≤ li ≤ ri ≤ |s| • s consists of only ‘e’, ‘a’, ‘s’, and ‘y’

Output

For each query, please output the easiness of that substring in one line.

Examples

standard input

easy

3

1 4

2 4

1 3

eeaseyaesasyy

4

1 13

2 12

2 10

3 11

standard output

1

0

0

2

2

1

0

题意：给了一个只含有'e'  'a'  's'  'y'  的字符串然后m次询问，每次询问输入l r 求这个区间含有多少个“easy”序列（每个“easy” 字符之间不需要连在一起）；

思路：用倍增的思路来做，每个点只记录最靠近它的在它左边的那个字母的位置，比如'e'记录前面的'y','a'记录前面的'e','s'记录前面的'a'，'y'记录前面的's' 并注意记录距离i最近（左边的y）的y的位置（用p[i]存储）  定义anc[i][j] 表示第i个字符前的第（1<<j）个字符的位置，这个可以用倍增做到 anc[i][j]=anc[anc[i][j-1]][j-1]，  查询时，先找到v=p[r] 然后找左边有效字符个数，最后除以4 就是结果；

代码如下：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <cstring>

#include <queue>

using namespace std;

typedef long long LL;

char s[];

int a[],p[];

int anc[][];

int mp[];

int main()

{

    int m;

    while(scanf("%s",s+)!=EOF)

    {

        int len=strlen(s+);

        for(int i=;i<=len;i++)

        {

            if(s[i]=='e') a[i]=;

            else if(s[i]=='a') a[i]=;

            else if(s[i]=='s') a[i]=;

            else a[i]=;

        }

        memset(mp,,sizeof(mp));

        for(int i=;i<=len;i++)

        {

            int pre=(a[i]-+)%;

            anc[i][]=mp[pre];

            mp[a[i]]=i;

            p[i]=mp[];

        }

        for(int i=;i<=;i++)

        {

            for(int j=;j<=len;j++)

            {

                anc[j][i]=anc[anc[j][i-]][i-];

            }

        }

        scanf("%d",&m);

        while(m--)

        {

            int l,r;

            int sum=;

            scanf("%d%d",&l,&r);

            int v=p[r];

            for(int i=;i>=;i--)

            {

                if(anc[v][i]>=l){

                    sum+=(<<i);

                    v=anc[v][i];

                }

            }

            printf("%d\n",sum/);

        }

    }

    return ;

}