题意：
给出 (n) 个字符串，(q) 组查询，每次查询第 (L) 到第 (R) 个字符串中有多少个不同的前缀。强制在线。
数据范围：(1≤N≤100000,1≤Q≤100000)，字符串总长最大为 (1e5)。
分析：
用字典树给每种前缀进行编号，最多有 (1e5) 个前缀。问题即转化为求区间内不同的数的个数，用 (last) 数组记录每种前缀最后一次查询的位置（字符串的编号），每次插入如果不是第一次出现就在上次出现位置上 (-1)，然后在此次出现的位置上 (+1)。
具体思路见：SPOJ - DQUERY
但注意的是本题一个位置要插入多个值。
代码：
#include <bits/stdc++.h>//给每一个前缀标号，记录每个前缀出现的次数
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+5;
char ss[N];
int cnt,cot,tol;
ll n;
int root[N],num[N],trie[N][27],tag[N],last[N];
struct node
{
ll val;
int lson,rson;
}tree[N*40];
void add(int len)
{
int rt=0;
for(int i=1;i<=len;i++)
{
int t=ss[i]-'a';
if(!trie[rt][t]) trie[rt][t]=++cot;
rt=trie[rt][t];
if(!tag[rt]) tag[rt]=++tol;
num[i]=tag[rt];//记录在该字符串中出现的前缀编号
}
}
int build(int l,int r)
{
int t=++cnt;
if(l==r)
{
tree[t].val=0;
return t;
}
int mid=(l+r)>>1;
tree[t].lson=build(l,mid);
tree[t].rson=build(mid+1,r);
tree[t].val=tree[tree[t].lson].val+tree[tree[t].rson].val;
return t;
}
int update(int l,int r,int pos,int val,int rt)
{
int t=++cnt;
tree[t]=tree[rt];
if(l==r)
{
tree[t].val+=val;
return t;
}
int mid=(l+r)>>1;
if(pos<=mid)
tree[t].lson=update(l,mid,pos,val,tree[rt].lson);
else
tree[t].rson=update(mid+1,r,pos,val,tree[rt].rson);
tree[t].val=tree[tree[t].lson].val+tree[tree[t].rson].val;
return t;
}
ll query(int l,int r,ll L,ll R,int rt)
{
if(L<=l&&r<=R)
return tree[rt].val;
int mid=(l+r)>>1;
ll ans=0;
if(L<=mid)
ans+=query(l,mid,L,R,tree[rt].lson);
if(R>mid)
ans+=query(mid+1,r,L,R,tree[rt].rson);
return ans;
}
int main()
{
while(scanf("%lld",&n)!=EOF)//竟然WA在了多组输入上
{
int q;
cnt=0,cot=0,tol=0;
root[0]=build(1,n);
memset(trie,0,sizeof(trie));
memset(last,0,sizeof(last));
memset(tag,0,sizeof(tag));
for(int i=1;i<=n;i++)
{
scanf("%s",ss+1);
int len=strlen(ss+1);
add(len);
for(int j=1;j<=len;j++)
{
if(last[num[j]]==0)
{
if(j==1)
root[i]=update(1,n,i,1,root[i-1]);
else
root[i]=update(1,n,i,1,root[i]);
}
else
{
if(j==1)
root[i]=update(1,n,last[num[j]],-1,root[i-1]);
else
root[i]=update(1,n,last[num[j]],-1,root[i]);
root[i]=update(1,n,i,1,root[i]);
}
last[num[j]]=i;
}
}
scanf("%d",&q);
ll ans=0,l,r,tl,tr;
while(q--)
{
scanf("%lld%lld",&tl,&tr);
ll t1=(ans+tl)%n;
ll t2=(ans+tr)%n;
l=min(t1,t2)+1;
r=max(t1,t2)+1;
ans=query(1,n,l,r,root[r]);
printf("%lld
",ans);
}
}
return 0;
}