题解：
对于这个题目，先想到是建立5棵Splay，然后每次更新把后面一段区间的树切下来，然后再转圈圈把切下来的树和别的树合并。
但是感觉写起来太麻烦就放弃了。
建立5棵线段树。
然后 seg[rt][i]代表的是只考虑当前所管辖的区间中的情况下， 下标对5取余之后为 i 的那些值的和。
最重要的一点是更新。
for(int i = 0; i < 5; ++i) seg[i][rt] = seg[i][rt<<1] + seg[((i-sz[rt<<1]%5)+5)%5][rt<<1|1];
我们可以通过左边的sz，来找到右边的数如果加上前面的sz之后，第i个值是哪里过来的。
代码：
#include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 1e5 + 100; int sz[N<<2]; LL seg[5][N<<2]; int op[N], v[N]; int b[N], m; char s[N]; int id(int x){ return lower_bound(b+1, b+1+m, x) - b; } void Updata(int L, int v, int l, int r, int rt){ if(l == r){ seg[1][rt] += b[L] * v; sz[rt] += v; return ; } int m = l+r >> 1; if(L <= m) Updata(L, v, lson); else Updata(L, v, rson); sz[rt] += v; for(int i = 0; i < 5; ++i) seg[i][rt] = seg[i][rt<<1] + seg[((i-sz[rt<<1]%5)+5)%5][rt<<1|1]; } int main(){ int q; scanf("%d", &q); for(int i = 1; i <= q; ++i){ scanf("%s", s); if(s[0] == ‘a‘) { op[i] = 1; scanf("%d", &v[i]); b[++m] = v[i]; } else if(s[0] == ‘d‘){ op[i] = -1; scanf("%d", &v[i]); } } sort(b+1, b+1+m); m = unique(b+1, b+1+m) - (b+1); for(int i = 1; i <= q; ++i){ if(!op[i]) printf("%lld\n", seg[3][1]); else Updata(id(v[i]), op[i], 1, m, 1); } return 0; } /* 4 add 1 add 2 add 3 sum */
CodeForces 85D Sum of Medians Splay | 线段树
原文：https://www.cnblogs.com/MingSD/p/10882107.html
