简单权值线段树题.1_权值线段树 例题

送花(过程全在注释里)

题目背景

小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。

题目描述

这些花都很漂亮，每朵花有一个美丽值 $W$，价格为 $C$。

小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：

• $1WC$：添加一朵美丽值为 $W$，价格为 $C$ 的花。
  如果此前已经加入了相等价格的花，那么这朵花不能加入花束。
• $2$：删除当前花束里最贵的一朵花。
• $3$：删除当前花束里最便宜的一朵花。
• $-1$：完成添加与删除，开始包装花束。

当花束为空时，忽略操作 $2$ 和 $3$。

请你写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。

输入格式

若干行，每行一个操作，以 $-1$ 结束。

输出格式

一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。

样例 #1

样例输入 #1

1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
1
2
3
4
5
6
7

样例输出 #1

8 5
1

提示

设操作数为 $m$。

• 对于 $20\%$ 数据，$m\le 100$，$1\le W,C\le 10^3$。
• 对于全部数据，$m\le 10^5$，$1\le W,C\le 10^6$。

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+10;
typedef long long ll;
int k,pp,meimei;
struct stu{
	int p,mei;
}tree[N*4];
void pushup(int u){
    tree[u].p=tree[u<<1].p+tree[u<<1|1].p;//左右两子段的区间和(总价格和总美丽值)相加反馈给顶部
    tree[u].mei=tree[u<<1].mei+tree[u<<1|1].mei;
}
void update(int l,int r,int u,int p,int mei){//插入一朵价格为p，美丽值为mei的花
	if(l==r){//到达叶子结点
        if(tree[u].p==p) return;//如果已经有一朵价格为p的花了，则不能加入该花
        tree[u].p=p;//否则更新该点信息
        tree[u].mei=mei;
    }
	else{//未到叶子结点继续折半查找
        int mid=(l+r)>>1;
	    if(p<=mid) update(l,mid,u<<1,p,mei);//查找左子树
	    else update(mid+1,r,u<<1|1,p,mei);//查找右子树
        pushup(u);//对顶部更新
    }
}
void remove(int l,int r,int u,int sign){//删除一朵花
    if(l==r) tree[u]={0,0};//找到该点清空删除
    else{
        int mid=(l+r)>>1;
        if(sign){//sign=1是删除最大值
            if(!tree[u<<1|1].p) remove(l,mid,u<<1,sign); //右区间为空则找左区间
            else remove(mid+1,r,u<<1|1,sign); //否则就找右区间
        }
        else{//sign=0是删除最小值
            if(!tree[u<<1].p) remove(mid+1,r,u<<1|1,sign); //左区间为空则找右区间
            else remove(l,mid,u<<1,sign); //否则就找左区间
        }
        pushup(u);//对顶部更新
    }
}
int main(){
    while(scanf("%d",&k)!=EOF){
        if(k==-1) break;
        if(k==1){
            scanf("%d %d",&meimei,&pp);
            update(1,N,1,pp,meimei);
        }
        else if(tree[1].p==0) continue;
        else if(k==2) remove(1,N,1,1);
        else remove(1,N,1,0);
    }
    cout<<tree[1].mei<<" "<<tree[1].p<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53