题解：P14567 【MX-S12-T2】区间

· · 题解

话说我看到这个题的第一眼感觉是个消消乐，没想到是个小小乐。

本题解介绍三种方法和一种经典的哈希模型:

异或哈希

顾名思义就是基于异或的哈希，那么我们先思考异或有什么性质:

  1. a_i \oplus a_i = 0
  3. a_i \oplus a_j = a_j \oplus a_i

那么我们可以给每一个数字一个哈希值，然后进行配对。

下面我们举一个例子:

给定一个 1 \sim n 的一个排列，要求是否存在一个连续的长度大小为 k 区间 [L,R] 使得将区间从小到大排序后正好是1 \sim k。（n \le 10^4）

上述例子存在线性的做法，但是在此介绍异或哈希：

首先对于每个数字赋一个随机权值，然后求出来前 1 \sim k 的数字做一次前缀异或和，然后对于原序列做一遍前缀异或，然后枚举 l,r 直接暴力即可。

下面开始介绍我们这一个题目:

首先是看到要求价值最小的一个区间使区间内的数字在区间外都不存在。

所以我们可以直接考虑预处理出来每个颜色的左端点和右端点。

考虑存在多个区间存在包含关系，下面我们考虑一个贪心:

对于多个相互包含的区间，选择最小的那个区间的价值一定是这些里面最优秀的。

这个证明很显然，肯定对于每一个 v_i 与他相乘的数字越小肯定更好所以距左端点越近越好。

此时我们的有效区间两两相离，所以我们只要暴力的对每个区间扫一边即可。

方法1 异或哈希

就是对于每个 c 随机赋权，然后前缀存 umap 里面判断一下，然后找到相离的区间计算一下就可以了。

mt19937_64 rnd(time(0));
int n, v[N], f[N];
ll t[N],ans = LLONG_MAX;
vector<int> p[N];
unordered_map<ll, int> h;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1, x; i <= n; i++) cin >> x, p[x].push_back(i);
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 1; i <= n; i++) cin >> f[i];
    for (int i = 1; i <= n; i++)
        if (p[i].size() > 1) {
            for (auto it = next(p[i].begin()); it != p[i].end(); it++) {
                ll now = rnd();
                t[*p[i].begin()] -= now;
                t[*it] += now;
            }
        }
    h[0] = 0;
    int mx = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        t[i] += t[i - 1];
        if (h.count(t[i])) {
            int l = h[t[i]] + 1, r = i;
            if (l > mx) {
                mx = l;
                ll sum = 0;
                for (int j = l; j <= r; j++) sum += 1ll * v[j] * f[j - l + 1], cnt++;
                ans = min(ans, sum);
            }
        }
        h[t[i]] = i;
    }
    cout << ans;
}

方法2 双指针

我们很明显发现区间只有包含和相离两种情况，此时我们可以倒着扫 l ，然后如果有一个 r 符合条件就跳到 r 处进行计算，显然是 O(n) 的。