线段树(多棵) HDOJ 4288 Coder

题意：集合，add x, del x, 求和

分析：首先，暴力可以过这题。用上线段树能大大降低时间的消耗，具体就是类似开了5棵线段树，每个节点都有5个空间，表示该区间的id%5后的和，区间合并右边的id‘ = i + leftnum，子节点要存到sum[o][1]表示%5=1。还需要对数据离线离散化。

//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef long long ll;
const int N = 1e5 + 5;
ll sum[N<<2][5];
int cnt[N<<2];
int x[N], X[N];
char str[N][3];

void push_up(int o) {
    cnt[o] = cnt[o<<1] + cnt[o<<1|1];
    int lnum = cnt[o<<1];
    for (int i=0; i<5; ++i) {
        sum[o][i] = sum[o<<1][i];
    }
    for (int i=0; i<5; ++i) {
        sum[o][(i+lnum)%5] += sum[o<<1|1][i];
    }
}
void updata(int p, int op, int l, int r, int o) {
    if (l == r) {
        cnt[o] = op;
        sum[o][1] = op * X[l-1];
        return ;
    }
    int mid = l + r >> 1;
    if (p <= mid) {
        updata (p, op, lson);
    } else {
        updata (p, op, rson);
    }
    push_up (o);
}

int main() {
    int n, m;
    char str[N][3];
    while (scanf ("%d", &n) == 1) {
        m = 0;
        for (int i=0; i<n; ++i) {
            scanf ("%s", str[i]);
            if (str[i][0] != 's') {
                scanf ("%d", &x[i]);
                X[m++] = x[i];
            }
        }
        std::sort (X, X+m);
        m = std::unique (X, X+m) - X;
        memset (sum, 0, sizeof (sum));
        memset (cnt, 0, sizeof (cnt));
        for (int i=0; i<n; ++i) {
            int pos = std::upper_bound (X, X+m, x[i]) - X;
            if (str[i][0] == 'a') {
                updata (pos, 1, 1, m, 1);
            } else if (str[i][0] == 'd') {
                updata (pos, 0, 1, m, 1);
            } else {
                printf ("%I64d
", sum[1][3]);
            }
        }
    }

    return 0;
}

线段树(多棵) HDOJ 4288 Coder

相关推荐