HDU 4288 Coder 【线段树+离线处理+离散化】

题意略。

离线处理，离散化。然后就是简单的线段树了。需要根据mod 5的值来维护。具体看代码了。

/*    线段树+离散化+离线处理*/#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;#define N 100010ll sum[N<<2][5];int a[N], n, m, cnt[N<<2];struct node {    char c;    int x;} q[N];void Up(int rt) {    cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];    for (int i=0; i<5; i++)        sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][(i-cnt[rt<<1]%5+5)%5];}void add(int idx, int val, int l, int r, int rt) {    if (l == r) {        cnt[rt] = 1;        sum[rt][1] = val;        return ;    }    int mid = (l + r) >> 1;    if (idx <= mid) add(idx, val, l, mid, rt<<1);    else add(idx, val, mid+1, r, rt<<1|1);    Up(rt);}void del(int idx, int l, int r, int rt) {    if (l == r) {        sum[rt][1] = cnt[rt] = 0;        return ;    }    int mid = (l + r) >> 1;    if (idx <= mid) del(idx, l, mid, rt<<1);    else del(idx, mid+1, r, rt<<1|1);    Up(rt);}int main() {    char s[10];    while (scanf("%d", &n) == 1) {        m = 0;        for (int i=0; i<n; i++) {            scanf(" %s", s);            q[i].c = s[0];            if (s[0] != 's') {                scanf("%d", &q[i].x);                a[m++] = q[i].x;            }        }        sort(a, a+m);        m = unique(a, a+m) - a;        memset(cnt, 0, sizeof(cnt));        memset(sum, 0, sizeof(sum));        int pos;        for (int i=0; i<n; i++) {            if (q[i].c == 's') printf("%I64d\n", sum[1][3]);            else {                pos = lower_bound(a, a+m, q[i].x) - a + 1;                if (q[i].c == 'a') add(pos, q[i].x, 1, m, 1);                else del(pos, 1, m, 1);            }        }    }    return 0;}