526互联

【W的AC企划 - 第二期】莫队算法

发布时间 2023-08-07 00:10:22作者: hh2048

往期浏览

讲解

普通莫队：以 \(\mathcal O(N \sqrt N)\) 的复杂度完成 \(Q\) 次询问的离线查询，其中每个分块的大小取 \(\sqrt N=\sqrt {10^5} = 317\) ，也可以使用 ceil((double)n / (int)sqrt(n)) 或者 sqrt(n) 划分。

带修莫队：以 \(\mathcal O(N^\frac{5}{3})\) 的复杂度完成 \(Q\) 次询问的离线查询，其中每个分块的大小取 \(N^\frac{2}{3}=\sqrt\[3]{100000^2}=2154\) （直接取会略快），也可以使用 pow(n, 0.6666) 划分。

二次离线莫队：在普通莫队的基础上，对转移过程中用于维护的某些数据结构也提前离线掉，使得在转移的过程中能过 \(\mathcal O(1)\) 查询，最终将复杂度由普通莫队的乘法 \(\mathcal O(N\sqrt N \cdot P)\) 变为加法 \(\mathcal O(N\sqrt N + P)\) ，其中 \(P\) 表示维护用的某些数据结构的复杂度。

个人封装

由于需要进行一定程度的修改，不符合结构体封装的原则，故没有使用结构体。

普通莫队封装

signed main() {
    int n;
    cin >> n;
    
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    
    int q;
    cin >> q;
    vector<array<int, 3>> query(q + 1);
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        query[i] = {l, r, i};
    }
    
    int Knum = n / min<int>(n, sqrt(q)); // 计算块长
    vector<int> K(n + 1);
    for (int i = 1; i <= n; i++) { // 固定块长
        K[i] = (i - 1) / Knum + 1;
    }
    sort(query.begin() + 1, query.end(), [&](auto x, auto y) {
        if (K[x[0]] != K[y[0]]) return x[0] < y[0];
        if (K[x[0]] & 1) return x[1] < y[1];
        return x[1] > y[1];
    });
    
    int l = 1, r = 0, val = 0;
    vector<int> ans(q + 1);
    for (int i = 1; i <= q; i++) {
        auto [ql, qr, id] = query[i];
        
        auto add = [&](int x) -> void {
            
        };
        
        auto del = [&](int x) -> void {
            
        };
        
        while (l > ql) add(w[--l]);
        while (r < qr) add(w[++r]);
        while (l < ql) del(w[l++]);
        while (r > qr) del(w[r--]);
        ans[id] = val;
    }
    
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << endl;
    }
}

带修莫队封装

signed main() {
    int n, q;
    cin >> n >> q;
    
    vector<int> w(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    
    vector<array<int, 4>> query = {{}}; // {左区间, 右区间, 累计修改次数, 下标}
    vector<array<int, 2>> modify = {{}}; // {修改的值, 修改的元素下标}
    for (int i = 1; i <= q; i++) {
        char op;
        cin >> op;
        if (op == 'Q') {
            int l, r;
            cin >> l >> r;
            query.push_back({l, r, (int)modify.size() - 1, (int)query.size()});
        } else {
            int idx, w;
            cin >> idx >> w;
            modify.push_back({w, idx});
        }
    }
    
    int Knum = 2154; // 计算块长
    vector<int> K(n + 1);
    for (int i = 1; i <= n; i++) { // 固定块长
        K[i] = (i - 1) / Knum + 1;
    }
    sort(query.begin() + 1, query.end(), [&](auto x, auto y) {
        if (K[x[0]] != K[y[0]]) return x[0] < y[0];
        if (K[x[1]] != K[y[1]]) return x[1] < y[1];
        return x[3] < y[3];
    });
    
    int l = 1, r = 0, val = 0;
    int t = 0; // 累计修改次数
    vector<int> ans(query.size());
    for (int i = 1; i < query.size(); i++) {
        auto [ql, qr, qt, id] = query[i];
        
        auto add = [&](int x) -> void {

        };
        
        auto del = [&](int x) -> void {

        };
        
        auto time = [&](int x, int l, int r) -> void {
            
        };
        
        while (l > ql) add(w[--l]);
        while (r < qr) add(w[++r]);
        while (l < ql) del(w[l++]);
        while (r > qr) del(w[r--]);
        while (t < qt) time(++t, ql, qr);
        while (t > qt) time(t--, ql, qr);
        ans[id] = val;
    }
    
    for (int i = 1; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
}

题单

  1. 86D - Powerful array：普通莫队
  2. 220B - Little Elephant and Array：普通莫队
  3. 617E - XOR and Favorite Number：普通莫队
  4. past202212_n - Sequence and Function 普通莫队
  5. 940F - Machine Learning：带修莫队、离散化

部分题解

题单第一题 [86D - Powerful array]

题意：记 \([L,R]\) 区间内元素 \(X\) 出现了 \(cnt_X\) 次，计算 \(cnt_X*cnt_X*X\) 之和。

思路：

原答案 \(cnt_X^2*X\) ，多出现一次，\(cnt_X >>> cnt_X+1\) ，新答案 \((cnt_X^2+2*cnt_X+1)*X\) ，直接将答案补上差值即可。

题单第二题 [220B - Little Elephant and Array]

题意：统计 \([L,R]\) 区间内有多少个元素 \(X\) 恰好出现了 \(X\) 次。

思路：

对于读入的一个新的数字 \(a[x]\) ，使用 \(cnt\) 数组统计其已经出现的次数，如果恰好为 \(a[x]\) 次则将答案 \(+1\) 。

注意点：

在统计时需要注意，加入前和加入后需要分别判断。

由于 \(a_i\) 的取值范围是 \(10^9\) ，所以 \(cnt\) 数组的大小需要注意，有两种解法，一是使用 \(\tt unordered\_map\) （因为普通 \(\tt map\) 会使复杂度退化为 \(\mathcal O(N*\sqrt N * logN)\) ，这是不可接受的；二是我们发对于 \(a_i>N\) 的情况根本不需要统计，又由于 \(N\) 的范围是正常的 \(10^5\) ，所以在 add,del 函数第一行加个判断就可以了

题单第三题 [617E - XOR and Favorite Number]

题意：统计 \([L,R]\) 区间内有多少个子区间 \([l,r]\) 满足异或和为 \(K\) 。

思路：

首先将问题转化为“ 对于固定的区间[L,R]，询问其中有多少个不同的子区间满足异或和为K ”，关于这一点，有一个很著名的结论，即使用前缀和异或数组 \(sum\) ：当一个区间 \([l,r]\) 异或和为 \(K\) 时，\(sum[l-1] \bigoplus sum[r] = K\)。

由这一点出发，我们发现对于 \(sum[r]\) ，能和其组合产生目标子区间的数量即为 \(sum[l-1]\) 的数量。又由于上述式子，\(sum[l-1]\) 可以被转化为 \(sum[r] \bigoplus K\) ，所以能和 \(sum[r]\) 组合产生目标子区间的数量进一步转化为 \(sum[r] \bigoplus K\) 的数量。

至此，该问题完全转化为只与 \(sum[r]\) 相关。

注意点：

由于是异或和，虽然题目中所给 \(a_i\) 的取值范围是 \(10^6\) ，但是最高是能达到 \(2^{20}=1048576\) 的，所以 \(cnt\) 数组至少要开 20 << 1 + 7 。

由于异或和的结论是与 \(L-1\) 相关，所以在读入时就要减去这个 \(1\) 。