“蔚来杯“2022牛客暑期多校训练营3 H.Hacker SAM+线段树/DP/分治(不带修查区间最大子段和)

H.Hacker 题目分析

给定母串以及若干子串，子串长度固定，每个位置都有一个权值，要求在子串和母串的公共子串中找到一个连续区间，使得连续区间的权值和最大，求最大权值和。

首先对母串建立SAM，然后用线段树维护静态区间和的最大值，然后每次对插入的字符串：

我们设置两个变量 v , l v,l v,l，分别表示当前状态以及匹配长度，一开始 v = t 0 v=t_0 v=t0​ 且 l = 0 l=0 l=0，即匹配为空串。

现在我们来描述如何添加一个字符 T i T_{i} Ti​ 并为其重新计算答案：

• 如果存在一个从 v v v 到字符 T i T_{i} Ti​ 的转移，我们只需要转移并让 l l l 自增一。
• 如果不存在这样的转移，我们需要缩短当前匹配的部分，这意味着我们需要按照后缀链接进行转移：

v = link ⁡ ( v ) v=\operatorname{link}(v) v=link(v)

与此同时，需要缩短当前长度。显然我们需要将 l l l 赋值为 len ⁡ ( v ) \operatorname{len}(v) len(v)。

每次找到合法区间，直接线段树上查询并更新答案即可。

数据很水，不缩也能过，这里提供一组群友造的特殊样例：

输入：

11 11 1
aaaabbbaaaa
2 3 7 5 10 -2 0 10 2 4 0
aaaaaaaaaaa

输出：

25

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
const int INF = 1e9 + 7;

int ww[N];

#define ls rt  s;
        cout