题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4288
题目大意：有n个操作和一个集合（初始为空），并且集合内元素满足按顺序排列。
现有三种操作：
add x ： 将元素x加入集合中。
del x： 将集合中的x元素删除。
sum： 统计集合中元素下标满足i%5==3的总和。
解题思路： 以为在线段树方面小有火候，现在发现自己在线段树方面还没起火，处于冒烟阶段。
这题让我蛋蛋又碎了，WA了一个晚上，各种调试，最后发现是数组必须开成节点4倍大小，我只开了两倍大小，导致了一个晚上的悲剧（why？个人认为两倍足够了，可以证明的）。
可以想到五颗线段树的操作，离线处理还是比较难想到的。先离线处理可以知道我们要处理多少个点，进行建树操作。然后接下来对这n个操作进行即时更新，遇见add x，则往x的对应位置进行传递，直到达到叶子节点，更新叶子节点sz为1，del x则更新对应叶子节点sz为0。然后递归回去上传更新，父亲的 sum[u][i]等于左孩子的sum[u][i]，而右孩子上传时则需要处理，因为位置发生了变化，cnt表示父亲的左孩子有cnt个实节点，所以右孩子上传时下标是从cnt+i开始，五种状态随时更新，随时相互转换。
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define lz 2*u,l,mid 8 #define rz 2*u+1,mid+1,r 9 const int maxn=100005; 10 __int64 sum[4*maxn][6]; ///开成2*maxn WA了一个晚上，蛋蛋都碎了 11 int a[maxn], X[maxn], sz[4*maxn]; 12 char str[maxn][20]; 13 14 void push_up(int u) 15 { 16 sz[u]=sz[2*u]+sz[2*u+1]; 17 for(int i=0; i<5; i++) sum[u][i]=sum[2*u][i]; 18 for(int i=0; i<5; i++) sum[u][(i+sz[2*u])%5]+=sum[2*u+1][i]; 19 } 20 21 void build(int u, int l, int r) 22 { 23 sz[u]=0; 24 for(int i=0; i<5; i++) sum[u][i]=0; 25 if(l==r) return ; 26 int mid=(l+r)>>1; 27 build(lz); 28 build(rz); 29 } 30 31 void Update(int u, int l, int r, int pos, int c) 32 { 33 if(l==r) 34 { 35 sz[u]=c; 36 sum[u][1]=c*X[l]; 37 return ; 38 } 39 int mid=(l+r)>>1; 40 if(pos<=mid) Update(lz,pos,c); 41 else Update(rz,pos,c); 42 push_up(u); 43 } 44 45 int main() 46 { 47 int n; 48 while(cin >> n) 49 { 50 int num=0, pos; 51 for(int i=0; i<n; i++) 52 { 53 scanf("%s",str[i]); 54 if(str[i][0]!='s') 55 { 56 scanf("%d",&a[i]); 57 if(str[i][0]=='a') X[++num]=a[i]; 58 } 59 } 60 sort(X+1,X+num+1); 61 int ep=unique(X+1,X+num+1)-(X+1); ///去重 62 build(1,1,ep); 63 for(int i=0; i<n; i++) 64 { 65 if(str[i][0]=='a') pos=upper_bound(X+1,X+ep+1,a[i])-(X+1), Update(1,1,ep,pos,1); 66 else if(str[i][0]=='d') pos=upper_bound(X+1,X+ep+1,a[i])-(X+1), Update(1,1,ep,pos,0); 67 else printf("%I64d\n",sum[1][3]); 68 } 69 } 70 return 0; 71 }