hdu 4288 Coder (离散化， 线段树，单点更新，区间合并)
题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9
思路：很容易想到的是，由于插入和删除元素造成的位置改变是剧烈的，因此要分别维护i%5==k,k属于0..4的元素的和。
这道题的核心点在于，由于只有1E5个操作，我们可以将元素离散化，这样做的目的是，将每个数和位置一一对应，每个位置用1或者0，表示该位置对应的元素是否在集合中。
考虑线段树，维护6个域，1个是区间中，在集合中的元素个数，剩下5个域，分别表示以该区间的端点为位置1，位置x%i=k的元素的和（k属于0..4)。因此每个叶子节点都是位置1.
考虑PushUp, 区间元素和之间累加，难点在于其他5个域的维护。
假设当前区间为rt,那么对于sum[0..4] (sum代表的就是上面说的要维护的5个域），显然区间rt«1的答案可以直接贡献给rt.
对于rt«1|1的答案，考虑rt«1|1中位置为%5==x的元素和，rt«1中的元素个数为len个，那么rt«1|1中sum[x]对 rt中的sum[(x+len)%5]有贡献。
反推出对rt 中 sum[i]有贡献的是rt«1|1中的sum[(i-len+5)%5)]
1/* ***********************************************
2Author :111qqz
3Created Time :2017年09月26日 星期二 12时42分10秒
4File Name :4288.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n;
36struct Node
37{
38 int cnt; //区间中，在集合中存在的元素的个数。
39 LL sum[5]; //sum[i]表示该区间中，以区间起点为下标1开始计算时，位置为x%5==i时的元素的和。
40}tree[N<<2];
41struct Opt
42{
43 int opt;
44 LL val;
45}qu[N];
46LL H[N],A[N];
47int cnt;
48int Hash( int x)
49{
50 return lower_bound(H,H+cnt,x)-H;
51}
52void PushUp( int rt)
53{
54 tree[rt].cnt = tree[rt<<1].cnt + tree[rt<<1|1].cnt;
55 for ( int i = 0 ; i < 5 ; i++)
56 {
57 int left_len = tree[rt<<1].cnt;
58 tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[((i-left_len)%5+5)%5];
59 }
60}
61void update( int p,int opt,int l,int r,int rt)
62{
63 if (l==r)
64 {
65 if (opt==1)
66 {
67 tree[rt].cnt=1;
68 tree[rt].sum[1]=H[p-1];
69 }
70 else
71 {
72 tree[rt].cnt=0;
73 tree[rt].sum[1]=0;
74 }
75 return ;
76 }
77
78 int m = (l+r)>>1;
79 if (p<=m) update(p,opt,lson);
80 else update(p,opt,rson);
81 PushUp(rt);
82}
83int main()
84{
85 #ifndef ONLINE_JUDGE
86 freopen("./in.txt","r",stdin);
87 #endif
88 while (~scanf("%d",&n))
89 {
90 ms(tree,0);
91 cnt=0;
92 for ( int i = 1 ; i <= n ; i++)
93 {
94 char tmp[5];
95 scanf("%s",tmp);
96 if (tmp[0]=='a')
97 {
98 qu[i].opt=1;
99 int x;
100 scanf("%d",&x);
101 qu[i].val=x;
102 H[cnt++]=x;
103 }else if (tmp[0]=='d')
104 {
105 qu[i].opt=2;
106 int x;
107 scanf("%d",&x);
108 qu[i].val = x;
109 }else
110 {
111 qu[i].opt=3;
112 }
113 }
114 sort(H,H+cnt);
115 cnt = unique(H,H+cnt)-H;
116 //cout<<"cnt:"<<cnt<<endl;
117 for ( int i = 1 ; i <= n ; i++)
118 {
119 LL ans = tree[1].sum[3];
120 if (qu[i].opt==3) printf("%lld\n",ans);
121 else
122 {
123 int x = Hash(qu[i].val)+1;
124 //cout<<"val:"<<qu[i].val<<"x:"<<x<<" H[p-1]:"<<H[x-1]<<endl;
125 update(x,qu[i].opt,1,cnt+1,1);
126 }
127 }
128 }
129 #ifndef ONLINE_JUDGE
130 fclose(stdin);
131 #endif
132 return 0;
133}