设置 (sqrt{n}) 个关键点，维护出关键点到每个右端点之间的答案以及Pam的左指针，每次暴力向左插入元素即可，为了去重，还需要记录一下Pam上每个节点在每个关键点为左端点插入到时候到最左边出现位置，总复杂度 (O(nsqrt{n}))。
/*program by mangoyang*/
#pragma GCC optimize("Ofast", "inline")
#include<bits/stdc++.h>
#define inf ((int)(1e9))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 100005;
char s[N];
namespace PAM{
int fa[N], ch[N][26], trans[N][26], len[N], size, tail, head;
inline void init(){
fa[0] = 1, len[1] = -1, tail = head = size = 1;
for(int i = 0; i < 26; i++) trans[0][i] = 1;
}
inline int newnode(int x){ return len[++size] = x, size; }
inline void pushback(int l, int r){
int c = s[r] - 'a', p = tail;
while(r - len[p] - 1 < l || s[r-len[p]-1] != s[r]) p = fa[p];
if(!ch[p][c]){
int np = newnode(len[p] + 2); fa[np] = ch[trans[p][c]][c];
memcpy(trans[np], trans[fa[np]], sizeof(trans[np]));
trans[np][s[r-len[fa[np]]]-'a'] = fa[np], ch[p][c] = np;
}
tail = ch[p][c];
if(len[tail] == r - l + 1) head = tail;
}
inline void pushfront(int l, int r){
int c = s[l] - 'a', p = head;
while(l + len[p] + 1 > r || s[l+len[p]+1] != s[l]) p = fa[p];
if(!ch[p][c]){
int np = newnode(len[p] + 2); fa[np] = ch[trans[p][c]][c];
memcpy(trans[np], trans[fa[np]], sizeof(trans[np]));
trans[np][s[l+len[fa[np]]]-'a'] = fa[np], ch[p][c] = np;
}
head = ch[p][c];
if(len[head] == r - l + 1) tail = head;
}
}
int bel[N], pos[700][N], pre[700][N], ans[700][N], ti[N], n, type, Q, Ans, tim;
int main(){
read(type), read(n), read(Q);
scanf("%s", s + 1);
int S = (int) min(n, 150), block = (n / S) + (n % S > 0);
PAM::init();
for(int i = 1; i <= n; i++) bel[i] = (i - 1) / S + 1;
for(int i = 1; i <= block; i++){
PAM::tail = PAM::head = 1, ++tim;
for(int j = (i - 1) * S + 1; j <= n; j++){
PAM::pushback((i - 1) * S + 1, j);
if(ti[PAM::tail] != tim) {
ti[PAM::tail] = tim, pos[i][PAM::tail] = j, ans[i][j]++;
}
ans[i][j] += ans[i][j-1], pre[i][j] = PAM::head;
}
}
while(Q--){
int l, r; read(l), read(r);
l ^= Ans * type, r ^= Ans * type, ++tim;
if(bel[l] == bel[r]){
PAM::head = PAM::tail = 1, Ans = 0;
for(int i = l; i <= r; i++){
PAM::pushback(l, i);
if(ti[PAM::tail] != tim) ti[PAM::tail] = tim, Ans++;
}
printf("%d
", Ans); continue;
}
int c = bel[l] + 1;
PAM::head = pre[c][r], Ans = ans[c][r];
for(int i = (c - 1) * S; i >= l; i--){
PAM::pushfront(i, r);
if(ti[PAM::head] != tim){
ti[PAM::head] = tim;
if(!pos[c][PAM::head] || pos[c][PAM::head] > r) Ans++;
}
}
printf("%d
", Ans);
}
return 0;
}