codeforces85D：Sum of Medians
2016-10-25 09:24:48         来源：qzh_1430586275的博客

1、题意：维护一个集合，支持三种操作，向集合内添加或删除元素元素和查询里面排名取余5等于3的数的和，操作数n≤105元素的值≤109
2、分析：讲个笑话，这个题用vector纯模拟可以AC。

```#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define M 400010
#define LL long long
#define VI vector
#define inf 2147483647
#define MOD 1000000007
#define rep(i, x, y) for(int i = (x); i <= (y); i ++)
#define drep(i, x, y) for(int i = (x); i >= (y); i --)

char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

namespace segment_tree{
struct Node{
LL a[5]; int sum;

inline void print(){
rep(i, 0, 4) printf("%I64d ", a[i]);
printf("%d \n", sum);
}
} q[M];
int root;

inline void update(int o, int y){
if(y > 0) q[o] = (Node){y, 0, 0, 0, 0, 1};
else q[o] = (Node){0, 0, 0, 0, 0, 0};
}

inline void pushup(int o){
int l = q[2 * o].sum;
rep(i, 0, 4) q[o].a[i] = q[2 * o].a[i] + q[2 * o + 1].a[((i - l) % 5 + 5) % 5];
q[o].sum = q[2 * o].sum + q[2 * o + 1].sum;
}

inline void add(int l, int r, int o, int x, int y){
if(l == r){
update(o, y);
return;
}
int mid = (l + r) / 2;
if(x <= mid) add(l, mid, 2 * o, x, y);
else add(mid + 1, r, 2 * o + 1, x, y);
pushup(o);
}

}

struct ops{
int op, x, y;
} a[M];
pair b[M];
int cnt;
int len;

int main(){
using namespace segment_tree; root = 1;
int n = read(); char op[10];
rep(i, 1, n){
scanf("%s", op);
if(op[0] == 'a'){
a[i] = (ops){1, x, 0};
b[++ cnt] = make_pair(x, i);
}
else if(op[0] == 'd'){
a[i] = (ops){2, x, 0};
b[++ cnt] = make_pair(x, i);
}
else{
a[i] = (ops){3, 0, 0};
}
}
sort(b + 1, b + cnt + 1);
rep(i, 1, cnt){
if(b[i].first != b[i - 1].first) len ++;
a[b[i].second].y = len;
}
/*rep(i, 1, n){
printf("%d %d %d\n", a[i].op, a[i].x, a[i].y);
}*/
rep(i, 1, n){
if(a[i].op == 1){
}
else if(a[i].op == 2){
}
else{
printf("%I64d\n", q[1].a[2]);
//  q[1].print();
}
}
return 0;
}```