题意:

你要维护一个集合a,每次你要支持加入一个数,删除一个数,或者求排序后

的值

链接:http://codeforces.com/contest/85/problem/D

做法一:

直接vector暴力,暴力出奇迹

vector居然有神奇的insert函数...我给跪了!

不知道set暴力能不能过...

注意要用GNU C++才能过,理由未知,MS C++会TLE

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
vector<int> v;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int n;
    scanf("%d",&n);
    int i;
    int flag=0;
    long long ans;
    for (i=0;i<n;i++)
    {
        static char a[105];
        int x;
        scanf("%s",a);
        if (a[0]=='a')
        {
            scanf("%d",&x);
            v.insert(lower_bound(v.begin(),v.end(),x),x);
            flag=0;
        }
        if (a[0]=='d')
        {
            scanf("%d",&x);
            v.erase(lower_bound(v.begin(),v.end(),x));
            flag=0;
        }
        if (a[0]=='s')
        {
            if (flag==1)
            {
                cout<<ans<<'\n';
                continue;
            }
            ans=0;
            int i;
            for (i=2;i<v.size();i+=5)
            {
                ans+=v[i];
            }
            cout<<ans<<'\n';
            flag=1;
        }
    }
    return 0;
}

做法二:

线段树来做

先离线

找出所有的值

然后建线段树

然后维护每个位置是否在,以及mod 5为0,1,2,3,4的值

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char oper[100005];
int oper_num[100005];
int a[100005];
map<int,int> ma;
long long val[1<<18][5];
int size[1<<18];
void change(int num,int l,int r,int k,int t,int x)
{
    if (l==r-1)
    {
        val[num][0]+=x*t;
        size[num]+=x;
        return;
    }
    int mid=(l+r)/2;
    if (k<mid)
    {
        change(num*2+1,l,mid,k,t,x);
    }
    else
    {
        change(num*2+2,mid,r,k,t,x);
    }
    size[num]=size[num*2+1]+size[num*2+2];
    int i;
    for (i=0;i<5;i++)
    {
        val[num][i]=val[num*2+1][i]+val[num*2+2][((i-size[num*2+1])%5+5)%5];
    }
}
long long query(int num,int l,int r,int l0,int r0)
{
    return val[num][2];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int n;
    scanf("%d",&n);
    int i;
    int t=0;
    for (i=0;i<n;i++)
    {
        static char opers[1005];
        scanf("%s",opers);
        oper[i]=opers[0];
        if (oper[i]!='s')
        {
            scanf("%d",&oper_num[i]);
            a[t++]=oper_num[i];
        }
    }
    sort(a,a+t);
    t=unique(a,a+t)-a;
    for (i=0;i<t;i++)
    {
        ma[a[i]]=i;
    }
    for (i=0;i<n;i++)
    {
        if (oper[i]=='s')
        {
            cout<<query(0,0,n,0,n)<<'\n';
        }
        else if (oper[i]=='a')
        {
            change(0,0,n,ma[oper_num[i]],oper_num[i],1);
        }
        else
        {
            change(0,0,n,ma[oper_num[i]],oper_num[i],-1);
        }
    }
    return 0;
}

做法三:

treap直接上...

维护的和线段树差不多...

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    node * ch[2];
    int val;
    int size;
    int weight;
    long long sum[5];
};
node * root;
node * null;
node * new_node(int val)
{
    static node a[300005];
    static int top=0;
    node * t=&a[top++];
    t->val=val;
    t->weight=rand();
    t->size=1;
    t->ch[0]=null;
    t->ch[1]=null;
    t->sum[0]=val;
    t->sum[1]=0;
    t->sum[2]=0;
    t->sum[3]=0;
    t->sum[4]=0;
    return t;
}
void update(node * &x)
{
    int i;
    for (i=0;i<5;i++)
    {
        x->sum[i]=x->ch[0]->sum[i];
    }
    int k=x->ch[0]->size;
    x->sum[k%5]+=x->val;
    k++;
    for (i=0;i<5;i++)
    {
        x->sum[(k+i)%5]+=x->ch[1]->sum[i];
    }
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]=x;
    y->size=x->size;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    update(x);
    update(y);
    x=y;
}
void insert_node(node * &now,node * x)
{
    if (now==null)
    {
        now=x;
        return;
    }
    int c;
    if (x->val>now->val)
    {
        c=1;
    }
    else
    {
        c=0;
    }
    insert_node(now->ch[c],x);
    now->size++;
    update(now);
    if (now->ch[c]->weight>now->weight)
    {
        rotate(now,c);
    }
}
void delete_node(node * &now,int val)
{
    now->size--;
    if (now->val==val)
    {
        int c;
        if (now->ch[0]->weight<now->ch[1]->weight)
        {
            c=1;
        }
        else
        {
            c=0;
            if (now->ch[0]==null)
            {
                now=null;
                return;
            }
        }
        rotate(now,c);
        delete_node(now->ch[!c],val);
        update(now);
    }
    else
    {
        if (now->val<val)
        {
            delete_node(now->ch[1],val);
            update(now);
        }
        else
        {
            delete_node(now->ch[0],val);
            update(now);
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    null=new_node(0);
    null->ch[0]=null;
    null->ch[1]=null;
    null->size=0;
    null->weight=-1;
    root=null;
    for (i=0;i<n;i++)
    {
        static char a[1005];
        scanf("%s",a);
        if (a[0]=='a')
        {
            int x;
            scanf("%d",&x);
            insert_node(root,new_node(x));
        }
        else if (a[0]=='d')
        {
            int x;
            scanf("%d",&x);
            delete_node(root,x);
        }
        else
        {
            cout<<root->sum[2]<<'\n';
        }
    }
    return 0;
}