首页 > 代码库 > hdu 4288 Coder
hdu 4288 Coder
http://acm.hdu.edu.cn/showproblem.php?pid=4288
初始有一个空集合,有N个操作,1 add x向集合中加一个元素x,2 del x在集合中删除一个元素x,sum询问下标mod 5为3的元素的和。
建立一棵线段树,能够实现数组中元素的删除和添加,维护区间的和。
重点是怎么在元素随时变动的条件下求下标mod 5 为3的数的和。首先节点有一个信息cnt表示区间内元素的个数,sum[5]
代表了在这个区间中下表分别对5取余的元素的和,注意是在当前区间内,若当前有一个元素那么存入sum[1]中。然后就是push_up时,sum【】的维护,这个挺难想的,看了题解然后和同学讨论了好久才明白。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> //#define LL long long #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100010; struct Info { char str[5]; LL num; }info[maxn]; LL x[maxn]; struct node { int l,r; int cnt; LL sum[6]; }tree[maxn*4]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].cnt = 0; tree[v].sum[0] = tree[v].sum[1] = tree[v].sum[2] = tree[v].sum[3] = tree[v].sum[4] = 0; if(l == r) return; int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); } int Binsearch(int l, int r, int key) { int mid,low = l,high = r; while(high >= low) { mid = (low + high) >> 1; if(x[mid] == key) return mid; if(x[mid] > key) high = mid-1; else low = mid+1; } return -1; } void update(int v, int pos, LL num, int f) { tree[v].cnt += f; if(tree[v].l == tree[v].r) { tree[v].sum[1] += num; return; } int mid = (tree[v].l + tree[v].r) >> 1; if(pos <= mid) update(v*2,pos,num,f); else update(v*2+1,pos,num,f); //重点,维护区间的和。 for(int i = 0; i < 5; i++) tree[v].sum[i] = tree[v*2].sum[i] + tree[v*2+1].sum[((i-tree[v*2].cnt)%5+5)%5]; } int main() { int n; int cnt; while(~scanf("%d",&n)) { cnt = 0; for(int i = 1; i <= n; i++) { scanf("%s",info[i].str); if(strcmp(info[i].str,"sum") != 0) { scanf("%I64d",&info[i].num); x[++cnt] = info[i].num; } } //离散化 sort(x+1,x+1+cnt); cnt = unique(x+1,x+1+cnt)-(x+1); build(1,1,cnt); int pos; for(int i = 1; i <= n; i++) { if(info[i].str[0] != 's') pos = Binsearch(1,cnt,info[i].num);//二分寻找下标 if(info[i].str[0] == 'a') { update(1,pos,info[i].num,1); } else if(info[i].str[0] == 'd') { update(1,pos,-info[i].num,-1); } else printf("%I64d\n",tree[1].sum[3]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。