博客

题目描述

小花梨有一个长度为n且只包含小写字母的字符串。现在对其进行q次询问。
每次询问字符串的一段区间[l,r]，从[l,r]区间内的所有子串中最多可以选出多少个字符串，使得选出来的这些字符串存在一种排列方式满足相邻的两个字符串a,b的最长公共后缀长度大于等于min(strlen(a),strlen(b))-1。

输入

第一行输入两个正整数n和q，分别表示字符串长度和询问次数。
第二行为长度为n的字符串。接下来q行，每行两个正整数l,r表示询问的区间。(1≤n≤10000,1≤q≤10000,1≤l≤r≤n)

输出

输出q行，第i行输出第i次询问的答案

样例输入

3 3
abc
1 1
1 2
1 3

样例输出

1
3
6

提示

[1,1]内有1个子串：a，存在排列a满足要求，长度为1
[1,2]内有3个子串：a,b,ab，存在排列a,ab,b满足要求，长度为3
[1,3]内有6个子串：a,b,c,ab,bc,abc，存在排列ab,b,c,bc,abc,a满足要求，长度为6

题目只是简单的考察字符串的子串有多少种

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int main()
{
    int n,q;
    char x[10010];
    scanf("%d %d",&n,&q);
    getchar();
    scanf("%s",x);
    int a,b;
    for(int i=0;i<q;i++)
    {
        scanf("%d %d",&a,&b);
        printf("%d\n",(b-a+1)*(b-a+2)/2);
    }
    return 0;
}