基本上算是抄的代码。。。。
线段树,维护一个sum数组,sum数组存的是当前区间段以第1-5个数为起点的间隔为5的数的总和
离线化处理也是以前从没有见过的
code:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define LL __int64 using namespace std; const int MAXN = 110005; struct seg { int left,right,cnt; LL sum[5]; }tree[MAXN<<2]; void build(int rt,int l,int r) { tree[rt].left=l; tree[rt].right=r; tree[rt].cnt=0; if(l==r) { return; } memset(tree[rt].sum,0,sizeof(tree[rt].sum)); int m=(l+r)>>1; build(rt<<1,l,m); build(rt<<1|1,m+1,r); } void update(int flag,int rt,int pos,int val) { if(tree[rt].left==tree[rt].right) { tree[rt].cnt=flag; tree[rt].sum[0]=flag*val; return ; } int m=(tree[rt].left+tree[rt].right)>>1; if(pos<=m) { update(flag,rt<<1,pos,val); }else{ update(flag,rt<<1|1,pos,val); } tree[rt].cnt=tree[rt<<1].cnt+tree[rt<<1|1].cnt; for(int i=0;i<5;i++) { tree[rt].sum[i]=tree[rt<<1].sum[i]+tree[rt<<1|1].sum[((i-tree[rt<<1].cnt)%5+5)%5]; } } char str[MAXN][3]; int q[MAXN],a[MAXN],tot,n,p; int main() { int i; while(~scanf("%d",&n)) { tot=1; for(i=1;i<=n;i++) { scanf("%s",str[i]); if(str[i][0]!='s') { scanf("%d",&q[i]); a[tot++]=q[i]; } } sort(a+1,a+tot); tot=unique(a+1,a+tot)-a; //printf("tot:%d\n",tot); build(1,1,tot); for(i=1;i<=n;i++) { if(str[i][0]=='a') { p=lower_bound(a+1,a+tot,q[i])-a; update(1,1,p,q[i]); }else if(str[i][0]=='d'){ p=lower_bound(a+1,a+tot,q[i])-a; update(0,1,p,q[i]); }else{ printf("%I64d\n",tree[1].sum[2]); } } } return 0; }