考虑到无法理解 T2，还是先把 T1 总结亿下吧。
可能有关联的题目：NOI2016优秀的拆分，SCOI2016萌萌哒。
求最小代价毫无疑问类似最小生成树。
要想求最小生成树的边就要把所有的平方串找出来。
传统方法毫无疑问是 O(n^2) 的，O(n^2) 枚举端点，O(1) 哈希检验。
然而这样太慢了，而且还没有考虑后续怎么做最小生成树（森林）。
首先按 w_i 排序，类似 kruskal 的第一步。
考虑借鉴 [NOI2016优秀的拆分] 的方法，若当前枚举长度为 2 \cdot len 的平方串，在 i=len,2 \cdot len,3 \cdot len,4 \cdot len … 的地方设置特殊点。
对于相邻的两个特殊点 i 和 j=i+len ，用二分+hash 求出 LCP（最长公共前缀）的长度和 LCS（最长公共后缀）的长度。若两者相加是大于等于 len 的，说明 $\forall i \in[i-l{LCS}+1,i+l{LCP}-1]，i与i+len$ 均可以连边。
分析上面的复杂度。枚举长度是 O(n) 的，枚举相邻两个特殊点看起来是 O(n) 但由于事实上是调和级数因此是带上枚举长度一共是 O(n \log n) 的。
二分 + hash 再带上一个 \log n ，因此上面总共的复杂度是 O (n \log^2 n) 的。
现在问题转化成给予两个区间 [l1,r1] 和 [l2,r2] (设 l1 具体地，集合[5,8]并入[1,4]时，par_{2,5}=1([1,4]的左端点很显然是1$)
我们给出合并时的代码：
void unite(int x,int y,int k)
{
int fx = find(x,k),fy = find(y,k);
if (fx == fy)return;
par[fx][k] = fy;
if(!k)return;
unite(x, y, k - 1);
unite(x + (1 << (k - 1)),y + (1 << (k - 1)), k - 1);
}
其中 k 表示层数。
合并当前层，之后分治的去递归下去。
在主函数的代码形如：
for(int k = 19; ~k; k --)
{
if (l1 + (1 << k) - 1 <= r1)
{
unite(l1, l2, k);
l1 += (1 << k);
l2 += (1 << k);
}
}
接下来分析总体复杂度。
看起来是嵌套的，其实不然。
学过最小生成树的我们知道 n 个节点的树只有 n-1 条边，因此合并最多仅会发生 O(n) 次。
每次合并是 \log n 的，因为树高就那么高。
因此最后总体复杂度取前面二分+hash的较高复杂度，为 O(n \log^2 n)
给出所有代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
typedef pair<int,int> PII;
typedef long long LL;
const LL B = 131, mod = 998244353;
int n, a[N], par[N][20];
LL power[N], h[N], res = 0;
PII w[N];
LL get(int l,int r){return ((h[r] - (h[l - 1] * power[r - l + 1] % mod)) % mod + mod) % mod;}
int find(int x,int k)
{
if (par[x][k] == x)return x;
else return par[x][k] = find(par[x][k],k);
}
void unite(int x,int y,int k,int cost)
{
int fx = find(x,k),fy = find(y,k);
if (fx == fy)return;
par[fx][k] = fy;
if(!k)
{
res += cost;
return;
}
unite(x, y, k - 1, cost);
unite(x + (1 << (k - 1)),y + (1 << (k - 1)), k - 1, cost);
}
int S(int x,int y,int dir)
{
int l = 0, r;
if(dir) r = min(n - x + 1, n - y + 1);
else r = min(x, y);
while (l < r)
{
int mid = (l + r + 1) >> 1;
LL w1, w2;
if (dir)
{
w1 = get(x, x + mid - 1);
w2 = get(y, y + mid - 1);
}
else
{
w1 = get(x - mid + 1, x);
w2 = get(y - mid + 1, y);
}
if(w1 == w2)l = mid;
else r = mid - 1;
}
return l;
}
void work()
{
res = 0;
scanf("%d", &n);
power[0] = 1;
for (int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
power[i] = power[i - 1] * B % mod;
h[i] = (h[i - 1] * B % mod + a[i]) % mod;
for(int j = 0; j <= 19; j++)par[i][j] = i;
}
for (int i = 1; i <= n / 2; i ++)
{
scanf("%d", &w[i].first);
w[i].second = i;
}
sort(w + 1, w + (n / 2) + 1);
for (int pos = 1; pos <= n / 2; pos ++)// O (n)
{
int len = w[pos].second;
for (int i = len; i + len <= n; i += len)
{
int x = i, y = i + len;
if(a[x] != a[y]) continue;
int LCP = S(x, y, 1), LCS = S(x, y, 0);
if (LCP + LCS >= len + 1)// cover
{
int l1 = x - LCS + 1, r2 = y + LCP - 1;
int l2 = l1 + len, r1 = r2 - len;
// unite [i,i + len] for i in [l1,r2-len-1]
for (int k = 19; ~k; k --)
{
if(l1 + (1 << k) - 1 <= r1)
{
unite(l1, l2, k, w[pos].first);
l1 += (1 << k);
l2 += (1 << k);
}
}
}
}
}
printf("%lld\n",res);
}
int main()
{
freopen("endless.in", "r", stdin);
freopen("endless.out", "w", stdout);
int T;
scanf("%d", &T);
while(T --)work();
return 0;
}
最后感谢 konata 将卡hash的两组数据删除了。