思路：
线段树；
代码：
#include <bits/stdc++.h> using namespace std; #define maxn 100005 struct TreeNodeType { int l,r,ci,sum,num,mid; }; struct TreeNodeType tree[maxn<<2]; 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=1;now=0; char Cget=getchar(); while(Cget>'9'||Cget<'0') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; 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>>1; build(now<<1,l,tree[now].mid); build(now<<1|1,tree[now].mid+1,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<<1,to,x); else updata0(now<<1|1,to,x); tree[now].num=tree[now<<1].num+tree[now<<1|1].num; tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; tree[now].ci=tree[now<<1].ci+tree[now<<1|1].ci; } void updata1(int now) { if(tree[now].l==tree[now].r) { if_[tree[now].l]=false; tree[now].num=0; tree[now].sum=0; tree[now].ci=0; return; } if(tree[now<<1|1].num)updata1(now<<1|1); else updata1(now<<1); tree[now].num=tree[now<<1].num+tree[now<<1|1].num; tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; tree[now].ci=tree[now<<1].ci+tree[now<<1|1].ci; } void updata2(int now) { if(tree[now].l==tree[now].r) { if_[tree[now].l]=false; tree[now].num=0; tree[now].sum=0; tree[now].ci=0; return; } if(tree[now<<1].num)updata2(now<<1); else updata2(now<<1|1); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; tree[now].num=tree[now<<1].num+tree[now<<1|1].num; tree[now].ci=tree[now<<1].ci+tree[now<<1|1].ci; } int main() { int now=1; in(ai[now].op); while(ai[now].op!=-1) { if(ai[now].op==1) { in(ai[now].w); in(ai[now].c); bi[++cnt]=ai[now].c; } in(ai[++now].op); } m=now,sort(bi+1,bi+cnt+1); size=unique(bi+1,bi+cnt+1)-bi-1; build(1,1,size); for(int i=1;i<=m;i++) { if(ai[i].op==1) { ai[i].c=lower_bound(bi+1,bi+size+1,ai[i].c)-bi; if(!if_[ai[i].c]) updata0(1,ai[i].c,ai[i].w); } if(ai[i].op==2) if(tree[1].num)updata1(1); if(ai[i].op==3) if(tree[1].num)updata2(1); } printf("%d %d ",tree[1].sum,tree[1].ci); return 0; }