hdu 4288

这题按我的做法是超时的，虽然开始也知道这应该是个线段树，不过由于之前都是看还没独立写过，所以没去尝试，果然那后面自己的写法超时了，没办法还是得用线段树，可基本不太会怎么办····最后只好先看看别人的代码了，不过能看懂也说明之前线段树的学习是有成效的，好像这题不仅有线段树，还说有离散化什么的，我猜大概意思是把每个下标mod 5的和用线段树表示出来,由于他们是间隔散乱的，如何让他们整合用线段树来表达，这应该是离散化的意思吧？

1.如何建树？：因为随着add操作，数的个数再改变，我们需要求出前前后后出现的数的个数以此来确定线段树的大小，那么这里就需要做一个离线处理，即先把所有信息储存再来处理，由于delete也会有输出数的请求，所记录的数据中有重复出现的，所以要去一下重，学到一个新函数unique(）去重函数，返回的是不重复的数的末尾，这样大小就能求出来，就可以进行建树。

2..如何记录信息呢？用sum[i]{i=0,1,2,3,4}来记录下标mod5=i的所有数的和，每一段区间都有自己对应的取mod下标和，通过合并即可转化为整个区间的下标和。

3.如何更新？由于位于修改的pos左边的所有下标都不会受影响，只要再统计时转移右边的下标位置就好。

对于线段树的学习现在稍微有点感觉了，还是得多做题，即使不会，看看别人代码，看多了也能明白其中的巧妙。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxnode=1000005;
struct IntervalTree{
int r;
int l;
int cnt;
long long sum[5];
}tree[maxnode];
void tree_build(int o,int L,int R){
tree[o].l=L;//记录区间边界
tree[o].r=R;
tree[o].cnt=0;
for(int i=0;i<5;i++)tree[o].sum[i]=0;
if(L==R)return;
int m=(L+R)>>1;
tree_build(o<<1,L,m);//左子树
tree_build(o<<1|1,m+1,R);//右子树
}
void mantain(int o){
for(int i=0;i<5;i++)
tree[o].sum[i]=tree[o<<1].sum[i];
for(int i=0;i<5;i++)
tree[o].sum[(i+tree[o<<1].cnt)%5]+=tree[o<<1|1].sum[i];
}
void tree_update(int o,int value,int pos,int op){
tree[o].cnt+=op;//更新数目
if(tree[o].r==tree[o].l){
tree[o].sum[1]+=value;
return;
}
else{
if(pos<=tree[o<<1].r)tree_update(o<<1,value,pos,op);
else tree_update(o<<1|1,value,pos,op);
mantain(o);
}
}
int main(){
int n,s[100005],num[100005];
char str[100005][10];
while(scanf("%d",&n)!=EOF){
int len=0;
for(int i=0;i<n;i++){
scanf("%s",str[i]);
if(str[i][0]!='s'){
scanf("%d",&s[i]);
num[len++]=s[i];
}
}
sort(num,num+len);
len=unique(num,num+len)-num;//unique去重函数,算出实际的集合中元素个数
tree_build(1,1,len);
for(int i=0;i<n;i++){
if(str[i][0]=='a'){
int pos=lower_bound(num,num+len,s[i])-num;//找到要插入的位置下标
tree_update(1,s[i],pos,1);//更新
}
if(str[i][0]=='d'){
int pos=lower_bound(num,num+len,s[i])-num;
tree_update(1,-s[i],pos,-1);
}
if(str[i][0]=='s')printf("%I64dn",tree[1].sum[3]);
}
}
return 0;
}

最后

以上就是故意牛排为你收集整理的hdu 4288的全部内容，希望文章能够帮你解决hdu 4288所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。