TIOJ 2027：腳步鬆散

TIOJ 2027：腳步鬆散

題目大意：給你 $a_1\sim a_n$，請你輸出有多少對 $i<j$，使得 $a_i \oplus a_j \geq \max(a_i\sim a_j)$。

解法：首先我們可以用 $\text{trie}$ 計算出有多少個 $\text{trie}$ 裡的元素 $k$，使得 $k\oplus x \geq mx$，然後我們就可以開始分治，左右區間都遞迴完後，可以枚舉最大值在右邊的情況，與在左邊的情況，最終複雜度 $O(n\times\log(n)\times\log(C))$。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 3e5 + 5;
const int TSIZ = 24 * SIZE;

int n;
ll ans;
int a[SIZE];
int cnt, to[TSIZ][2], num[TSIZ];

void Insert (int x) {
    int now = 0;
    for (int i = 23; i >= 0; i--) {
        bool b = x >> i & 1;
        if (!to[now][b]) to[now][b] = ++cnt;
        now = to[now][b];
        num[now]++;
    }
}

int query (int x, int mx) {
    int now = 0, re = 0;
    for (int i = 23; i >= 0; i--) {
        bool b = x >> i & 1;
        bool c = mx >> i & 1;
        if (c == 0) {
            if (to[now][b ^ 1]) re += num[to[now][b ^ 1]];
            if (!to[now][b]) return re;
            now = to[now][b];
        } else {
            if (!to[now][b ^ 1]) return re;
            now = to[now][b ^ 1];
        }
    }
    return re + num[now];
}

void divide (int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    divide (l, mid);
    divide (mid + 1, r);
    int lp = mid, rp = mid + 1, mx = -1;
    for (int i = mid + 1, mx, lp = mid; i <= r;) {
        mx = a[i];
        while (lp >= l && a[lp] <= mx) Insert (a[lp--]);
        int R = i;
        while (R <= r && a[R] <= mx) ans += query (a[R++], mx);
        i = R;
    }
    FOR (i, 0, cnt) to[i][0] = to[i][1] = num[i] = 0;
    cnt = 0;
    for (int i = mid, mx, rp = mid + 1; i >= l;) {
        mx = a[i];
        while (rp <= r && a[rp] < mx) Insert (a[rp++]);
        int L = i;
        while (L >= l && a[L] <= mx) ans += query (a[L--], mx);
        i = L;
    }
    FOR (i, 0, cnt) to[i][0] = to[i][1] = num[i] = 0;
    cnt = 0;
}

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> a[i];
    divide (1, n);
    cout << ans << '\n';
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！