
9 add 1 add 2 add 3 add 4 add 5 sum add 6 del 3 sum 6 add 1 add 3 add 5 add 7 add 9 sum
3 4 5HintC++ maybe run faster than G++ in this problem.
e5),有三种操作,加一个数,删一个数,求和,其中数小于1e9,求和的是
其中a是排过续的。#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int m,n;
LL sum[5][maxn<<2];
int cnt[maxn<<2];
vector<int> vi;
int demand[maxn];
int num[maxn];
void init() {
vi.clear();
memset(sum,0,sizeof sum);
memset(cnt,0,sizeof cnt);
}
void input() {
for(int i = 0; i < m; i++) {
char st[20];
scanf("%s",st);
if(st[0]=='a') {
scanf("%d",&num[i]);
vi.push_back(num[i]);
demand[i] = 1;
}
else if(st[0]=='d') {
scanf("%d",&num[i]);
demand[i] = 0;
}else {
demand[i] = 2;
}
}
sort(vi.begin(),vi.end());
n = vi.size();
}
void pushUP(int rt) {
cnt[rt] = cnt[rt<<1]+cnt[rt<<1|1];
int dir = cnt[rt<<1]%5;
for(int i = 0; i < 5; i++) {
sum[i][rt] = sum[i][rt<<1]+sum[((i-dir)%5+5)%5][rt<<1|1];
}
}
void update(int pos,int flag,int l,int r,int rt) {
if(l==r) {
if(flag) {
sum[1][rt] = vi[pos];
cnt[rt] = 1;
}else {
sum[1][rt] = 0;
cnt[rt] = 0;
}
return;
}
int mid = (l+r)>>1;
if(pos <= mid) {
update(pos,flag,l,mid,rt<<1);
}else {
update(pos,flag,mid+1,r,rt<<1|1);
}
pushUP(rt);
}
void solve() {
for(int i = 0; i < m; i++) {
if(demand[i]==2) {
printf("%I64d\n",sum[3][1]);
}
else {
int key = lower_bound(vi.begin(),vi.end(),num[i])-vi.begin();
update(key,demand[i],0,n-1,1);
}
}
}
int main(){
while(~scanf("%d",&m)) {
init();
input();
solve();
}
return 0;
}
原文:http://blog.csdn.net/mowayao/article/details/39026247