传送门：https://www.luogu.org/problemnew/show/2073#sub
题目背景
小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。
题目描述
这些花都很漂亮，每朵花有一个美丽值W，价格为C。
小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：
操作 含义
1 W C 添加一朵美丽值为W，价格为C的花。
3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。
2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。
-1 完成添加与删除，开始包装花束
若删除操作时没有花，则跳过删除操作。
如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。
请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。
输入格式
若干行，每行一个操作，以-1结束。
输出格式
一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。
样例君
输入
1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
输出
8 5
蒟蒻吐槽
忍不住想说，数据结构好麻烦啊啊。
其实这道题和洛谷1198最大数（传送门）蛮像的，反正我是这么认为。因为蒟蒻太弱了，只能暴力建一棵最大的树。每次加入花时，就把花束末尾的编号++，然后单点修改。对于拔花（滑稽），线段树维护最大值最小值，loc数组记录每个价格的花在数列的哪个位置，要是不想记录的话，也可以在pushup的时候顺便把max和min的位置传上来。
再删除的时候把那个节点的所有值赋成0，代表这个点不再存在了，要是不想写的话，建树的时候打个标记也可以。
为了便于记录答案和输出，我的树里记录了每个点对应的价值和、美丽度和、max值、min值。
代码附上，希望dalao们不要嫌弃哈。O(∩_∩)O！
代码
#include<cstdio> #include<algorithm> using namespace std; const int N=100010; struct node { int c,w,mx,mn; }tr[N<<2]; int ql,qr,w,c,k,n; int loc[N*10]; void update(int o,int l,int r) { if(ql<=l&&qr>=r) { tr[o].c=c; tr[o].w=w; tr[o].mx=tr[o].mn=c; return; } int mid=(l+r)>>1; if(ql<=mid)update(o<<1,l,mid); if(qr>mid)update(o<<1|1,mid+1,r); if(!tr[o<<1].mx&&tr[o<<1|1].mx)tr[o]=tr[o<<1|1]; if(!tr[o<<1].mx&&!tr[o<<1|1].mx)tr[o].w=tr[o].c=tr[o].mx=tr[o].mn=0; if(tr[o<<1].mx&&!tr[o<<1|1].mx)tr[o]=tr[o<<1]; if(tr[o<<1].mx&&tr[o<<1|1].mx) { tr[o].mx=max(tr[o<<1].mx,tr[o<<1|1].mx); tr[o].mn=min(tr[o<<1].mn,tr[o<<1|1].mn); tr[o].w=tr[o<<1].w+tr[o<<1|1].w; tr[o].c=tr[o<<1].c+tr[o<<1|1].c; } } int main() { while(true) { scanf("%d",&k); if(k==1) { scanf("%d%d",&w,&c); if(loc[c])continue; n++; loc[c]=n; ql=qr=n; update(1,1,N); } else if(k==2) { if(!tr[1].mx)continue; ql=qr=loc[tr[1].mx]; loc[tr[1].mx]=0; c=0;w=0; update(1,1,N); } else if(k==3) { if(!tr[1].mn)continue; ql=qr=loc[tr[1].mn]; loc[tr[1].mn]=0; c=0;w=0; update(1,1,N); } else break; } printf("%d %d",tr[1].w,tr[1].c); return 0; }