P3587 题解

一道哈希好题

分析

首先发现这个环就是个烟雾弹，因为两段区间中必有一段且仅有一段在原数列上连续，且结尾下标 $\in [1, n-1]$。于是就转化成了序列问题。

其次来考虑如何快速判断一段区间是否合法。考虑异或哈希，给每个位置赋权，使得每种颜色的异或和为 $0$。只要权值足够随机，哈希冲突的概率应该是极小的。这样一来，一段区间 $[l,r]$ 合法的充要条件就是 $\bigoplus_{i=l}^rw_i=0$，如果定义 $sum_0=0,sum_i=\bigoplus_{j=1}^iw_j$，亦即 $sum_r=sum_{l-1}$。

有了这个式子，第一问就简单了，哈希维护即可。

对于第二个式子，考虑二分求最值。令 check(int x) 返回长度差 $\le$ x 的方案数。第一问可以用这个函数求，第二问也可以用这个解决。注意到每个函数中合法的区间长度是连续的，于是用双指针即可。

代码

#include <bits/stdc++.h>
#define int long long
#define loop(i, a, b) for(int i = (a) ; i <= (int)(b) ; i++)
#define rloop(i, a, b) for(int i = (a) ; i >= (int)(b) ; i--)
#define chkmax(a, b) (a = max(a, (b)))
#define chkmin(a, b) (a = min(a, (b)))
#define mid (((l) + (r)) >> 1)
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N = 1e6 + 5;
int n, k, a[N], w[N], sum[N], st[N], ed[N], b[N], h[N];
int count(int x) {
    int l = 0, r = -1, cnt = 0, lenl = (n - x + 1) / 2, lenr = (n + x) / 2;
    loop(i, 0, n) h[i] = 0;
    loop(i, 1, n - 1) {
        while(r < i - lenl) h[sum[++r]]++;
        while(l < i - lenr) h[sum[l++]]--;
        cnt += h[sum[i]];
    }
    return cnt;
}
void discretize(int n, int a[]) {
    vector<int> vec;
    unordered_map<int, int> mp;
    loop(i, 0, n) vec.push_back(a[i]);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    loop(i, 0, vec.size() - 1) mp[vec[i]] = i;
    loop(i, 0, n) a[i] = mp[a[i]];
}
void solve() {
    mt19937_64 gen(350234);
    uniform_int_distribution<int> rd(0, 0x3f3f3f3f3f3f3f3f);
    cin >> n >> k;
    loop(i, 1, n) {
        cin >> a[i];
        w[i] = rd(gen);
        ed[a[i]] = i, b[a[i]] ^= w[i];
        if(!st[a[i]]) st[a[i]] = i;
    }
    loop(i, 1, k) w[ed[i]] ^= b[i];
    loop(i, 1, n) sum[i] = sum[i - 1] ^ w[i];
    discretize(n, sum);
    int ans1 = count(n - 2);
    int l = -1, r = n - 1;
    while(l + 1 < r) (count(mid) ? r : l) = mid;
    cout << ans1 << ' ' << r << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // int t; cin >> t; while(t--)
    solve();
    return 0;
}