代码

//#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<assert.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1LL<<62;
const int mod=1e9+7;

const int N=2e6+100;

int qpow(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;y>>=1;
	}
	return ans;
}

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

namespace io {
	const int L=(1<<21)+1;
	char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline char getc() {
		return gc();
	}
	inline void flush() {
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline void putc(char x) { *oS++=x; if (oS==oT) flush(); }
	template<class I> inline void gi(I&x) {
		for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
		for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
	}
	template<class I> inline void print(I x) {
		if (!x) putc('0');
		if (x<0) putc('-'),x=-x;
		while (x) st[++tp]=x%10+'0',x/=10;
		while (tp) putc(st[tp--]);
	}
	inline void gs(char*s, int&l) {
		for (c=gc();c<'a'||c>'z';c=gc());
		for (l=0;c<='z'&&c>='a';c=gc()) s[l++]=c;
		s[l]=0;
	}
	inline void ps(const char*s) { for (int i=0,n=strlen(s);i<n;i++) putc(s[i]); }
	struct IOFLUSHER{ ~IOFLUSHER() { flush(); } } _ioflusher_;
};
using io::getc;
using io::putc;
using io::gi;
using io::gs;
using io::ps;
using io::print;

const int alpha=27;
int x[N],y[N],v[N*2];
int bug[N],sa[N],rk[N],h[20][N],Log[N];
int lcp(int a,int b) {
	if ((a=rk[a])>(b=rk[b])) swap(a,b);
	int s=Log[b-a];
	return min(h[s][a],h[s][b-(1<<s)]);
}
void build(char *str,int n) {
	int i,j,m=alpha,p;
	for (i=1;i<=n;i++) bug[x[i]=str[i]-'a'+1]++;
	for (i=2;i<=m;i++) bug[i]+=bug[i-1];
	for (i=1;i<=n;i++) sa[bug[x[i]]--]=i;
	for (j=1,p=0;p<n;m=p,j<<=1) {
		for (i=n-j+1,p=0;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
		for (i=1;i<=m;i++) bug[i]=0;
		for (i=1;i<=n;i++) bug[v[i]=x[i]]++;
		for (i=2;i<=m;i++) bug[i]+=bug[i-1];
		for (i=n;i;i--) sa[bug[x[y[i]]]--]=y[i];
		for (i=1,p=0;i<=n;i++) x[sa[i]]=v[sa[i]]==v[sa[i-1]]&&v[sa[i]+j]==v[sa[i-1]+j]?p:++p;
	}
	//for (i=1;i<=n;i++) printf("%d ",sa[i]);putchar(10);
	for (i=1;i<=n;i++) rk[sa[i]]=i;
	for (i=1,Log[0]=-1;i<=n;i++) Log[i]=Log[i>>1]+1;
	for (i=1,p=0;i<=n;i++) {
		if (p) p--;
		if (rk[i]==n) continue;
		while (str[i+p]==str[sa[rk[i]+1]+p]) p++;
		h[0][rk[i]]=p;
	}
	for (j=1;j<20;j++)
		for (i=1;i<=n;i++)
			h[j][i]=min(h[j-1][i],h[j-1][i+(1<<(j-1))]);
}

char str[N];
int len[N],st[N];
int head[N],nxt[N],qr[N];
int ord[N],*cur[N],hd[N];

int mi[N*4];
#define lc (i<<1)
#define rc (lc|1)
void modify(int i,int l,int r,int k,int t) {
	if (l==r) mi[i]=t;
	else {
		int mid=(l+r)>>1;
		k<=mid?modify(lc,l,mid,k,t):modify(rc,mid+1,r,k,t);
		mi[i]=min(mi[lc],mi[rc]);
	}
}
bool query(int i,int l,int r,int L,int R,int t) {
	if (mi[i]>t) return false;
	if (L<=l&&r<=R) return true;
	int mid=(l+r)>>1;
	if (L<=mid&&query(lc,l,mid,L,R,t)) return true;
	return mid<R&&query(rc,mid+1,r,L,R,t);
}
LL ans[N];
int main()
{
	freopen("name.in","r",stdin);
	freopen("name.out","w",stdout);
	int n,m,i,all,j,l,rep,d,low,up,mid,x,y,t;
	gs(str+1,n);all=n;gi(m);
	for (i=1;i<=m;i++) {
		str[++all]='a'+26;
		gs(str+all+1,len[i]);
		for (j=all+1;j<=all+len[i];j++)
			hd[j]=i;
		st[i]=all;
		cur[i]=ord+all;
		all+=len[i];
		gi(j),nxt[i]=head[j],head[j]=i,gi(qr[i]);
	}
	build(str,all);
	for (i=1;i<=all;i++)
		if (hd[sa[i]])
			*++cur[hd[sa[i]]]=sa[i];

	memset(mi,0x3f,sizeof(mi));
	for (l=n;l;l--) {
		modify(1,1,all,rk[l],l);
		for (i=head[l];i;i=nxt[i]) {
			cur[i]-=len[i];
			for (j=1;j<=len[i];j++) {
				rep=0;
				low=0,up=min(st[i]+len[i]-cur[i][j]+1,qr[i]-l+1);
				while (low!=up) {
					mid=(low+up+1)>>1;
					x=y=rk[cur[i][j]];
					for (t=20;~(t=min(t-1,Log[x-1]));)
						if (h[t][x-(1<<t)]>=mid) x-=1<<t;
					for (t=20;~(t=min(t-1,Log[all-y]));)
						if (h[t][y]>=mid) y+=1<<t;
					if (query(1,1,all,x,y,qr[i]-mid+1))
						low=mid;
					else
						up=mid-1;
				}
				rep=low;
				if (j==1)
					ans[i]+=st[i]+len[i]-cur[i][j]+1-rep;
				else {
					d=min(lcp(cur[i][j-1],cur[i][j]),st[i]+len[i]-max(cur[i][j],cur[i][j-1])+1);
					ans[i]+=st[i]+len[i]-cur[i][j]+1-max(d,rep);
				}
				//if (i==8)
				//	print(ans[i]),putc('\n');
			}
		}
	}
	for (i=1;i<=m;i++)
		print(ans[i]),putc('\n');
	return 0;
}

评测结果