题目描述

定义：如果字符串 A 是字符串 B 的后缀，那么称 B 是 A 的 XQ 串。

小奇有 n 个只包含小写字母的字符串，编号为 1-n，表示为 Si。

接下来对于每个串 Si，小奇想知道：对于小奇拥有的 n 个字符串，所有是 Si 的 XQ 串的编号集合(包括 i）中第 Ki 小的编号。

对于 100%的数据 n<=100000，字符串总长<=300000。

题解

考虑处理 XQ 串，把字符串反过来建字典树，然后查询该串结束未知子树中第 k 大，可持久化线段树维护 dfs 序。喵喵题！

代码

const int N = 3e5 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int K[N];
	char s[N];

	int root[N];
	struct PersistentSegmentTree {
		int ls[N << 3], rs[N << 3], sum[N << 3];
		int cnt;
		void Insert (int &p, int l, int r, int val) {
			if (!p) p = ++cnt;
			if (l == r) { sum[p]++; return; }
			int mid = (l + r) >> 1;
			if (val <= mid) Insert (ls[p], l, mid, val);
			else Insert (rs[p], mid + 1, r, val);
			sum[p] = sum[ls[p]] + sum[rs[p]];
		}
		int Merge (int p, int q) {
			if (p + q == max(p, q)) return max(p, q);
			ls[p] = Merge(ls[p], ls[q]);
			rs[p] = Merge(rs[p], rs[q]);
			sum[p] = sum[ls[p]] + sum[rs[p]];
			return p;
		}
		int Query (int p, int l, int r, int rk) {
			if (rk > sum[p]) return -1;
			if (l == r) return l;
			int mid = (l + r) >> 1;
			if (sum[ls[p]] >= rk) return Query (ls[p], l, mid, rk);
			return Query (rs[p], mid + 1, r, rk - sum[ls[p]]);
		}
	} pst;

	vector <int> q[N];
	struct Trie {
		int ch[N][30], cnt = 1;
		int Insert (char *s) {
			int len = strlen(s + 1), now = 1;
			for (int i = len; i; i--) {
				if (!ch[now][s[i] - 'a']) ch[now][s[i] - 'a'] = ++cnt;
				now = ch[now][s[i] - 'a'];
			}
			return now;
		}
	} t;

	int ans[N];
	void Solve(int now) {
		for(int i = 0; i < 26; i++)
			if(t.ch[now][i]) {
				Solve(t.ch[now][i]);
				root[now] = pst.Merge(root[now], root[t.ch[now][i]]);
			}
		for(int i = 0; i < q[now].size(); i++) {
			int Q = q[now][i];
			ans[Q] = pst.Query(root[now], 1, n, K[Q]);
		}
	}

	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) {
			scanf ("%s", s + 1);
			int j = t.Insert(s);
			q[j].push_back(i);
			pst.Insert(root[j], 1, n, i);
		}
		for (int i = 1; i <= n; i++) K[i] = Read();
		Solve(1);
		for (int i = 1; i <= n; i++) printf ("%d\n", ans[i]);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}