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);
}