HDU 4288：離線處理 + 線段樹維護下標模 5 和查詢

題目大意

動態集合支持三操作：add x 插入、del x 刪除、sum 查詢。查詢定義：將集合元素升序排列 a1 < a2 < ... < ak，求下標模 5 為 3 的元素之和（即 a3 + a8 + a13 + ...）。N ≤ 1e5。

核心難點：動態下標維護

插入/刪除會導致後續元素下標偏移，直接維護困難。離線思想：
1. 收集所有出現過的 x，排序去重 → 坐標壓縮。
2. 線段樹葉子對應壓縮後的值，標記是否存在（0/1）。
3. 節點維護：cnt（該區間存在元素個數）、sum[5]（下標模 5 為 0..4 的元素和）。

線段樹合併邏輯

左子區間下標不變，右子區間下標整體偏移 left.cnt。
合併公式：
for i in 0..4: parent.sum[(i + left.cnt) % 5] += right.sum[i]
parent.cnt = left.cnt + right.cnt

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 500000 + 10;
int n, len;
char str[MAXN][10];
int num[MAXN], sorted[MAXN];
struct Node {
    int l, r, cnt;
    LL sum[5];
} tree[MAXN * 4];
void build(int l, int r, int idx) {
    tree[idx].l = l; tree[idx].r = r; tree[idx].cnt = 0;
    memset(tree[idx].sum, 0, sizeof(tree[idx].sum));
    if (l != r) {
        int mid = (l + r) >> 1;
        build(l, mid, idx<<1);
        build(mid+1, r, idx<<1|1);
    }
}
void pushup(int idx) {
    int lc = idx<<1, rc = idx<<1|1;
    tree[idx].cnt = tree[lc].cnt + tree[rc].cnt;
    memset(tree[idx].sum, 0, sizeof(tree[idx].sum));
    for (int i = 0; i < 5; i++)
        tree[idx].sum[i] = tree[lc].sum[i];
    for (int i = 0; i < 5; i++)
        tree[idx].sum[(i + tree[lc].cnt) % 5] += tree[rc].sum[i];
}
void update(int idx, int pos, int val, bool add) {
    if (tree[idx].l == tree[idx].r) {
        tree[idx].cnt = add ? 1 : 0;
        tree[idx].sum[1] = add ? val : 0; // 單元素下標為 1
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (pos <= mid) update(idx<<1, pos, val, add);
    else update(idx<<1|1, pos, val, add);
    pushup(idx);
}
int main() {
    while (~scanf("%d", &n)) {
        len = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", str[i]);
            if (str[i][0] != 's') {
                scanf("%d", &num[i]);
                sorted[len++] = num[i];
            }
        }
        sort(sorted, sorted + len);
        len = unique(sorted, sorted + len) - sorted;
        build(1, len, 1);
        for (int i = 0; i < n; i++) {
            if (str[i][0] == 'a') {
                int pos = lower_bound(sorted, sorted + len, num[i]) - sorted + 1;
                update(1, pos, num[i], true);
            } else if (str[i][0] == 'd') {
                int pos = lower_bound(sorted, sorted + len, num[i]) - sorted + 1;
                update(1, pos, num[i], false);
            } else {
                printf("%lld\n", tree[1].sum[3]);
            }
        }
    }
    return 0;
}

關鍵點總結

• 離線座標壓縮將動態值域映射到固定範圍，支持線段樹。
• 節點維護 sum[5] 而非單一值，巧妙處理下標偏移。
• 查詢直接讀取根節點 sum[3]，O(1)。
• 更新 O(log N)，總體 O(N log N)。