hdu4288 Coder（段树+分离）-白红宇

hdu4288 Coder（段树+分离）

阅读量：7041 次

发布时间：2019-06-28

本文共 2513 字，大约阅读时间需要 8 分钟。

主题链接：

题意：

题目中给了三个操作

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 0x3f3f3f3fusing 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 0x3f3f3f3fusing 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;}

你可能感兴趣的文章