此题有多种方法能够AC，其中最短的是用vector暴力：
using namespace std;
int n,x;
vector<int> v;
int main() {
cin>>n;
while(n--){
string s;
cin>>s;
if(s[0]=='s'){
long long r=0;
for(int i=2;i<v.size();i+=5)r+=v[i];
cout<<r<<endl;
}
else{
cin>>x;
if(s[0]=='a')v.insert(pos,x);
else v.erase(pos);
}
}
return 0;
}
这也是Codeforces上最短的代码。
第二种方法是用线段树，每个节点保存模5余0～4的和以及区间长度（当然需要离散化），答案就是根结点模5余3的和。代码如下：
using namespace std;
int n,cnt,sz[400005],rev[100005];
long long sgt[400005][5];
pair<string,int> q[100005];
map<int,int> disc;
void modify(int x,int l,int r,int t,int v){
if(l==r){
sgt[x][1]=v*rev[t];
sz[x]=v;
return;
}
int mid=(l+r)>>1;
if(t<=mid)modify(x*2+1,l,mid,t,v);
else modify(x*2+2,mid+1,r,t,v);
sz[x]=sz[x*2+1]+sz[x*2+2];
for(int i=0;i<5;i++){
sgt[x][i]=sgt[x*2+1][i]+sgt[x*2+2][(i-sz[x*2+1]%5+5)%5];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>q[i].first;
if(q[i].first[0]!='s')cin>>q[i].second;
disc[q[i].second];
}
for(auto &i:disc){
i.second=++cnt;
rev[cnt]=i.first;
}
for(int i=0;i<n;i++){
if(q[i].first[0]=='a')modify(0,1,cnt,disc[q[i].second],1);
else if(q[i].first[0]=='d')modify(0,1,cnt,disc[q[i].second],0);
else cout<<sgt[0][3]<<endl;
}
return 0;
}
还可以用Treap来维护，这样就可以在线做，不用离散化了，但是代码难度也要大不少。旋转版本的Treap代码如下（这是我第一次写Treap）:
using namespace std;
int n;
struct node{
int v,r,sz;
node* ch[2];
long long sum[5];
void maintain(){
int pre=0,s=1;
if(ch[0]!=NULL)s+=ch[0]->sz;
pre=s;
if(ch[1]!=NULL)s+=ch[1]->sz;
sz=s;
set0(sum);
sum[(pre%5)]=v;
for(int i=0;i<5;i++){
if(ch[0]!=NULL)sum[i]+=ch[0]->sum[i];
if(ch[1]!=NULL)sum[(pre+i)%5]+=ch[1]->sum[i];
}
}
node(int x){
this->v=x;
this->r=rand();
this->sz=1;
this->ch[0]=this->ch[1]=NULL;
set0(sum);
this->sum[1]=x;
}
};
node* rt;
void rotate(node* &x,int d){
node* k=x->ch[d^1];
x->ch[d^1]=k->ch[d];
k->ch[d]=x;
x->maintain();
k->maintain();
x=k;
}
void add(node* &x,int v){
if(x==NULL){
x=new node(v);
return;
}
bool nxt=v>(x->v);
add(x->ch[nxt],v);
if((x->ch[nxt]->r)>(x->r))rotate(x,nxt^1);
if(x!=NULL)x->maintain();
}
void del(node* &x,int v){
if((x->v)==v){
if(x->ch[0]!=NULL && x->ch[1]!=NULL){
bool nxt=(x->ch[0]->r)>(x->ch[1]->r);
rotate(x,nxt);
del(x->ch[nxt],v);
if(x!=NULL)x->maintain();
}
else if(x->ch[0]!=NULL)x=x->ch[0];
else x=x->ch[1];
}
else{
del(x->ch[v>(x->v)],v);
if(x!=NULL)x->maintain();
}
}
int main(){
srand((unsigned)time(NULL));
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
while(n--){
string opt;
cin>>opt;
if(opt[0]=='s'){
if(rt==NULL)cout<<"0\n";
else cout<<(rt->sum[3])<<endl;
}
else{
int x;
cin>>x;
if(opt[0]=='a')add(rt,x);
else del(rt,x);
}
}
return 0;
}
下面是非旋Treap的代码:
using namespace std;
int n;
struct node{
int v,w,sz;
node *l,*r;
long long sum[5];
void maintain(){
int pre=0,s=1;
if(l!=NULL)s+=l->sz;
pre=s;
if(r!=NULL)s+=r->sz;
sz=s;
set0(sum);
sum[(pre%5)]=v;
for(int i=0;i<5;i++){
if(l!=NULL)sum[i]+=l->sum[i];
if(r!=NULL)sum[(pre+i)%5]+=r->sum[i];
}
}
node(int x){
this->v=x;
this->w=rand();
this->sz=1;
this->l=this->r=NULL;
set0(sum);
this->sum[1]=x;
}
};
node* rt;
void Split(node *x,node **l,node **r,int v){
if(x==NULL)(*l)=(*r)=NULL;
else if(x->v<v){
*l=x;
Split(x->r,&x->r,r,v);
}
else{
*r=x;
Split(x->l,l,&x->l,v);
}
if((*l)!=NULL)(*l)->maintain();
if((*r)!=NULL)(*r)->maintain();
}
void Merge(node **x,node *l,node *r){
if(l==NULL || r==NULL){
*x=(l==NULL)?r:l;
return;
}
if(l->w<r->w){
*x=l;
Merge(&(*x)->r,(*x)->r,r);
}
else{
*x=r;
Merge(&(*x)->l,l,(*x)->l);
}
if((*x)!=NULL)(*x)->maintain();
}
void add(node **x,int v){
node *l,*r,*m;
Split(*x,&l,&r,v);
Merge(&m,l,new node(v));
Merge(x,m,r);
}
void del(node **x,int v){
node *l,*m,*r,*tmp;
Split(*x,&l,&tmp,v);
Split(tmp,&m,&r,v+1);
Merge(x,l,r);
}
int main(){
srand((unsigned)time(NULL));
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
while(n--){
string opt;
cin>>opt;
if(opt[0]=='s'){
if(rt==NULL)cout<<"0\n";
else cout<<(rt->sum[3])<<endl;
}
else{
int x;
cin>>x;
if(opt[0]=='a'){
if(rt==NULL)rt=new node(x);
else add(&rt,x);
}
else del(&rt,x);
}
}
return 0;
}