思路：第一个做法就是：每读入起始位置i和结束位置j，就从这位置i到位置j计算，可是TLE了，后面我想想要是我输入一个最长的字符串，且以最大次数计算开始位置1到结束位置100000，那么这计算量是很大的而且还是重复的。
第二种就是：我先把这个字符串每个位置i到位置j的哈希值都计算出来，然后储存起来，可是字符串最大长度是100000，所以这个n*n的复杂度，当然还是TLE了。
最后还是想到了线段树，而且这题还是裸的线段树，然后写出来了，可是我交了好多次都是RE！很无奈，然后看到该题的讨论版里面提到，如果起始位置超出范围，那么输出上一次的结果就可以了。然后我就加上了这个判断，结果AC了。可是题目给的数据范围是不会超出范围的啊！！是出题人的锅。当然我看到了有些大神过的还是很快的，所以原因还是有自己的一部分，不够严谨。
AC代码：
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 100005;
const int MAX_NN = MAX_N*4;
const int MOD = 9973;
int value[MAX_NN], left[MAX_NN], right[MAX_NN],n,a,b,len;
char word[MAX_N];
void build(int root, int l, int r)
{
left[root] = l;
right[root] = r;
if(l == r) value[root] = word[l]-28;
else
{
int mid = (l+r)/2;
build(root*2, l, mid);
build(root*2+1, mid+1, r);
value[root] = (value[root*2] * value[root*2+1] + MOD)%MOD;
}
}
int query(int root, int l, int r)
{
if(left[root] == l && right[root] == r) return value[root];
else
{
int mid = (left[root]+right[root])/2;
if(r <= mid) return query(root*2, l, r);
else if(l > mid) return query(root*2+1, l, r);
else return (query(root*2, l,mid) * query(root*2+1, mid+1, r) + MOD) %MOD;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int last = 0;
while(~scanf("%d", &n))
{
scanf("%s", word);
len = strlen(word);
build(1, 0, len-1);
if(n == 0) puts("");
while(n--)
{
scanf("%d %d", &a, &b);
if(a > b) swap(a,b);
if( a < 1 || b > len) printf("%d
", last); //之前老是RE，加上这个就AC了
else printf("%d
", last = query(1,a-1,b-1));
}
}
return 0;
}