代码

#include <cstdio>
#include <cstring>

#include <algorithm>

typedef long long ll;

using namespace std;

struct Node {
	int a, b, id;
};

struct Seg {
	int l, r, v;
	Seg *ls, *rs;

	void ch(int k, int v) {
		if (l == r) {
			this->v = v;
			return;
		}
		if (k <= ls->r)
			ls->ch(k, v);
		else
			rs->ch(k, v);
		this->v = max(ls->v, rs->v);
	}

	int qry(int l, int r) const {
		if (this->l == l && this->r == r)
			return v;
		if (r <= ls->r)
			return ls->qry(l, r);
		if (l >= rs->l)
			return rs->qry(l, r);
		return max(ls->qry(l, ls->r), rs->qry(rs->l, r));
	}
};

const int Q = 100010, N = 2000010, LGN = 21;

int n;
char tmp[N];
int s[N], cnt[N], rk[N], sa[N], ht[N], id[N];
int lgt[N];
int pre[N], suf[N];
int st[N][LGN];
int ql[Q], qr[Q], sl[Q], sr[Q], cur[Q];
ll ans[Q];
Node p[N], q[N];
Seg* seg;

void ins();
int qry(int l, int r);
Seg* build(int l, int r, int v);

int main() {
	int qc;
	ins();
	scanf("%d", &qc);
	for (int i = 1; i <= qc; ++i) {
		ins();
		scanf("%d%d", &ql[i], &qr[i]);
	}
	for (int i = 1; i <= n; ++i)
		cnt[s[i]] = 1;
	for (int i = 1; i <= 26 + qc; ++i)
		cnt[i] += cnt[i - 1];
	for (int i = 1; i <= n; ++i)
		rk[i] = cnt[s[i]];
	for (int t = 1; t <= n; t <<= 1) {
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; ++i) {
			p[i].id = i;
			p[i].a = rk[i];
			p[i].b = i + t > n ? 0 : rk[i + t];
		}
		for (int i = 1; i <= n; ++i)
			++cnt[p[i].b];
		for (int i = 1; i <= n; ++i)
			cnt[i] += cnt[i - 1];
		for (int i = n; i; --i)
			q[cnt[p[i].b]--] = p[i];
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; ++i)
			++cnt[q[i].a];
		for (int i = 1; i <= n; ++i)
			cnt[i] += cnt[i - 1];
		for (int i = n; i; --i)
			p[cnt[q[i].a]--] = q[i];
		int c = 0;
		for (int i = 1; i <= n; ++i) {
			if (p[i].a != p[i - 1].a || p[i].b != p[i - 1].b)
				++c;
			rk[p[i].id] = c;
		}
		if (c == n)
			break;
	}
	for (int i = 1; i <= n; ++i)
		sa[rk[i]] = i;
	int hh = 0;
	for (int i = 1; i <= n; ++i) {
		hh = max(hh - 1, 0);
		while (s[i + hh] == s[sa[rk[i] + 1] + hh])
			++hh;
		ht[rk[i]] = hh;
	}

	for (int i = 1; i <= qc; ++i)
		for (int j = sl[i]; j <= sr[i]; ++j)
			id[rk[j]] = i;

	for (int i = 2; i <= n; ++i)
		lgt[i] = lgt[i >> 1] + 1;
	for (int i = 1; i < n; ++i) {
		st[i][0] = ht[i];
		for (int j = 1; (1 << j) <= i; ++j)
			st[i][j] = min(st[i][j - 1], st[i - (1 << (j - 1))][j - 1]);
	}

	seg = build(1, n, 0);
	for (int i = 1; i <= n; ++i) {
		if (sa[i] <= sr[0])
			seg->ch(sa[i], i);
		else if (id[i])
			pre[i] = seg->qry(ql[id[i]], qr[id[i]]);
	}

	seg = build(1, n, -n - 1);
	for (int i = n; i; --i) {
		if (sa[i] <= sr[0])
			seg->ch(sa[i], -i);
		else if (id[i]) {
			suf[i] = -seg->qry(ql[id[i]], qr[id[i]]);
			if (suf[i] == n + 1)
				suf[i] = 0;
		}
	}

	for(int i = 1; i <= n; ++i) {
		if (!id[i])
			continue;
		int lim = 0;
		if (pre[i])
			lim = max(lim, qry(pre[i], i));
		if (suf[i])
			lim = max(lim, qry(i, suf[i]));
		if (cur[id[i]])
			lim = max(lim, qry(cur[id[i]], i));
		ans[id[i]] -= lim;
		cur[id[i]] = i;
	}

	for (int i = 1; i <= qc; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}

Seg* build(int l, int r, int v) {
	static Seg pool[N * 4];
	static Seg* ptop = pool;
	Seg* p = ptop;
	++ptop;
	p->l = l;
	p->r = r;
	p->v = v;
	if (l == r)
		return p;
	int mid = (l + r) / 2;
	p->ls = build(l, mid, v);
	p->rs = build(mid + 1, r, v);
	return p;
}

int qry(int l, int r) {
	--r;
	int lv = lgt[r - l + 1];
	return min(st[r][lv], st[l + (1 << lv) - 1][lv]);
}

void ins() {
	static int id = 0;
	if (!id)
		s[++n] = id + 26;
	scanf("%s", tmp);
	sl[id] = n + 1;
	for (char* c = tmp; *c; ++c)
		s[++n] = *c - 'a' + 1;
	sr[id] = n;
	ans[id] = (sr[id] - sl[id] + 1) * (sr[id] - sl[id] + 2LL) / 2;
	++id;
}

评测结果