hdu 4288

发布时间:2016-12-11 22:03:54 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4288",主要涉及到hdu 4288方面的内容,对于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("%I64d\n",tree[1].sum[3]); } } return 0; }

上一篇:android socket 即时通信
下一篇:初步了解mysql

相关文章

关键词: hdu 4288

相关评论