代码

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>

const size_t ioSize = 1 << 21;
char iBuf[ioSize], *iS, *iE, oBuf[ioSize], *oS(oBuf), *oE(oBuf + ioSize);
inline char getc()
{
	return iS == iE ? iE = iBuf + fread(iS = iBuf, 1, ioSize, stdin), iS == iE ? EOF : *iS++ : *iS++;
}
void reads(char *s)
{
	char c;
	for (c = getc(); !islower(c); c = getc())
		;
	*s++ = c;
	for (c = getc(); islower(c); c = getc())
		*s++ = c;
	*s = '\0';
}
void readi(int &x)
{
	char c;
	for (c = getc(); !isdigit(c); c = getc())
		;
	x = c ^ '0';
	for (c = getc(); isdigit(c); c = getc())
		(x *= 10) += c ^ '0';
}
inline void flush()
{
	fwrite(oBuf, 1, oS - oBuf, stdout);
	oS = oBuf;
}
inline void putc(char c)
{
	*oS++ = c;
	if (oS == oE)
		flush();
}
template<typename T>
void puti(T x)
{
	static char qu[20];
	char *qr = qu;
	do
		*qr++ = x % 10 ^ '0';
	while (x /= 10);
	while (qr != qu)
		putc(*--qr);
	putc('\n');
}

const size_t maxL = 1600005, maxQ = 100005;

char S[maxL];
int N, Q, L, qL[maxQ], qR[maxQ], posL[maxQ], posR[maxQ];
int SA[maxL], Rank[maxL], H[maxL], ST[21][maxL], Lg[maxL];

const size_t _M_size = 300 << 20;
char _M_pool[_M_size], *_M_cur(_M_pool + _M_size);
inline void *operator new(size_t size)
{
	return _M_cur -= size;
}
inline void operator delete(void *) {}

struct node
{
	int sum;
	node *lc, *rc;
	node() : sum(0)
	{
		lc = rc = this;
	}
} *null = new node(), *root[maxL];

void modify(node *&o, int l, int r, int pos)
{
	o = new node(*o);
	++(o->sum);
	if (l == r)
		return;
	int m = l + r >> 1;
	if (pos <= m)
		modify(o->lc, l, m, pos);
	else
		modify(o->rc, m + 1, r, pos);
}

int query(node *o, int l, int r, int tl, int tr)
{
	if (l >= tl && r <= tr)
		return o->sum;
	int m = l + r >> 1;
	if (tr <= m)
		return query(o->lc, l, m, tl, tr);
	if (tl > m)
		return query(o->rc, m + 1, r, tl, tr);
	return query(o->lc, l, m, tl, tr) + query(o->rc, m + 1, r, tl, tr);
}

int Child[maxL * 2 + 1][27], Link[maxL * 2 + 1], Pos[maxL * 2 + 1], Len[maxL * 2 + 1], tot, last;
bool isEnd[maxL * 2 + 1];

void extend(int c, int i)
{
	int cur = ++tot;
	Len[cur] = Len[last] + 1, Pos[cur] = i, isEnd[cur] = true;
	int p = last;
	while (p != -1 && !Child[p][c])
	{
		Child[p][c] = cur;
		p = Link[p];
	}
	if (p != -1)
	{
		int q = Child[p][c];
		if (Len[q] != Len[p] + 1)
		{
			int t = ++tot;
			Len[t] = Len[p] + 1;
			std::memcpy(Child[t], Child[q], sizeof(Child[0]));
			Link[t] = Link[q], Pos[t] = Pos[q];
			while (p != -1 && Child[p][c] == q)
			{
				Child[p][c] = t;
				p = Link[p];
			}
			Link[q] = Link[cur] = t;
		}
		else
			Link[cur] = q;
	}
	last = cur;
}

void DFS(int i)
{
	if (isEnd[i])
		SA[Rank[Pos[i]] = ++tot] = Pos[i];
	for (int j = 0; j <= 26; ++j)
		if (Child[i][j])
			DFS(Child[i][j]);
}

