hdu4288 Coder 2012成都网络赛 A题

题意：往集合里面添加删除数，集合中的数是按从小到大排列的，询问下标模5等于3的数的和。

记得当时这题不会做，

现在想简单多了，只要维护五个值和左右子树的size大小就行了。

#define maxn 100005

struct node
{
  int l,r;
  int sz;
  i64 f[5];
  int mid()
  {
    return (l + r ) /2 ;
  }
};
node tt[maxn * 3 ];
struct node1
{
  int id ;
  i64  x;
};
node1 ml[maxn];
void push_up(int root )
{
  int sz ;
  sz = tt[root * 2].sz;
  tt[root].sz = tt[root * 2].sz + tt[root * 2 + 1].sz;
  for(int i = 0 ; i < 5 ; i ++ )
    tt[root].f[i] = tt[root * 2].f[i] + tt[root * 2 + 1 ].f[(i + 5 - sz % 5 ) % 5];
  return ;
}
void build(int root ,int l,int r )
{
  tt[root].l = l ;
  tt[root].r = r ;
  tt[root].sz = 0 ;
  for(int i = 0; i < 5; i ++ ) tt[root].f[i] = 0 ;
  if(l == r ) return  ;
  int mid = tt[root].mid();
  build(root * 2 , l , mid );
  build(root * 2 + 1 , mid + 1 , r);
  return ;
}
void update(int root ,int pos ,i64 vv)
{
  if(tt[root].l == tt[root].r )
  {
    if(vv == 0 )
    {
      tt[root].sz = 0 ;
      for(int i = 0; i < 5; i ++ ) tt[root].f[i] = 0 ;
    }
    else
    {
      tt[root].sz = 1 ;
      for(int i = 0 ; i < 5 ;i ++ ) tt[root].f[i] = 0 ;
      tt[root].f[1] = vv;
    }
    return ;
  }
  int mid = tt[root].mid();
  if(pos <= mid )
    update(root * 2 , pos , vv);
  if(pos > mid )
    update(root * 2 + 1 , pos , vv);
  push_up(root);
}
int num;
i64 b[maxn];
int pos[maxn];
char str[10];
int main()
{
  int x;
  int n ;
  while(scanf("%d",&n)!=EOF)
  {
    num = 0 ;
    for(int i = 1 ;i <= n ; i ++ )
    {
      scanf("%s",str);
      if(str[0] == 'a')
      {
        ml[i].id = 1;
        scanf("%I64d",&ml[i].x);
        b[num++] = ml[i].x;
      }
      else if(str[0] == 'd')
      {
        ml[i].id = 2 ;
        scanf("%I64d",&ml[i].x);
        b[num++] = ml[i].x;
      }
      else
      {
        ml[i].id = 3;
      }
    }
    sort(b ,b + num);
    int pos;
    num = unique(b,b+num) - b;
    build(1,1,num);
    for(int i = 1; i <= n ; i ++ )
    if(ml[i].id != 3)
    {
      pos = lower_bound(b , b + num , ml[i].x) - b + 1 ;
      if(ml[i].id == 1 )
        update(1,pos,ml[i].x);
      else update(1,pos,0);
    }
    else
    {
      printf("%I64d
",tt[1].f[3]);
    }
  }
    return 0;
}