1. POI2015 - Podział naszyjnika
考虑对每个位置附一个随机权值，保证序列中所有等于某个数的位置权值异或和为 \(0\)。则一种划分合法当且仅当两个区间异或和都为 \(0\)，相当于找到一个区间 \([L,R]\) 异或和为 \(0\)。于是用 umap 记录前缀异或和即可。第二问把每个相同的前缀异或和放到一个 vector 里双指针即可。注意 \([1,i],[i+1,n]\) 之类的划分可能会被统计两次，解决方法是不统计所有以 \(n\) 结尾的区间。
点击查看代码
//P3587
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
void solve();int main(){ solve(); return 0; }
const int N = 1e6 + 10;
int n, k, a[N], cnt, mx;
ll xom[N], val[N], ans;
unordered_map<ll, int> mp;
vector<int> g[N];
int cl(int x, int y){
return min(y - x, x + n - y);
}
mt19937 rng(time(0));
uniform_int_distribution<long long>gen(1,0x3f3f3f3f3f3f3f3f);
void solve(){
srand(unsigned(time(NULL)));
mp[0] = ++ cnt;
g[mp[0]].push_back(0);
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++ i){
scanf("%d", &a[i]);
val[i] = gen(rng);
xom[a[i]] ^= val[i];
}
for(int i = 1; i <= n; ++ i){
val[i] ^= xom[a[i]];
xom[a[i]] = 0;
val[i] ^= val[i-1];
if(!mp[val[i]]){
mp[val[i]] = ++ cnt;
}
g[mp[val[i]]].push_back(i);
}
for(int i = 1; i <= cnt; ++ i){
int x = g[i].size();
if(mp[val[n]] == i){
-- x;
}
ans += (ll)x * (x-1) / 2;
int pr = 0;
for(int j = 1; j < x; ++ j){
while(pr < j && cl(g[i][pr], g[i][j]) < cl(g[i][pr+1], g[i][j])){
++ pr;
}
mx = max(mx, cl(g[i][pr], g[i][j]));
}
}
printf("%lld %d", ans, n - mx - mx);
}