2nd Universal Cup Stage 10 Harbin C 题解

First Post:

Last Update:

比较好的字符串题。

题意： https://qoj.ac/problem/7748

首先考虑暴力怎么写，设 ，那么对于 ， 都会以 为开头出现一次。将 做前缀和后可得 。

可以使用 exkmp 线性求出，不是重点。

考虑如何算答案。从小到大扫描 ，容易发现每个 的贡献会从 变化到 至多一次。变化后的贡献是好算的，树状数组统计即可。对于还没变化的位置 ，它们实际上说明 。考虑找到 的最小的 ，设为 。那么集合 其实就是 的 border 集合。画图后容易发现这一点。那我们相当于要对 的所有 border 求权值之和。对 求出 kmp 的 fail 数组之后可以 求得这个答案。

时间复杂度 。

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
60
61
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<int,int> pii;
#define FI first
#define SE second
#define mkp make_pair
int n,Q;
char s[N],t[N];
int nxt[N],Z[N],L[N];
ll w[N],sum[N];
int ql[N],qr[N];
ll ans[N];
set<int> Is;
vector<int> del[N]; // i + L[i]
vector<int> Qs[N];
struct BIT {
	ll tr[N];
	#define lowbit(x) (x&(-x))
	inline void upd(int x,ll v) { for(int i = x;i <= n;i += lowbit(i)) tr[i] += v;}
	inline ll Sum(int x) { ll res = 0;for(int i = x;i;i ^= lowbit(i)) res += tr[i];return res;}
} C;
int main() {
	scanf("%d%d",&n,&Q);
	scanf("%s%s",s + 1,t + 1);
	for(int i = 1;i <= n;i++) scanf("%lld",&w[i]),w[i] += w[i - 1];
	for(int i = 1;i <= Q;i++) scanf("%d%d",&ql[i],&qr[i]),Qs[qr[i]].push_back(i);
	Z[1] = n;
	for(int i = 2,l = 0,r = 0;i <= n;i++) {
		if(i <= r) Z[i] = min(Z[i - l + 1],r - i + 1);
		while(i + Z[i] <= n && s[1 + Z[i]] == s[i + Z[i]]) ++Z[i];
		if(i + Z[i] - 1 > r) l = i,r = i + Z[i] - 1;
	}
	for(int i = 1,l = 0,r = 0;i <= n;i++) {
		if(i <= r) L[i] = min(Z[i - l + 1],r - i + 1);
		while(i + L[i] <= n && s[1 + L[i]] == t[i + L[i]]) ++L[i];
		if(i + L[i] - 1 > r) l = i,r = i + L[i] - 1;
	}
	for(int i = 1;i <= n;i++) del[i + L[i]].push_back(i);
	nxt[1] = 0;
	for(int i = 2,j = 0;i <= n;i++) {
		while(j && s[i] != s[j + 1]) j = nxt[j];
		if(s[i] == s[j + 1]) ++j;
		nxt[i] = j;
	}
	for(int i = 1;i <= n;i++) sum[i] = sum[nxt[i]] + w[i];
	for(int r = 1;r <= n;r++) {
		Is.insert(r);
		for(auto i : del[r]) Is.erase(i),C.upd(i,w[L[i]]);
		for(auto i : Qs[r]) {
			auto it = Is.lower_bound(ql[i]);
			if(it != Is.end())
				ans[i] += sum[r - (*it) + 1];
			ans[i] += C.Sum(r) - C.Sum(ql[i] - 1);
		}
	}
	for(int i = 1;i <= Q;i++) cout << ans[i] << endl;
	return 0;
}

≡