//先将所有的操作离线,将读入的所有数按照从小到大排列,去除重复的点
//用线段树维护这个区间内的数读入的数目,用一个数组存入在这个区间内
//对5取余数分别为0,1,2,3,4的所有数之和
//更新的时候tree[v].sum[i] = tree[v<<1].sum[i] + tree[v<<1|1].sum[((i - tree[v<<1].cnt)%5 + 5)%5] ;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std ;
const int maxn = 500010 ;
struct node
{
int l ,r ;
__int64 sum[5];
int cnt ;
}tree[4*maxn] ;
int len ;
int a[maxn] ;
int data[maxn] ;
char str[maxn][10] ;
int N ;
int flag = 0;
int bit(int num)
{
int left = 0;
int right = len - 1;
while(left <= right)
{
int mid = (left + right) >> 1 ;
if(a[mid] > num)
right = mid - 1 ;
else if(a[mid] < num)
left = mid + 1;
else
return mid ;
}
}
void build(int l ,int r ,int v)
{
tree[v].l = l;
tree[v].r = r;
tree[v].cnt = 0;
memset(tree[v].sum , 0 ,sizeof(tree[v].sum)) ;
if(l == r) return ;
int mid = (l+r)>>1;
build(l , mid , v<<1) ;
build(mid+1 , r , v<<1|1) ;
}
void update(int pos , int num ,int v)
{
tree[v].cnt += 2*flag - 1 ;
if(tree[v].l == tree[v].r)
{
tree[v].sum[0] = flag*num ;
return ;
}
if(pos <= tree[v<<1].r)
update(pos , num , v<<1) ;
else update(pos , num , v<<1|1) ;
for(int i = 0;i < 5 ; i++)
tree[v].sum[i] = tree[v<<1].sum[i] + tree[v<<1|1].sum[((i - tree[v<<1].cnt)%5 + 5)%5] ;
}
int main()
{
// freopen("in.txt","r",stdin) ;
while(scanf("%d" , &N) != EOF)
{
len = 0;
for(int i = 0;i < N ;i++)
{
scanf("%s", str[i]) ;
if(str[i][0] != ‘s‘)
{
scanf("%d" , &data[i]);
a[len++] = data[i] ;
}
}
sort(a , a+len) ;
len = unique(a,a+len) - a ;
if(!len) memset(tree[1].sum , 0 ,sizeof(tree[1].sum)) ;
else build(1, len , 1) ;
for(int i = 0;i < N ;i++)
{
if(str[i][0] == ‘a‘)
{
flag = 1 ;
int pos = bit(data[i]) ;
update(pos , data[i] , 1) ;
}
else if(str[i][0] == ‘d‘)
{
flag = 0;
int pos = bit(data[i]);
update(pos , data[i] , 1) ;
}
else
printf("%I64d\n" , tree[1].sum[2]) ;
}
}
}
hdu 4288 Coder 线段树
原文:http://blog.csdn.net/cq_pf/article/details/44814691