2022 FB Hackercup Round2

比賽時只寫出 A1、 D1，A2是賽後補的。進不了 Round3 ，不過名次應該可以拿到 T-shirt。

感想：怎麼兩題都線段樹 🤣

Problem A: Perfectly Balanced

Prob A2

題目

給定一個數列，要支援以下兩種操作：

1. 單點修改：修改單個數字
2. 區間查詢：確認該區間是否可以分成兩半，其中一半剛好和另一半只差一個數字。

Ex:

1. [2, 2, 3] 可以被分成 [2] 和 [2, 3]
2. [1, 3, 1, 1, 1] 可以被分成 [1, 3, 1] 和 [1, 1]
3. [1, 2, 2, 1] 沒辦法

大概作法

1. 線段樹區間和。
2. 把每個數字都對應到 $[0, P)$ 之間的數字。
3. 區間和就是這些數字的和。
4. 要檢查兩個區間是否只差一個數字，就是把區間和相減後，看這個差是不是數字的對應。
5. 當然，可以設置好幾組對應來降低壞掉的機率。
6. 題目有一部份重點會是計算機率，P越大或組數越多，壞掉的機率就越低。

Code

#include <bits/stdc++.h>

using namespace std;

// gen [0, upper)*n
// usage:
//  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//  auto v1 = genRand(rng, 100000, 10000000);
//  auto v2 = genRand(rng, 100000, 12343212);
vector<int64_t> genRand(mt19937_64& rng, size_t n, int64_t upper) {
    uniform_int_distribution<int64_t> valDistr(0, upper - 1);
    uniform_int_distribution<int64_t> rangDistr(0, n - 1);

    set<int64_t> vals;
    while (vals.size() < n) {
        vals.insert(valDistr(rng));
    }

    vector<int64_t> ret(vals.begin(), vals.end());
    for (size_t i = 0; i < n; ++i) {
        swap(ret[i], ret[rangDistr(rng)]);
    }

    return vector<int64_t>(vals.begin(), vals.end());
}

struct ZKWTree {
    vector<int64_t> data;
    size_t base;

    ZKWTree(size_t n) {
        base = 1 << __lg(n + 5) + 1;
        data = vector<int64_t>(base << 1, 0);
    }

    // x in [0, n)
    void update(size_t x, int64_t v) {
        ++x;  // 0-base to 1-base
        x += base;
        data[x] = v;
        for (x >>= 1; x; x >>= 1) {
            data[x] = data[x << 1] + data[(x << 1) | 1];
        }
    }

    // [l, r]
    // l, r in [0, n)
    int64_t query(size_t l, size_t r) const {
        ++l, ++r;  // 0-base to 1-base
        int64_t ans = 0;
        for (l += base - 1, r += base + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) {
                ans += data[l ^ 1];
            }
            if (r & 1) {
                ans += data[r ^ 1];
            }
        }
        return ans;
    }
};

int main() {
    // init
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // prepare random mapper
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    const int hashNum = 4;
    vector<int64_t> hashs[hashNum];
    set<int64_t> hashSets[hashNum];
    for (int lx = 0; lx < hashNum; ++lx) {
        hashs[lx] = genRand(rng, 1000001, 1e9 + 7);
        hashSets[lx] = set<int64_t>(hashs[lx].begin(), hashs[lx].end());
    }

    int T;
    cin >> T;
    for (int lt = 1; lt <= T; ++lt) {
        size_t N;
        cin >> N;

        vector<ZKWTree> trees(hashNum, ZKWTree(N));

        vector<int> xs(N);
        for (int& x : xs) {
            cin >> x;
        }

        for (int lx = 0; lx < hashNum; ++lx) {
            for (int i = 0; i < N; ++i) {
                trees[lx].update(i, hashs[lx][xs[i]]);
            }
        }

        size_t Q;
        cin >> Q;
        int ans = 0;
        for (int lq = 0; lq < Q; ++lq) {
            int tp, a, b;
            cin >> tp >> a >> b;
            if (tp == 1) {
                for (int lx = 0; lx < hashNum; ++lx) {
                    trees[lx].update(a - 1, hashs[lx][b]);
                }
            } else {
                --a, --b;  // 1-base to 0-base

                if ((b - a) % 2 == 1) {
                    continue;
                }

                int m = (a + b) / 2;

                // [a, m], [m+1, b]
                bool ok1 = true;
                for (int lx = 0; lx < hashNum; ++lx) {
                    int64_t v =
                        trees[lx].query(a, m) - trees[lx].query(m + 1, b);
                    if (hashSets[lx].find(v) == hashSets[lx].end()) {
                        ok1 = false;
                        break;
                    }
                }

                // [a, m-1], [m, b]
                bool ok2 = true;
                for (int lx = 0; lx < hashNum; ++lx) {
                    int64_t v =
                        trees[lx].query(m, b) - trees[lx].query(a, m - 1);
                    if (hashSets[lx].find(v) == hashSets[lx].end()) {
                        ok2 = false;
                        break;
                    }
                }

                if (ok1 || ok2) {
                    ++ans;
                }
            }
        }

        cout << "Case #" << lt << ": " << ans << endl;
    }

    return 0;
}

