题意：
给定三种操作
1. add x 向序列中添加x，添加之后序列还保持有序
2. del x 删除序列中值为x的元素
3. sum 求下边模5等于3的元素和
思路：
直接暴力也可以过，就是看暴力写的好不好了。用数组直接暴力可过。
暴力代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100010; typedef long long ll; int a[maxn]; int main() { int n; while (~scanf("%d", &n)) { char cmd[10]; int d; int len = 0; while (n--) { scanf("%s", cmd); if (cmd[0] == 'a') { scanf("%d", &d); int i; for (i = len++; i >= 1; i--) { if (a[i] <= d) break; a[i + 1] = a[i]; } a[i + 1] = d; } else if (cmd[0] == 'd') { scanf("%d", &d); int i; for (i = 1; i <= len; i++) if (a[i] == d) break; for (; i < len; i++) a[i] = a[i + 1]; len--; } else { ll ans = 0; for (int i = 3; i <= len; i += 5) ans += (ll)a[i]; printf("%lld ", ans); } } } return 0; }
也可以用线段树来维护。先把所有的数据都读进来，然后离散化一下建树。树的每个节点维护一个sum[5]，就是模上5之后的余数，还有一个当前区间的有多少个数字的个数。注意：每个节点的sum当中的下边都是对应线段树中该节点的下边来说的。所以叶子节点一定对应1，就是sum[0], 关键就是pushup，因为往上更新的时候，考虑一个父区间，它的左孩子区间对应的sum[i]，就是父区间的sum[i]，但是右区间的sum[i]对应的不是父区间的sum[i],而是sum[(i + lson.cnt)%5]。所以这样就可以做拉。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100010; typedef long long ll; struct Tree { int cnt; ll sum[5]; }tree[maxn << 2]; int dat[maxn], tmp[maxn]; char cmd[maxn][10]; void pushup(int rt) { for (int i = 0; i < 5; i++) tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[((i - tree[rt<<1].cnt) % 5 + 5) % 5]; tree[rt].cnt = tree[rt<<1].cnt + tree[rt<<1|1].cnt; //当然也可以这么写。 //int j = (i + tree[rt<<1].cnt) % 5; //tree[rt].sum[j] = tree[rt<<1].sum[j] + tree[rt<<1|1].sum[i]; } void build(int rt, int l, int r) { for (int i = 0; i < 5; i++) tree[rt].sum[i] = 0; tree[rt].cnt = 0; if (l == r) return; int mid = (l + r) / 2; build(rt<<1, l, mid); build(rt<<1|1, mid + 1, r); } void update(int rt, int l, int r, int p, int val, int flag) { if (l == r) { tree[rt].cnt += flag; tree[rt].sum[0] = val; return; } int mid = (l + r) / 2; if (p <= mid) update(rt<<1, l, mid, p, val, flag); else update(rt<<1|1, mid + 1, r, p, val, flag); pushup(rt); } int main() { int n; while (~scanf("%d", &n)) { int num = 0; for (int i = 0; i < n; i++) { scanf("%s", cmd[i]); if (cmd[i][0] != 's') { scanf("%d", &dat[i]); tmp[num++] = dat[i]; } } sort(tmp, tmp + num); num = unique(tmp, tmp + num) - tmp; build(1, 1, n); for (int i = 0; i < n; i++) { int p = lower_bound(tmp, tmp + num, dat[i]) - tmp; if (cmd[i][0] == 's') printf("%lld ", tree[1].sum[2]); else if (cmd[i][0] == 'a') update(1, 1, n, p, dat[i], 1); else update(1, 1, n, p, 0, -1); } } return 0; }