void getSA()
{
	Link[0] = -1;
	for (int i = L; i; --i)
		extend(S[i] == '#' ? 26 : S[i] - 'a', i);
	memset(Child, 0, sizeof(Child));
	for (int i = 1; i <= tot; ++i)
		Child[Link[i]][S[Pos[i] + Len[Link[i]]] == '#' ? 26 : S[Pos[i] + Len[Link[i]]] - 'a'] = i;
	tot = 0;
	DFS(0);
	// for (int i = 1; i <= L; ++i)
		// printf("%d\n", SA[i]);
	// fflush(stdout);
	for (int i = 1, h = 0; i <= L; ++i)
	{
		if (h)
			--h;
		if (Rank[i] == 1)
			continue;
		while (S[i + h] == S[SA[Rank[i] - 1] + h])
			++h;
		H[Rank[i]] = h;
	}

	for (int i = 2; i <= L; ++i)
		ST[0][i] = H[i];
	for (int i = 1; i <= Lg[L]; ++i)
		for (int j = 2; j + (1 << i) - 1 <= L; ++j)
			ST[i][j] = std::min(ST[i - 1][j], ST[i - 1][j + (1 << i - 1)]);
}

inline int getMin(int l, int r)
{
	int d = Lg[r - l + 1];
	return std::min(ST[d][l], ST[d][r - (1 << d) + 1]);
}

inline int LCP(int x, int y)
{
	if (x == y)
		return L - x + 1;
	x = Rank[x], y = Rank[y];
	if (x > y)
		std::swap(x, y);
	return getMin(x + 1, y);
}

bool check(int ql, int qr, int l, int r)
{
	if (r - l > qr - ql)
		return false;
	int lb = Rank[l], rb = Rank[l], d;
	/*for (int d = 20; ~d; --d)
	{
		if (rb + (1 << d) <= L && ST[d][rb + 1] >= r - l + 1)
			rb += 1 << d;
		if (lb - (1 << d) > 0 && ST[d][lb - (1 << d) + 1] >= r - l + 1)
			lb -= 1 << d;
	}*/
	for (d = 0; 1 << d < lb && ST[d][lb - (1 << d) + 1] >= r - l + 1; ++d)
		;
	for (--d; ~d; --d)
		if (lb - (1 << d) > 0 && ST[d][lb - (1 << d) + 1] >= r - l + 1)
			lb -= 1 << d;
	for (d = 0; rb + (1 << d) <= L && ST[d][rb + 1] >= r - l + 1; ++d)
		;
	for (--d; ~d; --d)
		if (rb + (1 << d) <= L && ST[d][rb + 1] >= r - l + 1)
			rb += 1 << d;
	static const int limit = 100;
	if (rb - lb + 1 <= limit)
	{
		for (int i = lb; i <= rb; ++i)
			if (SA[i] >= ql && SA[i] <= qr - (r - l))
				return true;
		return false;
	}
	return query(root[rb], 1, N, ql, qr - (r - l)) - query(root[lb - 1], 1, N, ql, qr - (r - l));
}

int main()
{
	reads(S + 1);
	N = L = strlen(S + 1);
	readi(Q);
	for (int i = 1; i <= Q; ++i)
	{
		static char buffer[maxL];
		reads(buffer + 1), readi(qL[i]), readi(qR[i]);
		S[++L] = '#';
		posL[i] = L + 1;
		for (char *s = buffer + 1; *s; ++s)
			S[++L] = *s;
		posR[i] = L;
	}

	Lg[0] = -1;
	for (int i = 1; i <= L; ++i)
		Lg[i] = Lg[i >> 1] + 1;

	getSA();

	root[0] = null;
	for (int i = 1; i <= L; ++i)
	{
		root[i] = root[i - 1];
		if (SA[i] <= N)
			modify(root[i], 1, N, SA[i]);
	}

	for (int i = 1; i <= Q; ++i)
	{
		static int temp[maxL];
		for (int l = posL[i], r = posL[i] - 1; l <= posR[i]; ++l)
		{
			r = std::max(r, l - 1);
			while (r < posR[i] && check(qL[i], qR[i], l, r + 1))
				++r;
			temp[l] = r - l + 1;
		}
		static int buffer[maxL];
		int cnt = 0;
		for (int j = posL[i]; j <= posR[i]; ++j)
			buffer[++cnt] = j;
		std::sort(buffer + 1, buffer + 1 + cnt, [](int a, int b) {
			return Rank[a] < Rank[b];
		});
		for (int j = 2; j <= cnt; ++j)
			temp[buffer[j]] = std::max(temp[buffer[j]], LCP(buffer[j - 1], buffer[j]));
		long long ans = (long long)(posR[i] - posL[i] + 2) * (posR[i] - posL[i] + 1) / 2;
		for (int j = posL[i]; j <= posR[i]; ++j)
			ans -= temp[j];
		puti(ans);
	}

	flush();

	return 0;
}

评测结果