Problem D1: Work-Life Balance - Chapter 1

Prob D1

題目整理

給定一個 {1, 2, 3} 數列，支援以下操作：

1. 修改一個數字成 {1, 2, 3}
2. 查詢兩個區間：查詢經過有限次交換兩個數字次數後，使兩區間和一樣。

Ex:

1. [1, 2] [3] 可以不需要經過交換。
2. [1, 2] [1] 經過一次交換，可變成 [1, 1] 和 [2]。
3. [1, 1, 1] [2] 無法經過有限次交換後和一樣。

大概作法

1. 開三顆線段樹，紀錄區間 1, 2, 3 的個數。
2. 重點：交換 (1, 2), (2, 3) 可以換取 2 的差異，交換 (1, 3) 可以換取 4 差異。
3. 用換硬幣 greedy 的方式處理。
4. 重點在處理 Case

Code

#include <bits/stdc++.h>

using namespace std;

struct ZKWTree {
    vector<int> data;
    int base;
    ZKWTree(int n) {
        base = 1 << __lg(n + 5) + 1;
        data = vector<int>(base << 1, 0);
    }

    void update(int x, int v) {
        ++x;  // 0-base to 1-base
        for (int i = x + base; i; i >>= 1) {
            data[i] += v;
        }
    }

    // [l, r]
    int query(int l, int r) {
        ++l, ++r;  // 0-base to 1-base
        int ans = 0;
        for (l += base - 1, r += base + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) ans += data[l ^ 1];
            if (r & 1) ans += data[r ^ 1];
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int lt = 1; lt <= T; ++lt) {
        int N, M;
        cin >> N >> M;
        vector<int> arr(N);
        for (int& v : arr) {
            cin >> v;
        }

        ZKWTree tree[3] = {
            ZKWTree(N),
            ZKWTree(N),
            ZKWTree(N),
        };

        // cout << "zkw ok" << endl;

        for (int i = 0; i < N; ++i) {
            // cout << arr[i] - 1 << endl;

            tree[arr[i] - 1].update(i, 1);
        }

        int64_t ans = 0;
        for (int lq = 0; lq < M; ++lq) {
            int X, Y, Z;
            cin >> X >> Y >> Z;
            --X;  // to 0-base

            tree[arr[X] - 1].update(X, -1);
            arr[X] = Y;
            tree[arr[X] - 1].update(X, 1);

            int leftCnt1 = tree[0].query(0, Z - 1);
            int leftCnt2 = tree[1].query(0, Z - 1);
            int leftCnt3 = tree[2].query(0, Z - 1);

            int lval = leftCnt1 + leftCnt2 * 2 + leftCnt3 * 3;

            int rightCnt1 = tree[0].query(Z, N - 1);
            int rightCnt2 = tree[1].query(Z, N - 1);
            int rightCnt3 = tree[2].query(Z, N - 1);

            int rval = rightCnt1 + rightCnt2 * 2 + rightCnt3 * 3;

            int lr = lval - rval;

            if (lr < 0) {
                swap(leftCnt1, rightCnt1);
                swap(leftCnt2, rightCnt2);
                swap(leftCnt3, rightCnt3);
                lr = -lr;
            }

            // cout << leftCnt1 << "," << leftCnt2 << "," << leftCnt3 << endl;
            // cout << rightCnt1 << "," << rightCnt2 << "," << rightCnt3 <<
            // endl;

            // lr >= 0
            int q = 0;

            // 3 <-> 1
            int mv31 = min(min(leftCnt3, rightCnt1), lr / 4);

            leftCnt3 -= mv31;
            rightCnt3 += mv31;
            leftCnt1 += mv31;
            rightCnt1 -= mv31;

            lr -= mv31 * 4;
            q += mv31;

            // 3 <-> 2

            int mv32 = min(min(leftCnt3, rightCnt2), lr / 2);

            leftCnt3 -= mv32;
            rightCnt3 += mv32;
            leftCnt2 += mv32;
            rightCnt2 -= mv32;

            lr -= mv32 * 2;
            q += mv32;

            // 2 <-> 1

            int mv21 = min(min(leftCnt2, rightCnt1), lr / 2);

            leftCnt2 -= mv21;
            rightCnt2 += mv21;
            leftCnt1 += mv21;
            rightCnt1 -= mv21;

            lr -= mv21 * 2;
            q += mv21;

            if (lr == 0) {
                ans += q;
            } else {
                q = -1;
                --ans;
            }
            // cout << "mv31 = " << mv31 << ", mv32 = " << mv32
            //      << ", mv21 = " << mv21 << endl;
            // cout << "Q = " << q << endl;
        }

        cout << "Case #" << lt << ": " << ans << endl;
    }

    return 0;
}