HDU 4288 Coder（线段树＋离线处理）

95 阅读 0 评论 63 点赞

我是靠谱客的博主老实百合，这篇文章主要介绍HDU 4288 Coder（线段树＋离线处理），现在分享给大家，希望可以做个参考。

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

维护一个序列an，有以下三种操作：

一、在序列中添加元素x

二、在序列中删除元素x

三、计算序列中下标i%5=3的元素和

在写解题报告之前先废话几句关于线段树的姿势问题：

之前一直习惯于结构体姿势的线段树，后来看了notonlysuccess的线段树总结，开始采用数组的方式写线段树，结构体的缺点在于浪费了2n的空间（维护区间l和r值），而数组的缺点在于浪费了常数的时间（传参），之前在清华校赛中有遇到这种情况，卡常数最后那题一直没过，这道题也是这种情况，结构体1s多，数组需要2s多（这题可过，但花费时间太多）。虽然数组的方式很优雅，但是在必要的时候还是需要考虑一下空间和时间。。。

典型的线段树单点更新区间查询问题。

线段树不支持添加和删除操作，所以肯定无法在线处理，采用离线的方法。

先预处理数据，将所有数据保存到a数组中，并复制到x数组，将x数组的所有元素排序去重，然后根据x数组建立线段树。

线段树中维护两个：num和sum[5]

num表示区间内的元素个数，sum[i]表示区间中所有满足下标x％5=i的元素和（下标是指区间内的第一个，不是整体）

这样的话，向上更新的时候满足

复制代码

1
node[rt].sum[i]=node[rt<<1].sum[i]+node[rt<<1|1].sum[((i-node[rt<<1].num)%5+5)%5];

因为右结点的第x元素下标在父结点中应该对应的是第(x+左结点的元素个数)个元素，即i=x+cnt,x=i-cnt，取模是为了防止负数

每次查询时只需要返回node[1].sum[2]即可

复制代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
typedef __int64 ll;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int n;
int a[maxn],x[maxn];
char cmd[maxn][10];
struct Node{
ll sum[5];
int num;
}node[maxn<<2];
void PushUp(int rt){
for(int i=0;i<5;i++){
node[rt].sum[i]=node[rt<<1].sum[i]+node[rt<<1|1].sum[((i-node[rt<<1].num)%5+5)%5];
}
}
void build(int rt,int l,int r){
if(l==r){
memset(node[rt].sum,0,sizeof(node[rt].sum));
node[rt].num=0;
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
memset(node[rt].sum,0,sizeof(node[rt].sum));
node[rt].num=0;
}
void Update(int rt,int l,int r,int pos,int val,int op){
op?++node[rt].num:--node[rt].num;
if(l==r){
node[rt].sum[0]=op*val;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) Update(lson,pos,val,op);
else Update(rson,pos,val,op);
PushUp(rt);
}
int main(){
while(~scanf("%d",&n)){
int len=0;
for(int i=0;i<n;i++){
scanf("%s",cmd[i]);
if(cmd[i][0]!='s'){
scanf("%d",&a[i]);
x[len++]=a[i];
}
}
sort(x,x+len);
len=unique(x,x+len)-x;
build(1,1,len);
for(int i=0;i<n;i++){
if(cmd[i][0]=='a'){
int k=(int)(lower_bound(x,x+len,a[i])-x)+1;
Update(1,1,len,k,a[i],1);
}
else if(cmd[i][0]=='d'){
int k=(int)(lower_bound(x,x+len,a[i])-x)+1;
Update(1,1,len,k,a[i],0);
}
else{
printf("%I64dn",node[1].sum[2]);
}
}
}
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
typedef __int64 ll;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int n;
int a[maxn],x[maxn];
char cmd[maxn][10];
struct Node{
ll sum[5];
int num;
}node[maxn<<2];
void PushUp(int rt){
for(int i=0;i<5;i++){
node[rt].sum[i]=node[rt<<1].sum[i]+node[rt<<1|1].sum[((i-node[rt<<1].num)%5+5)%5];
}
}
void build(int rt,int l,int r){
if(l==r){
memset(node[rt].sum,0,sizeof(node[rt].sum));
node[rt].num=0;
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
memset(node[rt].sum,0,sizeof(node[rt].sum));
node[rt].num=0;
}
void Update(int rt,int l,int r,int pos,int val,int op){
op?++node[rt].num:--node[rt].num;
if(l==r){
node[rt].sum[0]=op*val;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) Update(lson,pos,val,op);
else Update(rson,pos,val,op);
PushUp(rt);
}
int main(){
while(~scanf("%d",&n)){
int len=0;
for(int i=0;i<n;i++){
scanf("%s",cmd[i]);
if(cmd[i][0]!='s'){
scanf("%d",&a[i]);
x[len++]=a[i];
}
}
sort(x,x+len);
len=unique(x,x+len)-x;
build(1,1,len);
for(int i=0;i<n;i++){
if(cmd[i][0]=='a'){
int k=(int)(lower_bound(x,x+len,a[i])-x)+1;
Update(1,1,len,k,a[i],1);
}
else if(cmd[i][0]=='d'){
int k=(int)(lower_bound(x,x+len,a[i])-x)+1;
Update(1,1,len,k,a[i],0);
}
else{
printf("%I64dn",node[1].sum[2]);
}
}
}
return 0;
}