您的位置: 首页  >  IT文章  >  [luoguP2463] [SDOI2008]Sandy的卡片（后缀数组 + st表）

[luoguP2463] [SDOI2008]Sandy的卡片（后缀数组 + st表）

分类: IT文章 • 2022-07-16 18:54:42

传送门

很容易想到，题目中的相同是指差分数组相同。

那么可以把差分数组连起来，中间加上一个没有出现过的且字典序小的数

双指针移动，用st表维护height数组中的最小值。

当然用单调队列应该也可以且更快。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 1010000

using namespace std;

int n, m, t, cnt, len, ans, mx, mn = 1e9;
int pos[N], a[N / 1000], num[N / 1000], sa[N], height[N], Rank[N], b[N], x[N], y[N], d[N][22], s[N];

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

inline void build_sa()
{
	int i, k, p;
	for(i = 0; i < m; i++) b[i] = 0;
	for(i = 0; i < n; i++) b[x[i] = s[i]]++;
	for(i = 1; i < m; i++) b[i] += b[i - 1];
	for(i = n - 1; i >= 0; i--) sa[--b[x[i]]] = i;
	for(k = 1; k <= n; k <<= 1)
	{
		p = 0;
		for(i = n - k; i < n; i++) y[p++] = i;
		for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
		for(i = 0; i < m; i++) b[i] = 0;
		for(i = 0; i < n; i++) b[x[y[i]]]++;
		for(i = 1; i < m; i++) b[i] += b[i - 1];
		for(i = n - 1; i >= 0; i--) sa[--b[x[y[i]]]] = y[i];
		swap(x, y);
		p = 1, x[sa[0]] = 0;
		for(i = 1; i < n; i++)
			x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
		if(p >= n) break;
		m = p;
	}
}

inline void build_height()
{
	int i, j, k = 0;
	for(i = 0; i < n; i++) Rank[sa[i]] = i;
	for(i = 0; i < n; i++)
	{
		if(k) k--;
		j = sa[Rank[i] - 1];
		while(s[i + k] == s[j + k]) k++;
		height[Rank[i]] = k;
	}
}

inline void build_st()
{
	int i, j;
	for(i = 1; i < n; i++) d[i][0] = height[i];
	for(j = 1; (1 << j) < n; j++)
		for(i = 1; i + (1 << j) - 1 < n; i++)
			d[i][j] = min(d[i][j - 1], d[i + (1 << j - 1)][j - 1]);
}

inline int query(int l, int r)
{
	l++;
	if(l > r) return 0;
	int tmp = log2(r - l + 1);
	return min(d[l][tmp], d[r - (1 << tmp) + 1][tmp]);
}

inline void solve()
{
	int i, j = 0;
	for(i = 0; i < n; i++)
	{
		while(j < n && cnt < t)
		{
			if(!num[pos[sa[j]]]++ && pos[sa[j]]) cnt++;
			j++;
		}
		if(cnt == t) ans = max(ans, query(i, j - 1));
		if(!--num[pos[sa[i]]] && pos[sa[i]]) cnt--;
	}
}

int main()
{
	int i, j, k;
	t = read();
	for(i = 1; i <= t; i++)
	{
		k = read();
		for(j = 1; j <= k; j++) a[j] = read();
		for(j = 1; j < k; j++)
		{
			pos[n] = i;
			s[n++] = a[j + 1] - a[j];
			mn = min(mn, s[n - 1]);
		}
		s[n++] = mx++;
	}
	for(i = 0; i < n; i++)
		if(pos[i]) s[i] = s[i] - mn + mx, m = max(m, s[i]);
	m++;
	build_sa();
	build_height();
	build_st();
	solve();
	printf("%d
", ans + 1);
	return 0;
}

　　

相关推荐