hdu4288 Coder（线段树+离散化） - c++编程基础

TOP

hdu4288 Coder（线段树+离散化）

2015-07-20 17:29:34 来源: 作者: 【大中小】浏览:3次

题目链接：

huangjing

题意：

题目中给了三个操作 1：add x 就是把x插进去 2：delete x 就是把x删除 3：sum 就是求下标%5=3的元素的和。还有一个条件是插入和删除最后都要保证数列有序。。。首先告诉一种暴力的写法。。因为时间非常充足，需要对stl里面的函数有所了解。。就是直接申明一个vector的容器，然后直接用vector里面的操作比如 insert，erase等等操作。。不过这个效率很低。。最后跑出来6000多ms。。（强哥的代码）代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #define eps 1e-9 #define ll long long #define INF 0x3f3f3f3f using namespace std; char s[5]; int n; vector
           
            a; int main() { int len,val; vector
            
             ::iterator iter; while(cin>>n) { len=0; a.clear(); while(n--) { scanf("%s",s); if(s[0]=='s') { long long ans = 0; for(int i=2; i < len ; i+=5) ans += a[i]; cout<
             
              
 
              
 第二种方法是线段树做法，这个要维护5颗线段树，结构体里面保存每个节点的个数，首先因为线段树不支持插入，删除，要维护一个个数cnt，当插入一个数的时候，你看原来%3的数，现在取余肯定等于2，那么怎么办呢？？那么这个cnt就起到了神奇的作用，每当插入删除的时候就把相应的节点数变化，来维护那5棵线段树。。最后因为没有告诉数据范围，所以要采取离散化，然后离线处理，最后得出所有要操作的总个数，然后依此建树，第一次用离散化，觉得好高大上。。。 代码：（参考自cxlove） 
              #include
               
                
#include
                
                  #include
                 
                   #include
                  
                    #include
                    #include
                    
                      #include
                     
                       #include
                      
                        #include
                       
                         #define eps 1e-9 #define ll long long #define INF 0x3f3f3f3f using namespace std; const int maxn=100000+10; int n,a[maxn],b[maxn]; char op[maxn][5]; struct Tree { int cnt; ll sum[5]; }tree[maxn<<2]; void buildtree(int l,int r,int dex) { tree[dex].cnt=0; memset(tree[dex].sum,0,sizeof(tree[dex].sum)); if(l==r) return; int mid=(l+r)>>1; buildtree(l,mid,dex<<1); buildtree(mid+1,r,dex<<1|1); } void push_up(int dex) { for(int i=0;i<5;i++) tree[dex].sum[i]=tree[dex<<1].sum[i]+tree[dex<<1|1].sum[((i-tree[dex<<1].cnt)%5+5)%5]; } void update(int l,int r,int dex,int pos,int flag,int val) { tree[dex].cnt+=flag; if(l==r) { if(flag==1) tree[dex].sum[1]=val; else tree[dex].sum[1]=0; return; } int mid=(l+r)>>1; if(pos<=mid) update(l,mid,dex<<1,pos,flag,val); else update(mid+1,r,dex<<1|1,pos,flag,val); push_up(dex); } int main() { int tot,pos,flag; while(~scanf("%d",&n)) { tot=0; for(int i=1;i<=n;i++) { scanf("%s",op[i]); if(op[i][0]!='s') { scanf("%d",&b[i]); a[tot++]=b[i]; } } sort(a,a+tot); tot=unique(a,a+tot)-a; if(tot==0) memset(tree[1].sum,0,sizeof(tree[1].sum)); else buildtree(1,tot,1); for(int i=1;i<=n;i++) { pos=lower_bound(a,a+tot,b[i])-a; pos++; if(op[i][0]=='a') { flag=1; update(1,tot,1,pos,flag,b[i]); } else if(op[i][0]=='d') { flag=-1; update(1,tot,1,pos,flag,b[i]); } else printf("%I64d\n",tree[1].sum[3]); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：zoj3820 Building Fire Stations ..	下一篇：uva 12436 - Rip Van Winkle'..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: