Sum of Medians
题解：
对于这个题目，先想到是建立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]);elseUpdata(id(v[i]), op[i], 1, m, 1);}return 0;}/*4add 1add 2add 3sum*/
View Code
