AC日记——送花 洛谷 P2073

送花

思路：

　　线段树；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 100005

struct TreeNodeType {

    int l,r,ci,sum,num,mid;

};

struct TreeNodeType tree[maxn<<];

struct OperationType {

    int op,w,c;

};

struct OperationType ai[maxn];

int n,m,bi[maxn],cnt,size;

bool if_[maxn];

inline void in(int &now)

{

    int if_z=;now=;

    char Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

void build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r;

    if(l==r) return;tree[now].mid=l+r>>;

    build(now<<,l,tree[now].mid);

    build(now<<|,tree[now].mid+,r);

}

void updata0(int now,int to,int x)

{

    if(tree[now].l==tree[now].r)

    {

        if_[tree[now].l]=true;

        tree[now].num++;

        tree[now].sum+=x;

        tree[now].ci+=bi[tree[now].l];

        return;

    }

    if(to<=tree[now].mid) updata0(now<<,to,x);

    else updata0(now<<|,to,x);

    tree[now].num=tree[now<<].num+tree[now<<|].num;

    tree[now].sum=tree[now<<].sum+tree[now<<|].sum;

    tree[now].ci=tree[now<<].ci+tree[now<<|].ci;

}

void updata1(int now)

{

    if(tree[now].l==tree[now].r)

    {

        if_[tree[now].l]=false;

        tree[now].num=;

        tree[now].sum=;

        tree[now].ci=;

        return;

    }

    if(tree[now<<|].num)updata1(now<<|);

    else updata1(now<<);

    tree[now].num=tree[now<<].num+tree[now<<|].num;

    tree[now].sum=tree[now<<].sum+tree[now<<|].sum;

    tree[now].ci=tree[now<<].ci+tree[now<<|].ci;

}

void updata2(int now)

{

    if(tree[now].l==tree[now].r)

    {

        if_[tree[now].l]=false;

        tree[now].num=;

        tree[now].sum=;

        tree[now].ci=;

        return;

    }

    if(tree[now<<].num)updata2(now<<);

    else updata2(now<<|);

    tree[now].sum=tree[now<<].sum+tree[now<<|].sum;

    tree[now].num=tree[now<<].num+tree[now<<|].num;

    tree[now].ci=tree[now<<].ci+tree[now<<|].ci;

}

int main()

{

    int now=;

    in(ai[now].op);

    while(ai[now].op!=-)

    {

        if(ai[now].op==)

        {

            in(ai[now].w);

            in(ai[now].c);

            bi[++cnt]=ai[now].c;

        }

        in(ai[++now].op);

    }

    m=now,sort(bi+,bi+cnt+);

    size=unique(bi+,bi+cnt+)-bi-;

    build(,,size);

    for(int i=;i<=m;i++)

    {

        if(ai[i].op==)

        {

            ai[i].c=lower_bound(bi+,bi+size+,ai[i].c)-bi;

            if(!if_[ai[i].c]) updata0(,ai[i].c,ai[i].w);

        }

        if(ai[i].op==) if(tree[].num)updata1();

        if(ai[i].op==) if(tree[].num)updata2();

    }

    printf("%d %d\n",tree[].sum,tree[].ci);

    return ;

}