Reincarnation HDU

\(\color{#0066ff}{ 题目描述 }\)

给定一个字符串，多次询问某一字串的f值

f(s)代表s的不同字串数量

\(\color{#0066ff}{输入格式}\)

第一行T，代表数据组数\(T\leq 5\)

每组数据第一行一个字符串\(1\leq len \leq 2000\)

然后一个数字m(\(1\leq m \leq 10000\))，表示有m个询问

接下来m行，每行两个整数l，r，表示询问[l,r]的字串的答案

\(\color{#0066ff}{输出格式}\)

对于每个询问，输出一行表示答案

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

本题不卡hash，但是正解不是hash

\(\color{#0066ff}{ 题解 }\)

考虑没有询问的时候，对于查询不同字串个数，见一个SAM就没事了

本题询问有10000个，考虑优化

因为长度是2000的，\(O(n^2)\)显然可以

所以我们开一个二维数组暴力预处理出所有的ans，然后\(O(1)\)查询

\(O(nq) \to O(n^2 + q)\)

#include<bits/stdc++.h>

using namespace std;

#define LL long long

LL in() {

	char ch; int x = 0, f = 1;

	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);

	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));

	return x * f;

}

const int maxn = 5555;

struct SAM {

protected:

	struct node {

		node *ch[26], *fa;

		int len, siz;

		node(int len = 0, int siz = 0): fa(NULL), len(len), siz(siz) {

			memset(ch, 0, sizeof ch);

		}

	};

	node *root, *tail, *lst;

	node pool[maxn];

public:

	node *extend(int c) {

		node *o = new(tail++) node(lst->len + 1, 1), *v = lst;

		for(; v && !v->ch[c]; v = v->fa) v->ch[c] = o;

		if(!v) o->fa = root;

		else if(v->len + 1 == v->ch[c]->len) o->fa = v->ch[c];

		else {

			node *n = new(tail++) node(v->len + 1), *d = v->ch[c];

			std::copy(d->ch, d->ch + 26, n->ch);

			n->fa = d->fa, d->fa = o->fa = n;

			for(; v && v->ch[c] == d; v = v->fa) v->ch[c] = n;

		}

		return lst = o;

	}

	void clr() {

		tail = pool;

		root = lst = new(tail++) node();

	}

	SAM() { clr(); }

}sam;

LL ans[2050][2050];

char s[maxn];

int main() {

	for(int T = in(); T --> 0;) {

		scanf("%s", s + 1);

		int len = strlen(s + 1);

		for(int i = 1; i <= len; i++) {

			for(int j = i; j <= len; j++) {

				auto o = sam.extend(s[j] - 'a');

				ans[i][j] = ans[i][j - 1] + o->len - o->fa->len;

			}

			sam.clr();

		}

		for(int m = in(); m --> 0;) {

			int l = in(), r = in();

			printf("%lld\n", ans[l][r]);

		}

	}

	return 0;

}

巴特西

Reincarnation HDU - 4622

\(\color{#0066ff}{ 题目描述 }\)

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{ 题解 }\)

考虑没有询问的时候，对于查询不同字串个数，见一个SAM就没事了

本题询问有10000个，考虑优化

因为长度是2000的，\(O(n^2)\)显然可以

所以我们开一个二维数组暴力预处理出所有的ans，然后\(O(1)\)查询

\(O(nq) \to O(n^2 + q)\)

最新文章

热门文章

巴特西

Reincarnation HDU - 4622

\(\color{#0066ff}{ 题目描述 }\)

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{ 题解 }\)

考虑没有询问的时候，对于查询不同字串个数，见一个SAM就没事了

本题询问有10000个，考虑优化

因为长度是2000的，\(O(n^2)\)显然可以

所以我们开一个二维数组暴力预处理出所有的ans， 然后\(O(1)\)查询

\(O(nq) \to O(n^2 + q)\)

最新文章

热门文章

所以我们开一个二维数组暴力预处理出所有的ans，然后\(O(1)\)查询