「HAOI2017」供给侧改革

发表于

题目描述

Anihc国提高社会生产力水平.落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质.你调查了某个产业近来 $ n $ 个时期的供求关系平衡情况.每个时期的情况都用 $ 0 $ 或 $ 1 $ 中的一个数字来表示.于是这就是—个长度为 $ n $ 的 $ 01 $ 字符串 $S$ 。为了更好的了解这一些数据.你需要解决一些询问.我们令 $ data(l,r) $ 表示：在字符串 $S$ 中.起始位置在$ [l,r] $之间的这些后缀之中，具有最长公共前缀的两个后缀的最长公共前缀的长度。

对于每一个询问 $ L $ , $ R $ .求

$ ans = \sum\limits_{ L \le i \lt R } data(i, R) $

数据范围$100000$

由于你其实根本没有时间调查，所以这些数据都是乱编的，即串S中的每一位都是在 $ 0 $ 和 $ 1 $ 之间随机产生的。

算法讨论

这道题出题人真是搞事。。还以为是什么高深的后缀数组之类的做法，结果正解太乱搞了

题目关键在于最后一句话，数据是随机的，于是两两后缀的LCP不会太长，网上说不超过40,我也不知道怎么算出来的

于是就变成了一道水题，离线加后缀(只加后缀前40个)，trie树记一下timing就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 100005;

char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline int _R() {
	int d; char t;
	while (t = GC, t < '0' || t > '9') ;
	d = t - '0';
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return d;
}
inline int _S(char *c) {
	char *t = c, ch;
	while (ch = GC, ch == ' ' || ch == '\n' || ch == '\r') ;
	*t ++ = ch;
	while (ch = GC, ch != ' ' && ch != '\n' && ch != '\r') *t ++ = ch;
	*t = 0;
	return t - c;
}

int n, m;
struct Query {
	int l, r, id;
	bool operator < (const Query& rhs) const {
		return r == rhs.r ? l < rhs.l : r < rhs.r;
	}
} Q[N];

char str[N];
int root, tot, Ans[N], Son[N * 40][2], Last[N * 40], Max[55];
void Insert(int st) {
	int i, t, p = root;
	for (i = 0; st + i <= n && i < 45; i ++) {
		t = str[st + i] - '0';
		if (!Son[p][t]) Son[p][t] = ++ tot;
		else Max[i + 1] = max(Max[i + 1], Last[Son[p][t]]);
		p = Son[p][t];
		Last[p] = st;
	}
}
int main () {
	int i, j, k, sum = 0, l;
	n = _R(), m = _R();
	_S(str + 1);
	for (i = 1; i <= m; i ++) Q[i].id = i, Q[i].l = _R(), Q[i].r = _R();
	sort(Q + 1, Q + 1 + m);
	root = tot = 1;
	for (i = 1, k = 0; i <= m; i ++) {
		while (k + 1 <= Q[i].r) k ++, Insert(k);
		l = Q[i].l;
		Max[0] = Q[i].r;
		for (j = 44; j >= 0; j --) 
			if (Max[j] >= l) Ans[Q[i].id] += j * (Max[j] - l + 1), l = Max[j] + 1;
	}
	for (i = 1; i <= m; i ++) printf("%d\n", Ans[i]);
}