本文共 2120 字，大约阅读时间需要 7 分钟。
给了 n(1≤n≤100000 个操作，每个操作要么是在集合中添加一个整数(在区间 [1, 109] 中，且保证不在集合中)，要么是删除一个整数（保证在集合中），还有一个操作 sum，询问的是当前集合中，所有元素从小到大排列好之后，下标除以 5 余数为 3 的所有数的和
先把所有的操作存储下来，然后把每一个出现过的整数（添加的和删除的）全部“有序的”离散化，这样，我们再添加或者删除的时候就找得到具体的位置了，接着就是怎么用线段树做的问题了：
可以这样，线段树的每个节点存一个数组 sum[5]，表示当前节点覆盖的区间中，从左到有编号，模 5 为 0,1,2,3,4的所有数的和
每个节点再保存一个当前节点所包含的区间中有多少个数的信息：cnt。那么：
添加的时候就是在相应的位置把整数加进去，并把 cnt+1
删除的时候就是在相应的位置赋值为 0，并把 cnt-1
关于 pushUp 的问题，我们可以这样考虑：
父亲的 cnt 肯定是两个儿子的 cnt 的和
父亲的 sum 肯定赋初值为 左儿子 的 sum
右儿子的 sum[i] 对应的是父亲的 sum[(i+Lson.cnt)%5]，以此作为更新的依据
每一个求和的询问，直接输出根节点的 sum[3] 就行
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 typedef long long LL;11 const int N=100006;12 13 struct data14 {15 int val, fg;16 } op[N];17 int n;18 char hehe[10];19 map ihash;20 vector haha;21 22 struct Interval_Tree23 {24 struct node25 {26 int s, t, cnt;27 LL sum[5];28 void init(int L, int R)29 {30 s=L, t=R, cnt=0;31 for(int i=0; i<5; i++) sum[i]=0;32 }33 } T[N<<2];34 35 void build(int id, int L, int R)36 {37 T[id].init(L, R);38 if(L==R) return;39 int mid=(L+R)>>1;40 build(id<<1, L, mid);41 build(id<<1|1, mid+1, R);42 }43 44 void pushUp(node &x, node &L, node &R)45 {46 x.s=L.s, x.t=R.t, x.cnt=L.cnt+R.cnt;47 for(int i=0; i<5; i++) x.sum[i]=L.sum[i];48 for(int i=0; i<5; i++) x.sum[(L.cnt+i)%5]+=R.sum[i];49 }50 51 void update(int id, int pos, int val)52 {53 if(T[id].s==T[id].t)54 {55 for(int i=0; i<5; i++) T[id].sum[i]=0;56 T[id].sum[1]=val;57 if(val==0) T[id].cnt=0;58 else T[id].cnt=1;59 return;60 }61 int mid=(T[id].s+T[id].t)>>1;62 if(pos<=mid) update(id<<1, pos, val);63 else update(id<<1|1, pos, val);64 pushUp(T[id], T[id<<1], T[id<<1|1]);65 }66 } tree;67 68 int main()69 {70 while(scanf("%d", &n)!=EOF)71 {72 haha.clear();73 for(int i=0; i
转载于:https://www.cnblogs.com/zhj5chengfeng/archive/2013/04/25/3043159.html
HDU 4288