hdu 4288 Coder - c++编程基础 - C语言编程开发

TOP

hdu 4288 Coder

2015-07-20 17:51:38 来源: 作者: 【大中小】浏览:1次

初始有一个空集合，有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 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#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 ,tree[1].sum[3]); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[POJ 2407]Relatives(欧拉函数)	下一篇：ZOJ - 3794 Greedy Driver 最短路

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: