Solution
还是去看了题解。 感谢大佬的博客→ 题解传送门
是一道思路比较新的题。
搞一个前缀和， 记录前 $i$ 个位置每种颜色的出现次数， 如果位置 $i$ 是 颜色 $a[i]$ 的最后一个位置， 就把颜色 $a[i]$ 清零。
这样就可以保证两个可以分割的点， 它们的前缀和一定是相同的。
$k$ 种颜色的前缀和不好维护(太大了）， 就开到hash里面去， 用hash检验是否相等。
两个分割点 $r, l$ 要尽可能满足 $r-l$ 接近 $n \div 2$， 用单调队列维护
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rd read()
#define ll long long
#define R register
using namespace std; const int N = , base1 = , base2 = , mod1 = 1e9 + , mod2 = 1e9 + ; ll po1[N], po2[N], sum1, sum2;
int last[N], cnt[N], n, k, a[N]; struct node {
int id;
ll s1, s2;
}b[N]; inline int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} int cmp(const node &A, const node &B) {
if (A.s1 != B.s1) return A.s1 < B.s1;
if (A.s2 != B.s2) return A.s2 < B.s2;
return A.id < B.id;
} int jud(int x, int y) {
if (b[x].s1 != b[y].s1) return ;
if (b[x].s2 != b[y].s2) return ;
return ;
} void cmin(int &A, int B) {
if (A > B) A = B;
} int Abs(int A) {
return A > ? A : -A;
} int main()
{
n = rd; k = rd;
for (R int i = ; i <= n; ++i)
a[i] = rd;
po1[] = po2[] = ;
for (R int i = ; i <= k; ++i)
po1[i] = po1[i - ] * base1 % mod1,
po2[i] = po2[i - ] * base2 % mod2;
for (R int i = ; i <= n; ++i)
cnt[a[i]]++, last[a[i]] = i;
for (R int i = ; i <= n; ++i) {
(sum1 += po1[a[i]]) %= mod1;
(sum2 += po2[a[i]]) %= mod2;
if (i == last[a[i]])
sum1 = (sum1 - po1[a[i]] * cnt[a[i]] % mod1) % mod1,
sum1 = (sum1 + mod1) % mod1,
sum2 = (sum2 - po2[a[i]] * cnt[a[i]] % mod2) % mod2,
sum2 = (sum2 + mod2) % mod2;
b[i].id = i,
b[i].s1 = sum1,
b[i].s2 = sum2;
}
sort(b + , b + + n, cmp);
ll ans1 = ; int ans2 = n;
int mid = (n + ) >> ;
for (int i = , j = ; i <= n; i = j) {
while (j <= n && jud(i, j)) j++;
ans1 += 1LL * (j - i) * (j - i - ) / ;
for (int l = i, r = i; r < j; ++r) {
while (l < r && b[r].id - b[l].id >= mid) l++;
cmin(ans2, Abs(n - * (b[r].id - b[l].id)));
if (l != i)
cmin(ans2, Abs(n - * (b[r].id - b[l - ].id)));
}
}
printf("%lld %d\n", ans1, ans2);
}