HDU 4288 Coder 【线段树+离线处理+离散化】
题意略。
离线处理，离散化。然后就是简单的线段树了。需要根据mod 5的值来维护。具体看代码了。
/*
线段树+离散化+离线处理
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
#define N 100010
ll 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;
}