HDOJ 4288 Coder（線段樹）

[cpp] 
/*
線段樹很強大，這個應該也屬於區間處理、多次查詢的問題，所以要用到線段樹解決。
sum[]分別表示區間內%5余數之和，cnt表示區間內總個數
首先離散化，然後建立線段樹（讓線段樹中l,r與A[]數組相對應起來），然後添加和刪除元素即可
*/ 
 
 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
const __int64 nMax = 100007; 
__int64 N; 
struct Node 
{ 
    char opr[5]; 
    __int64 a; 
    Node(){} 
    Node(char *_opr, __int64 _a) 
    { 
        memcpy(opr, _opr, sizeof(opr)); 
        a = _a; 
    } 
}node[nMax]; 
struct Tree 
{ 
    __int64 l, r; 
    __int64 sum[5]; 
    __int64 cnt; 
}tree[nMax * 4]; 
__int64 A[nMax]; 
__int64 cnt; 
 
int cmp(const void *a, const void *b) 
{ 
    __int64 *pa = (__int64 *) a; 
    __int64 *pb = (__int64 *) b; 
    return *pa - *pb; 
} 
 
void build(__int64 rt, __int64 l, __int64 r) 
{ 
    if(l < r) 
    { 
        __int64 mid = (l + r) / 2; 
        build(rt * 2, l, mid); 
        build(rt * 2 + 1, mid + 1, r); 
    } 
    tree[rt].l = l; 
    tree[rt].r = r; 
    tree[rt].cnt = 0; 
    memset(tree[rt].sum, 0, sizeof(tree[rt].sum)); 
} 
 
void add(__int64 rt, __int64 a) 
{ 
    if(tree[rt].l == tree[rt].r) 
    { 
        tree[rt].cnt = 1; 
        tree[rt].sum[1] = a; 
        return; 
    } 
    __int64 mid = (tree[rt].l + tree[rt].r) / 2; 
    if(a <= A[mid]) 
        add(rt * 2, a); 
    else 
        add(rt * 2 + 1, a); 
    tree[rt].cnt = tree[rt * 2].cnt + tree[rt * 2 + 1].cnt; 
    __int64 i; 
    memset(tree[rt].sum, 0, sizeof(tree[rt].sum)); 
    for(i = 0; i < 5; ++ i) 
    { 
        tree[rt].sum[i] += tree[rt * 2].sum[i]; 
        tree[rt].sum[(tree[rt * 2].cnt + i) % 5] += tree[rt * 2 + 1].sum[i]; 
    } 
} 
 
void del(__int64 rt, __int64 a) 
{ 
    if(tree[rt].l == tree[rt].r) 
    { 
        tree[rt].cnt = 0; 
        tree[rt].sum[1] = 0; 
        return; 
    } 
    __int64 mid = (tree[rt].l + tree[rt].r) / 2; 
    if(a <= A[mid]) 
        del(rt * 2, a); 
    else 
        del(rt * 2 + 1, a); 
    tree[rt].cnt = tree[rt * 2].cnt + tree[rt * 2 + 1].cnt; 
    __int64 i; 
    memset(tree[rt].sum, 0, sizeof(tree[rt].sum)); 
    for(i = 0; i < 5; ++ i) 
    { 
        tree[rt].sum[i] += tree[rt * 2].sum[i]; 
        tree[rt].sum[(tree[rt * 2].cnt + i) % 5] += tree[rt * 2 + 1].sum[i]; 
    } 
} 
 
int main() 
{ 
    //freopen("e://data.in", "r", stdin) 
    while(scanf("%I64d", &N) != EOF) 
    { 
        __int64 i, j; 
        char opr[5]; 
        __int64 a; 
        cnt = 0; 
        for(i = 0; i < N; ++ i) 
        { 
            scanf("%s", opr); 
            if(opr[0] == 'a') 
            { 
                scanf("%I64d", &a); 
                A[cnt ++] = a; 
            } 
            else if(opr[0] == 'd') 
            { 
                scanf("%I64d", &a); 
            } 
            else a = 0; 
            node[i] = Node(opr, a); 
        } 
        qsort(A, cnt, sizeof(A[0]), cmp); 
        for(i = 1, j = 1; i < cnt; ++ i) 
            if(A[i] != A[i - 1]) 
                A[j ++] = A[i]; 
        cnt = j; www.2cto.com
        build(1, 0, cnt - 1); 
        for(i = 0; i < N; ++ i) 
        { 
            if(node[i].opr[0] == 'a') 
                add(1, node[i].a); 
            else if(node[i].opr[0] == 'd') 
                del(1, node[i].a); 
            else 
                printf("%I64d\n", tree[1].sum[3]); 
        } 
    } 
    return 0; 
}