首页 > 代码库 > hdu 4288 Coder (线段树+离线)
hdu 4288 Coder (线段树+离线)
题意：
刚开始有一个空集合。有三种操作：
1.往集合中加入一个集合中不存在的数 x
2.从集合中删除一个已经存在的数 x
3.计算集合的digest sum并输出。 digest sum求法：将集合中所有数从小到大排序，得到a1<a2<...<an。 digest sum = sum(ai) where i mod 5 = 3
数据范围：
N ( 1 <= N <= 105 )
1 <= x <= 109.
For any “add x” it is guaranteed that x is not currently in the set just before this operation.
For any “del x” it is guaranteed that x must currently be in the set just before this operation.
思路：
先将所有增加过的，删除过的数存下来，去重，搞成线段树。
每个结点（区间）里有两个东西，一个是 cnt，记录该区间的在集合中的元素的个数。一个是sum[i] , sum[i]：该区间序号%5等于i的存在于集合中的元素的总和。
插入和删除时维护即可。
代码：
int const maxn=1e5+5;struct node{ int cnt; ll sum[5];}tree[maxn<<2];int n,tot;int q[maxn],a[maxn];char ope[maxn][15];void build(int l,int r,int rt){ tree[rt].cnt=0; memset(tree[rt].sum,0,sizeof(tree[rt].sum)); if(l==r) return; int m=(l+r)>>1; build(lson); build(rson);}void pushUp(int rt){ rep(i,0,4) tree[rt].sum[i]=tree[rt<<1].sum[i]+tree[rt<<1|1].sum[((5-tree[rt<<1].cnt%5)%5+i)%5];}void update(int k,int pos,int num,int l,int r,int rt){ tree[rt].cnt+=k; if(l==r){ tree[rt].sum[0]+=(k*num); return; } int m=(l+r)>>1; if(pos<=m) update(k,pos,num,lson); else update(k,pos,num,rson); pushUp(rt);}int main(){ //freopen("test.in","r", stdin); while(scanf("%d",&n)!=EOF){ tot=0; rep(i,1,n){ scanf("%s",ope[i]); if(ope[i][0]!=‘s‘){ scanf("%d",&q[i]); a[tot++]=q[i]; } } sort(a,a+tot); tot=unique(a,a+tot)-a; if(tot==0) memset(tree[1].sum,0,sizeof(tree[1].sum)); else build(1,tot,1); rep(i,1,n){ int pos=lower_bound(a,a+tot,q[i])-a+1; if(ope[i][0]==‘a‘){ update(1,pos,q[i],1,tot,1); continue; } if(ope[i][0]==‘d‘){ update(-1,pos,q[i],1,tot,1); continue; } printf("%I64d\n",tree[1].sum[2]); } } //fclose(stdin);}
hdu 4288 Coder (线段树+离线)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。