CF547E Mike and Friends

IOI2020集训队作业

~~呐,你想要的的小暗~~

最近集训队作业加大难度了啊?

而且你谷愚人节随机名字颜色真不错

给定 $n$ 个字符串 $s_{1 \dots n}$ 。
$q$ 次询问 $s_ks$ 在 $s_{l \dots r}$ 中出现了多少次。
$n, \sum |s| \le 2 \times 10^5$ $q \le 5 \times 10^5$ 。

主要是考虑区间这一维限制怎么消掉

你发现我们完全可以用类似于莫队的扩展方式来消掉,也就是维护一个编号的数组

但是我们查询在建出SAM后就变成了对于一个子树里编号集合的查询...莫队好像没啥意义

因为我们有线段树合并啊w,用线段树维护编号的数组

线段树合并到fail树那个节点就可以处理这个节点上的所有查询了,直接区间查询和就好

但问题来了,这样很可能MLE啊QAQ

所以我们建立广义SAM时还需要注意不能开直接开新点,不过这个好像和之前写广义SAM写法是一样的,不过要拆开近似点

看下代码什么都懂啦

code:

#include<iostream>
#include<cstdio>
#include<cstring>
const int MAXN = 5e5 + 7;
const int INF = 1e7;
namespace Tree {
	int root[MAXN], T, lc[INF], rc[INF], w[INF];
#define lt lc[k], l, mid
#define rt rc[k],mid+1,r
	inline void modi(int &k, int l, int r, int x) {
		if(!k)k = ++T;
		w[k]++;
		if(l == r)return ;
		register int mid = (l + r) >> 1;
		if(x <= mid)modi(lt, x);
		else modi(rt, x);
	}
	inline int query(int k, int l, int r, int x, int y) {
		if(x > r || y < l || !k)return 0;
		if(x <= l && r <= y)return w[k];
		register int mid = (l + r) >> 1;
		return query(lt, x, y) + query(rt, x, y);
	}
	inline int merge(int x, int y) {
		if(!x || !y)return x + y;
		register int now = ++T;
		w[now] = w[x] + w[y];
		lc[now] = merge(lc[x], lc[y]);
		rc[now] = merge(rc[x], rc[y]);
		return now;
	}
};

namespace SAM {
	int ch[MAXN][27], len[MAXN], link[MAXN], T, lst, p, q, cur, cle;
	int buc[MAXN], sa[MAXN], id[MAXN];
	inline void init() {
		lst = 1;
		T = 1;
	}
	inline void add(int x) {
		if(ch[lst][x]) {
			p = lst;
			q = ch[p][x];
			if(len[p] + 1 == len[q]) {
				lst = q;
				return ;
			}
			cle = ++T;
			len[cle] = len[p] + 1;
			link[cle] = link[q];
			memcpy(ch[cle], ch[q], sizeof(ch[q]));
			while(p && ch[p][x] == q)ch[p][x] = cle, p = link[p];
			lst = cle;
			link[q] = cle;
			return ;
		}
		len[cur = ++T] = len[lst] + 1;
		p = lst;
		lst = cur;
		while(p && !ch[p][x])ch[p][x] = cur, p = link[p];
		if(!p) {
			link[cur] = 1;
			return ;
		}
		q = ch[p][x];
		if(len[p] + 1 == len[q]) {
			link[cur] = q;
			return ;
		}
		cle = ++T;
		len[cle] = len[p] + 1;
		link[cle] = link[q];
		memcpy(ch[cle], ch[q], sizeof(ch[q]));
		while(p && ch[p][x] == q)ch[p][x] = cle, p = link[p];
		link[cur] = link[q] = cle;
	}
	inline void sort() {
		for(int i = 1; i <= T; ++i)buc[len[i]]++;
		for(int i = 1; i <= T; ++i)buc[i] += buc[i - 1];
		for(int i = T; i >= 1; --i)sa[buc[len[i]]--] = i;
		for(int i = T; i >= 1; --i) {
			if(sa[i] == 1)continue;
			//printf("%d %d %d\n", sa[i], len[i], link[i]);
			Tree::root[link[sa[i]]] = Tree::merge(Tree::root[link[sa[i]]], Tree::root[sa[i]]);
		}
	}
};
char c[MAXN];
int n, m, X, Y, W;
int main() {
	scanf("%d%d", &n, &m);
	SAM::init();
	for(int i = 1; i <= n; ++i) {
		scanf("%s", c + 1);
		SAM::lst = 1;
		int len = strlen(c + 1);
		for(int j = 1; j <= len; ++j) {
			SAM::add(c[j] - 'a' + 1);
			Tree::modi(Tree::root[SAM::lst], 1, n, i);
		}
		SAM::id[i] = SAM::lst;
	}
	SAM::sort();
	while(m-- > 0) {
		scanf("%d%d%d", &X, &Y, &W);
		printf("%d\n", Tree::query(Tree::root[SAM::id[W]], 1, n, X, Y));
	}
	return 0;
}

夏晓光(loveJY)的博客

CF547D Mike and Fish