HDU 4288 线段树+离散化

题意：

n个操作

在[1, 100000]  的区间上add 或del数( 必不会重复添加或删除不存在的数)

sum 求出整个集合中 (下标%5 == 3 位置) 的数   的和

注意数据类型要64位

#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <functional>
#include <map>

#define N 101000
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define Mid(x,y) ((x+y)>>1)
#define ll __int64
using namespace std;
inline ll Max(ll a, ll b){ return a>b?a:b;}
inline ll Min(ll a, ll b){ return a<b?a:b;}

ll Point[N];

struct node{
	int l,r;
	ll sum[5];
	int num;
}tree[N*4];

void build( int l, int r, int id){
	tree[id].l = l,  tree[id].r = r;
	memset(tree[id].sum,0,sizeof(tree[id].sum));
	tree[id].num = 0;

	if(l==r)return ;
	int mid = Mid(l, r);
	build(l, mid, L(id));
	build(mid+1, r, R(id));
}
void Updata_up(int id){
		tree[id].num = tree[L(id)].num + tree[R(id)].num ;

	for(int i=0;i<5;i++)
		tree[id].sum[i] = tree[L(id)].sum[i];
	
	for(int i=0;i<5;i++) tree[id].sum[ (tree[L(id)].num + i)%5 ] += tree[R(id)].sum[i];

}
void insert(int pos, int id, ll data, bool add){										// add = true 插入data =false 删除data
	if(tree[id].l == tree[id].r){
		if(add)
		{ tree[id].num = 1; tree[id].sum[1] = data;}
		else 
		{ tree[id].num = 0; tree[id].sum[1] = 0; }

		return ;
	}

	int mid = Mid(tree[id].l, tree[id].r);

	if( pos <= mid) insert(pos, L(id), data, add);
	else			insert(pos, R(id), data, add);

	Updata_up(id);
}

struct QUE{
	char c;
	ll u;
}que[N];
set<ll> tempset;

map<ll, int> mymap;

void Input(int n){
	ll u; char s[5];
	tempset.clear();
	mymap.clear();		
	for(int i = 1; i <= n; i++){
		scanf("%s", s);
		que[i].c = s[0];

		if(s[0]!='s')scanf("%I64d",&u), que[i].u = u,	tempset.insert(u);
	}

	set<ll> ::iterator p = tempset.begin();
	int size = tempset.size();
	for(int i = 1; i <= size ; i++,p++){
		mymap.insert(pair<ll, int>(*p, i));
		Point[i] = *p;
	}
}
int go(ll x){
	return mymap.find(x) -> second;
}
int main(){
	int n;
	while(~scanf("%d",&n)){
		build(1,100000,1);

		Input(n);

		for(int i = 1; i<=n; i++){
			ll u = que[i].u;
			if(que[i].c == 'a')				
				insert(go(u),1,u,1);

			else if(que[i].c == 'd')
				insert(go(u),1,u,0);

			else if(que[i].c == 's')
				printf("%I64d
", tree[1].sum[3]);


		}
	}
	return 0;
}
/* 
9
add 1
add 2
add 3
add 4
add 5
sum
add 6
del 3
sum

ans:
3
4

6
add 1
add 3
add 5
add 7
add 9
sum

ans:
5


*/