HDU 4737 A Bit Fun：線段樹統計區間 OR 值小於 m 的對數

問題描述

給定長度 n 的數列，詢問有多少對區間 [i, j] 使得該區間所有數的按位 OR 值嚴格小於 m。n ≤ 100,000。

核心觀察

• OR 操作單調不減：a | b ≥ max(a, b)。擴大區間 OR 值不會變小。
• 固定右端點 r，隨著左端點 l 左移，區間 OR 值單調遞增（或不變）。因此存在一個最左邊界 L(r)，使得 [L(r), r] 的 OR < m，而 [L(r)-1, r] 的 OR ≥ m。
• 對每個 r，合法的左端點數為 r - L(r) + 1（若 L(r) 存在）。

線段樹輔助二分

構建線段樹維護區間 OR 值。對固定 r，在 [1, r] 上二分查找最小的 l 使得 OR(l, r) ≥ m。利用線段樹的結構，可在 O(log n) 內完成「找第一個不滿足位置」的操作：從根節點遞歸，優先檢查右子樹，若右子樹 OR 與當前累積 OR 後仍 < m，則進入左子樹並更新累積 OR。

演算法流程

1. 建立線段樹，節點存儲區間 OR 值。
2. 對每個 r = 1..n：
   • 若 a[r] ≥ m，直接跳過（單元素已不合法）。
   • 調用 query(1, r) 找到最左不合法位置 pos（若全合法則 pos=0）。
   • 累加答案 r - pos。

關鍵函數

// 在以 v 為根的子樹中，已知右側累積 OR 為 sum，找最左使總 OR ≥ m 的位置
int get_first(int v, int sum) {
    if (tree[v].l == tree[v].r) return tree[v].l;
    if ((sum | tree[right].value) >= m) return get_first(right, sum);
    return get_first(left, sum | tree[right].value);
}

// 查詢 [1, pos] 中第一個使 OR ≥ m 的位置
int query(int v, int pos) {
    if (tree[v].l == tree[v].r) return tree[v].value;
    int mid = (tree[v].l + tree[v].r) >> 1;
    if (pos <= mid) return query(left, pos);
    int sum = query(right, pos);
    if (sum < m && (sum | tree[left].value) >= m) {
        ans = get_first(left, sum);
    }
    return sum | tree[left].value;
}

複雜度

• 建樹：O(n)。
• 每次查詢：O(log n)。總時間 O(n log n)。
• 空間：O(n)。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;

struct Node { int l, r, val; } tr[MAXN<<2];
int a[MAXN], n, m, ans;

void build(int l, int r, int v) {
    tr[v].l = l; tr[v].r = r;
    if (l == r) { tr[v].val = a[l]; return; }
    int mid = (l+r)>>1;
    build(l, mid, v<<1);
    build(mid+1, r, v<<1|1);
    tr[v].val = tr[v<<1].val | tr[v<<1|1].val;
}

int get_first(int v, int sum) {
    if (tr[v].l == tr[v].r) return tr[v].l;
    if ((sum | tr[v<<1|1].val) >= m) return get_first(v<<1|1, sum);
    return get_first(v<<1, sum | tr[v<<1|1].val);
}

int query(int v, int pos) {
    if (tr[v].l == tr[v].r) return tr[v].val;
    int mid = (tr[v].l + tr[v].r) >> 1;
    if (pos <= mid) return query(v<<1, pos);
    int sum = query(v<<1|1, pos);
    if (sum < m && (sum | tr[v<<1].val) >= m) ans = get_first(v<<1, sum);
    return sum | tr[v<<1].val;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; ++cas) {
        scanf("%d%d", &n, &m);
        for (int i=1;i<=n;i++) scanf("%d", &a[i]);
        build(1, n, 1);
        long long res = 0;
        for (int i=1;i<=n;i++) {
            ans = 0;
            if (a[i] >= m) continue;
            query(1, i);
            res += i - ans;
        }
        printf("Case #%d: %lld\n", cas, res);
    }
    return 0;
}