题意：

给出一个有序集合，3种操作。插入一个数，删除一个数，都保证序列有序。以及求和

其中求和是将下标%5==3的所有数求和；

 

题解： 线段树   + 离散化 + 离线处理

一开始也是想的 线段树 ，但是 这个和以前的 做过的 一个线段树 不同的 是 ，如果 我们 删除 一个 元素后  ，那么 他的 下标 将会 改变 ，比赛是 不知  如何下手 。。。。。

 

 

同样 是 用 5棵线段树   维护 ，s[0]表示 %5  == 1 的 下标，其他 依次类推  cnt，记录 子树的 元素个数。

想要得到该区间内所有模5等3所有元素的和，左孩子可以求到，两个孩子相互独立，所以求右孩子需要知道（左子树含有 ）多少个元素，因为这样分开求的时候，我们才知道 求右孩子时应该求下标模5等几（)的所有元素的和。

假如我们 求  i ==  3 时 （表示  %5 == 4），对于 左子树 我们 直接 求 就可以 ，但是 对于 右子树，我们 要知道 在 i== 3 的 情况下 ，右子树的 元素的下标 应该 是 %5 == 几？

p[x].s[i] = p[x*2].s[i] + p[x*2+1].s[((i  - p[x*2].cnt)%5 + 5)% 5]；

 

 

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<

set>

#include<map>

#include<queue>

#include<vector>

#include<

string>

#define Min(a,b) a<b?a:b

#define Max(a,b) a>b?a:b

#define CL(a,num) memset(a,num,sizeof(a));

#define eps  1e-12

#define inf   10000000

//

freopen("data.txt","r",stdin);

const 

double pi  = acos(-

1.0);

typedef   __int64  ll;

const 

int maxn = 

101000 ;

using 

namespace std;

char c[

6];

struct node

{

    

int l;

    

int r;

    ll s[

5] ;

    

int cnt ;

}p[maxn*

4] ;

ll  a[maxn],b[maxn],tp[maxn] ;

void build(

int x,

int l,

int r)

{

     p[x].cnt = 

0;

     p[x].l = l;

     p[x].r = r;

     CL(p[x].s,

0) ;

    

if(l == r)

return ;

    

int mid = ( l + r) >> 

1;

    build(x*

2,l,mid);

    build(x*

2+

1,mid+

1,r) ;

}

void add(

int x,

int pos,

int k)

{

    p[x].cnt += k*

2 - 

1 ;

    

if(p[x].l  == pos && p[x].r == pos)

    {

          p[x].s[

0] = k*a[pos] ;

//

只有 一个元素 所以 % 5 == 1，我们 放到 s[0]里面

          

return ;

    }

    

int  mid = (p[x].l + p[x].r) >> 

1;

    

if(pos <=mid )add(x*

2,pos,k);

    

else add(x*

2+

1,pos,k);

    

for(

int i = 

0 ; i< 

5;i++)

    {

        p[x].s[i] = p[x*

2].s[i] + p[x*

2+

1].s[((i  - p[x*

2].cnt)%

5 + 

5)% 

5] ;

//

实现了 动态的 改变

    }

}

int main()

{

   

//

freopen("data.txt","r",stdin);

   

int n ,i;

   

while(scanf(

"

%d

",&n)!=EOF)

   {

       CL(tp,-

1);

       

int num = 

0 ;

       

for(i = 

0 ; i < n;i++)

       {

           scanf(

"

%s

",c);

           

if(c[

0] == 

'

a

')

           {

               tp[i] = 

0;

               scanf(

"

%I64d

",&b[i]);

               a[num++] = b[i] ;

           }

           

if(c[

0] == 

'

d

')

           {

               tp[i] = 

1;

               scanf(

"

%I64d

",&b[i]);

               a[num++] = b[i] ;

           }

           

if(c[

0] == 

'

s

')

           {

               tp[i] = 

2 ;

           }

       }

        sort(a,a+num) ;

        

int tot = unique(a,a+num) - a ;

        

        build(

1,

0,tot - 

1);

        

for(i = 

0  ; i< n;i++)

        {

            

if(tp[i] == 

0)

            {

                add(

1,lower_bound(a,a+tot,b[i]) - a ,

1);

            }

            

if(tp[i] == 

1)

            {

                  add(

1,lower_bound(a,a+tot,b[i]) - a ,

0);

            }

            

if(tp[i] == 

2)

             printf(

"

%I64d\n

",p[

1].s[

2]);

        }

   }

}