hdu 4288 2012成都ネット試合

線分の木の学の遥かに足りないで、ネットの試合の時ずっとどのようにすることを知らないで、それから大神の報告を見て、やっと少し学びました.
セグメントツリーは、各ノードにsum[0...5]、すなわち、位置mod 5の5つの結果の数に対応する和を記録する.cnt記録区間には何個の数がありますか.
更新の際は対応サブ区間のsum[i]を加算すればOKです

#include<iostream>
#include<algorithm>
using namespace std;

#define MAXN 100010
#define lson u<<1
#define rson u<<1|1
typedef long long LL;

int dat[MAXN],tmp[MAXN];
char cmd[MAXN][5];

struct Node{
	int lef,rig;
	LL sum[5];
	int cnt;
}T[MAXN<<2];

void Build(int u,int l,int r){
	T[u].lef=l;
	T[u].rig=r;
	T[u].cnt=0;
	for(int i=0;i<5;i++)T[u].sum[i]=0;
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(lson,l,mid);
	Build(rson,mid+1,r);
}

void PushUp(int u){
	for(int i=0;i<5;i++)T[u].sum[i]=T[lson].sum[i]+T[rson].sum[((i-T[lson].cnt)%5+5)%5];
}

void Update(int u,int pos,int val,int op){
	T[u].cnt+=op;
	if(T[u].lef==T[u].rig){
		T[u].sum[0]+=val;return;
	}
	else {
		if(pos<=T[lson].rig)Update(lson,pos,val,op);
		else Update(rson,pos,val,op);
		PushUp(u);
	}
}

int main(){
	int n;
	while(scanf("%d",&n)==1){

		int num=0;
		for(int i=0;i<n;i++){
			scanf("%s",cmd[i]);
			if(cmd[i][0]!='s'){scanf("%d",&dat[i]);tmp[num++]=dat[i];}
		}

		sort(tmp,tmp+num);
		num=unique(tmp,tmp+num)-tmp;

		Build(1,1,num);
		for(int i=0;i<n;i++){
			int pos=lower_bound(tmp,tmp+num,dat[i])-tmp;
			if(cmd[i][0]=='a')Update(1,pos,dat[i],1);
			else if(cmd[i][0]=='d')Update(1,pos,-dat[i],-1);
			else printf("%I64d
",T[1].sum[2]);
		}
	}

}