思路 想到了，但是木写对啊....代码 各种bug，写的乱死了....
输出最靠前的，比较折腾...
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
#define N 501000
#define LL __int64
int sa[N],height[N],rank[N];
int c[N],wa[N],wb[N];
int p[N];
int res[N];
char str[N];
LL sum[N];
LL l,r;
int bin[];
int minz[][N];
int sz[][N];
void build_sa(int s[],int n,int m)
{
int i,j,p,*x = wa,*y = wb;
for(i = ;i < m;i ++)
c[i] = ;
for(i = ;i < n;i ++)
c[x[i] = s[i]] ++;
for(i = ;i < m;i ++)
c[i] += c[i-];
for(i = n-;i >= ;i --)
sa[--c[x[i]]] = i;
for(j = ;j <= n;j <<= )
{
p = ;
for(i = n-j;i < n;i ++)
y[p++] = i;
for(i = ;i < n;i ++)
if(sa[i] >= j) y[p++] = sa[i] - j;
for(i = ;i < m;i ++)
c[i] = ;
for(i = ;i < n;i ++)
c[x[y[i]]] ++;
for(i = ;i < m;i ++)
c[i] += c[i-];
for(i = n-;i >= ;i --)
sa[--c[x[y[i]]]] = y[i];
swap(x,y);
p = ;x[sa[]] = ;
for(i = ;i < n;i ++)
x[sa[i]] = y[sa[i-]] == y[sa[i]]&&y[sa[i-]+j] == y[sa[i]+j]?p-:p++;
if(p >= n) break;
m = p;
}
}
void get_height(int s[],int n)
{
int i,j,k = ;
for(i = ;i <= n;i ++)
rank[sa[i]] = i;
for(i = ;i < n;i ++)
{
if(k) k--;
j = sa[rank[i]-];
while(s[i+k]==s[j+k]) k ++;
height[rank[i]] = k;
}
}
void init(int n)
{
int i,j;
for(i = ; i <= n; i ++)
{
minz[][i] = height[i];
sz[][i] = sa[i];
}
for(i = ; bin[i] <= n; i ++)
{
for(j = ; j + bin[i-] <= n; j ++)
{
minz[i][j] = min(minz[i-][j],minz[i-][j+bin[i-]]);
sz[i][j] = min(sz[i-][j],sz[i-][j+bin[i-]]);
}
}
}
int rmq(int s,int t)
{
s = rank[s];
t = rank[t];
if(s > t) swap(s,t);
s ++;
int k = log((t-s+)*1.0)/log(2.0);
return min(minz[k][s],minz[k][t-bin[k]+]);
}
int rmq1(int s,int t)
{
s = rank[s];
t = rank[t];
if(s > t) swap(s,t);
s ++;
int k = log((t-s+)*1.0)/log(2.0);
return min(sz[k][s],sz[k][t-bin[k]+]);
}
void find(LL k,int n)
{
int str,end,mid,i;
str = ;
end = n;
while(str < end)
{
mid = (str + end + )/;
if(sum[mid] > k)
end = mid - ;
else
str = mid;
}
i = end;
if(sum[end] > k)
{
l = sa[i];
r = sa[i]+k-;
}
else if(k == sum[end])
{
l = sa[i];
r = n-;
}
else
{
i ++;
l = sa[i];
r = sa[i] + k - sum[end] + height[i]-;
}
int len = r-l+;
if(i == n)
{
l ++;
r ++;
return ;
}
if(height[i+] < len)
{
l ++;
r ++;
return ;
}
str = i+;
end = n;
while(str < end)
{
mid = (str + end + )/;
if(rmq(sa[i],sa[mid]) < len)
end = mid - ;
else
str = mid;
}
if(rmq(sa[i],sa[end]) >= len)
{
l = min(l,(LL)rmq1(sa[i],sa[end]));
r = l+len-;
}
l ++;
r ++;
}
int main()
{
int i,len,n;
LL maxz;
for(i = ; i < ; i ++)
bin[i] = <<i;
LL v,k;
while(scanf("%s",str)!=EOF)
{
len = strlen(str);
for(i = ;i < len;i ++)
{
p[i] = str[i]-'a'+;
}
p[len] = ;
build_sa(p,len+,);
get_height(p,len);
init(len);
maxz = ;
for(i = ;i <= len;i ++)
{
maxz += len-sa[i]-height[i];
sum[i] = maxz;
}
scanf("%d",&n);
l = r = ;
for(i = ;i < n;i ++)
{
scanf("%I64d",&v);
// find(v,len);
// printf("%I64d %I64d\n",l,r);
k = (v^l^r)+; if(k > maxz)
{
l = r = ;
}
else
{
find(k,len);
}
printf("%I64d %I64d\n",l,r);
}
}
return ;
}