小花梨的字符串--美登杯

Description
小花梨有一个长度为n且只包含小写字母的字符串。现在对其进行q次询问。
每次询问字符串的一段区间[l，r]，从[l，r]区间内的所有子串中最多可以选出多少个字符串，
使得选出来的这些字符串存在一种排列方式满足相邻的两个字符串a,b的最长公共后缀长度
大于等于min( strlen(a),strlen(b) )-1。
Input
第一行输入两个正整数n和q，分别表示字符串长度和询问次数。
第二行为长度为n的字符串。接下来q行，每行两个正整数l，r表示询问的区间。
(1 ≤ n ≤ 10000,1 ≤ q ≤ 10000,1 ≤ l ≤ r ≤ n)
Output
输出q行，第 i 行输出第 i 次询问的答案

Note
[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

分析

这个题用一个等差数列前n项和公式就可以了，对应每个区间的字符串，其所有子串都能用到，组成一个序列满足题目要求。具体原理我也不知道，只是在做题的时候看了上面的note，发现了这个规律，一交，A了。。。

代码

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll cal(ll l,ll r)
{ll len=r-l+1;return len*(1+len)/2;
}
int main()
{int n,q;char s[10005];scanf("%d%d",&n,&q);scanf("%s",s);for(int i=0;i<q;i++){ll l,r;scanf("%lld%lld",&l,&r);ll ans=cal(l,r);printf("%lld\n",ans);}return 0;
}