hdu 4288(区间合并)

112 阅读 0 评论 74 点赞

我是靠谱客的博主开朗墨镜，这篇文章主要介绍hdu 4288(区间合并)，现在分享给大家，希望可以做个参考。

题意：给出三种操作，add x表示往序列里添加x，del x表示将序列中的x删除，sum要求输出序列按升序排列好后中下标%5==3的数字的和。
题解：线段树每个节点要存两种值，一个是当前区间内还有多少个数字，另一个是sum[i]表示下标%5==i的数字的和，修改数字比较很简单，而在同时维护sum[i]的值比较不好办，一个节点的sum[i]可以由两个孩子节点得到，tree[k].sum[(i+tree[k*2].num)%5] = tree[k*2].sum[(i+tree[k*2].num)%5] + tree[k*2+1].sum[i]，因为将右边的下标确定，左边的可能会一些没有下标的数字被删掉了，应该按数量+i计算。

复制代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
struct Tree {
int num;
long long sum[5];
}tree[N << 2];
int a[N], b[N], n;
char str[N][10];
void pushup(int k) {
for (int i = 0; i < 5; i++) {
int temp = (i + tree[k * 2].num) % 5;
tree[k].sum[temp] = tree[k * 2].sum[temp] + tree[k * 2 + 1].sum[i];
}
}
void build(int k, int left, int right) {
tree[k].num = 0;
memset(tree[k].sum, 0, sizeof(tree[k].sum));
if (left == right)
return;
int mid = (left + right) / 2;
build(k * 2, left, mid);
build(k * 2 + 1, mid + 1, right);
}
void modify(int k, int left, int right, int pos, int x, int flag) {
if (flag)
tree[k].num++;
else
tree[k].num--;
if (left == right) {
tree[k].sum[1] = flag * x;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
modify(k * 2, left, mid, pos, x, flag);
else
modify(k * 2 + 1, mid + 1, right, pos, x, flag);
pushup(k);
}
int main() {
while (scanf("%d", &n) == 1) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
scanf("%s", str[i]);
if (str[i][0] != 's') {
scanf("%d", &b[i]);
a[cnt++] = b[i];
}
}
sort(a, a + cnt);
cnt = unique(a, a + cnt) - a;
if (cnt == 0)
memset(tree[1].sum, 0, sizeof(tree[1].sum));
else
build(1, 1, cnt);
for (int i = 1; i <= n; i++) {
if (str[i][0] == 'a') {
int pos = lower_bound(a, a + cnt, b[i]) - a + 1;
modify(1, 1, cnt, pos, b[i], 1);
}
else if (str[i][0] == 'd') {
int pos = lower_bound(a, a + cnt, b[i]) - a + 1;
modify(1, 1, cnt, pos, b[i], 0);
}
else
printf("%lldn", tree[1].sum[3]);
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
struct Tree {
int num;
long long sum[5];
}tree[N << 2];
int a[N], b[N], n;
char str[N][10];
void pushup(int k) {
for (int i = 0; i < 5; i++) {
int temp = (i + tree[k * 2].num) % 5;
tree[k].sum[temp] = tree[k * 2].sum[temp] + tree[k * 2 + 1].sum[i];
}
}
void build(int k, int left, int right) {
tree[k].num = 0;
memset(tree[k].sum, 0, sizeof(tree[k].sum));
if (left == right)
return;
int mid = (left + right) / 2;
build(k * 2, left, mid);
build(k * 2 + 1, mid + 1, right);
}
void modify(int k, int left, int right, int pos, int x, int flag) {
if (flag)
tree[k].num++;
else
tree[k].num--;
if (left == right) {
tree[k].sum[1] = flag * x;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
modify(k * 2, left, mid, pos, x, flag);
else
modify(k * 2 + 1, mid + 1, right, pos, x, flag);
pushup(k);
}
int main() {
while (scanf("%d", &n) == 1) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
scanf("%s", str[i]);
if (str[i][0] != 's') {
scanf("%d", &b[i]);
a[cnt++] = b[i];
}
}
sort(a, a + cnt);
cnt = unique(a, a + cnt) - a;
if (cnt == 0)
memset(tree[1].sum, 0, sizeof(tree[1].sum));
else
build(1, 1, cnt);
for (int i = 1; i <= n; i++) {
if (str[i][0] == 'a') {
int pos = lower_bound(a, a + cnt, b[i]) - a + 1;
modify(1, 1, cnt, pos, b[i], 1);
}
else if (str[i][0] == 'd') {
int pos = lower_bound(a, a + cnt, b[i]) - a + 1;
modify(1, 1, cnt, pos, b[i], 0);
}
else
printf("%lldn", tree[1].sum[3]);
}
}
return 0;
}