hdu4288Coder

75 阅读 0 评论 50 点赞

我是靠谱客的博主怕孤单电源，这篇文章主要介绍hdu4288Coder，现在分享给大家，希望可以做个参考。

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4288

题意：给定n个操作：add x：添加一个元素x进入集合，del x：将集合中的x删除，sum：将集合中所有元素排序，输出i%5==3的a[i]的和，并且题目说明每个add的x都不相同。

分析：首先我们将所有操作读入，将所有x离散化一下，这样的话我们就只要每次将元素插入到它对应的位置即可。但是问题在于求和的位置是%5=3的位置，我们在添加和删除元素的时候都会使得答案的统计大批的移动，这样就很不利于我们快速得到答案了。我们想想能否将题目分治，每次通过子问题合并来求解，有了这个想法其实就差不多了，我们将所有数的位置建线段树，然后在每一个节点（区间）保存我们想要的信息：m[i][x]在节点x表示区间中mod 5==i的总和是多少，sum[x]表示x的区间中的元素个数，这样的话我们就可以将两个子区间合并成大区间啦，然后只要logn添加和删除即可。O(nlogn)。

代码：

复制代码

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=100010;
const int MAX=1000000100;
const int mod=100000000;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=998244353;
const ll INF=10000000010;
typedef double db;
typedef unsigned long long ull;
struct node {
int op,x;
node () {}
node (int op,int x):op(op),x(x) {}
}ope[N];
char s[5];
int a[N],b[N],sum[4*N];
ll m[5][4*N];
void build(int x,int l,int r) {
sum[x]=m[0][x]=m[1][x]=m[2][x]=m[3][x]=m[4][x]=0;
if (l==r) return ;
int mid=(l+r)>>1;
build(2*x,l,mid);build(2*x+1,mid+1,r);
}
void add(int x,int l,int r,int w,int z) {
sum[x]++;
if (l==r) { m[1][x]+=(ll)z;return ; }
int i,g,mid=(l+r)>>1;
if (w<=mid) add(2*x,l,mid,w,z);
else add(2*x+1,mid+1,r,w,z);
g=sum[2*x]%5;
for (i=0;i<5;i++) m[(i+g)%5][x]=m[(i+g)%5][2*x]+m[i][2*x+1];
}
void del(int x,int l,int r,int w) {
sum[x]--;
if (l==r) { m[1][x]=0;return ; }
int i,g,mid=(l+r)>>1;
if (w<=mid) del(2*x,l,mid,w);
else del(2*x+1,mid+1,r,w);
g=sum[2*x]%5;
for (i=0;i<5;i++) m[(i+g)%5][x]=m[(i+g)%5][2*x]+m[i][2*x+1];
}
int main()
{
int i,k,n,x,w;
while (scanf("%d", &n)!=EOF) {
k=0;
for (i=1;i<=n;i++) {
scanf("%s", s);
if (s[0]=='a') {
scanf("%d", &x);
ope[i]=node(1,x);
k++;a[k]=b[k]=x;
} else if (s[0]=='d') {
scanf("%d", &x);
ope[i]=node(2,x);
} else ope[i]=node(3,0);
}
sort(b+1,b+k+1);
w=unique(b+1,b+k+1)-(b+1);
build(1,1,k);
for (i=1;i<=n;i++)
if (ope[i].op==1) add(1,1,k,lower_bound(b+1,b+w+1,ope[i].x)-b,ope[i].x);
else if (ope[i].op==2) del(1,1,k,lower_bound(b+1,b+w+1,ope[i].x)-b);
else printf("%I64dn", m[3][1]);
}
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
74
75
76
77
78
79
80
81
82
83
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=100010;
const int MAX=1000000100;
const int mod=100000000;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=998244353;
const ll INF=10000000010;
typedef double db;
typedef unsigned long long ull;
struct node {
int op,x;
node () {}
node (int op,int x):op(op),x(x) {}
}ope[N];
char s[5];
int a[N],b[N],sum[4*N];
ll m[5][4*N];
void build(int x,int l,int r) {
sum[x]=m[0][x]=m[1][x]=m[2][x]=m[3][x]=m[4][x]=0;
if (l==r) return ;
int mid=(l+r)>>1;
build(2*x,l,mid);build(2*x+1,mid+1,r);
}
void add(int x,int l,int r,int w,int z) {
sum[x]++;
if (l==r) { m[1][x]+=(ll)z;return ; }
int i,g,mid=(l+r)>>1;
if (w<=mid) add(2*x,l,mid,w,z);
else add(2*x+1,mid+1,r,w,z);
g=sum[2*x]%5;
for (i=0;i<5;i++) m[(i+g)%5][x]=m[(i+g)%5][2*x]+m[i][2*x+1];
}
void del(int x,int l,int r,int w) {
sum[x]--;
if (l==r) { m[1][x]=0;return ; }
int i,g,mid=(l+r)>>1;
if (w<=mid) del(2*x,l,mid,w);
else del(2*x+1,mid+1,r,w);
g=sum[2*x]%5;
for (i=0;i<5;i++) m[(i+g)%5][x]=m[(i+g)%5][2*x]+m[i][2*x+1];
}
int main()
{
int i,k,n,x,w;
while (scanf("%d", &n)!=EOF) {
k=0;
for (i=1;i<=n;i++) {
scanf("%s", s);
if (s[0]=='a') {
scanf("%d", &x);
ope[i]=node(1,x);
k++;a[k]=b[k]=x;
} else if (s[0]=='d') {
scanf("%d", &x);
ope[i]=node(2,x);
} else ope[i]=node(3,0);
}
sort(b+1,b+k+1);
w=unique(b+1,b+k+1)-(b+1);
build(1,1,k);
for (i=1;i<=n;i++)
if (ope[i].op==1) add(1,1,k,lower_bound(b+1,b+w+1,ope[i].x)-b,ope[i].x);
else if (ope[i].op==2) del(1,1,k,lower_bound(b+1,b+w+1,ope[i].x)-b);
else printf("%I64dn", m[3][1]);
}
return 0;
}