本文共 1849 字，大约阅读时间需要 6 分钟。
通过离线处理，由于线段树不能够动态的扩张，将所有的数都进行永久标号，无视信息的冗余。对于每一个节点，保留对5取余的所有余数的和值，用long long存储。然后根据元素个数进行更新。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include #define MAXN 100005using namespace std;typedef long long Int64;char op[MAXN][5];int num[MAXN], rec[MAXN], idx;map mp;struct Node { int l, r, tot; Int64 a[5];}s[MAXN*4];void build(int p, int l, int r) { s[p].l = l, s[p].r = r, s[p].tot = 0; memset(s[p].a, 0, sizeof (s[p].a)); if (l != r) { int mid = (l + r) >> 1; build(p<<1, l, mid); build(p<<1|1, mid+1, r); }}void push_up(int p) { s[p].tot = s[p<<1].tot + s[p<<1|1].tot; for (int i = 0; i < 5; ++i) { int k = (s[p<<1].tot+i) % 5; s[p].a[k] = s[p<<1].a[k] + s[p<<1|1].a[i]; }}void modify(int p, int pos, int f) { if (s[p].l == s[p].r) { if (f > 0) { s[p].tot = 1, s[p].a[1] = rec[pos-1]; // rec[pos-1]保留的是原来的值 } else { s[p].tot = 0; s[p].a[1] = 0; } } else { int mid = (s[p].l + s[p].r) >> 1; if (pos <= mid) { modify(p<<1, pos, f); } else { modify(p<<1|1, pos, f); } push_up(p); }}int main(){ int N; while (scanf("%d", &N) != EOF) { idx = -1; mp.clear(); for (int i = 1; i <= N; ++i) { scanf("%s", op[i]); if (op[i][0] == 'a') { scanf("%d", &num[i]); rec[++idx] = num[i]; } else if (op[i][0] == 'd') { scanf("%d", &num[i]); rec[++idx] = num[i]; } } sort(rec, rec+idx+1); idx = unique(rec, rec+idx+1) - rec; // 返回的是元素个数 for (int i = 0; i < idx; ++i) { mp[rec[i]] = i + 1; // 对数字进行离散化 } if (idx != -1) { build(1, 1, idx); } for (int i = 1; i <= N; ++i) { if (op[i][0] == 'a') { modify(1, mp[num[i]], 1); } else if (op[i][0] == 'd'){ modify(1, mp[num[i]], -1); } else { printf("%I64d\n", s[1].a[3]); } } } return 0;}
转载于:https://www.cnblogs.com/Lyush/archive/2012/09/19/2693276.html