P14962 [LBA-OI R2 A] 一次买够题解

P14962 [LBA-OI R2 A] 一次买够

题目背景

小清新签到题~

题目描述

小 Y 非常有钱，所以她可以买下所有她想要的东西。

今天，她来到商店购物。商店有nnn件商品，第iii件商品的价格为viv_ivi​，性价比为wiw_iwi​。一开始，小 Y 会买下性价比最大的所有商品（如果有多个就全部买下）。接下来，有mmm个事件依次发生，第i (1≤i≤m)i\;(1 \leq i \leq m)i(1≤i≤m)个事件可能为以下两种类型之一：

1. 新增一件价格为xix_ixi​，性价比为yiy_iyi​的商品，其编号为n+in+in+i；
2. 将编号为xix_ixi​的商品的性价比更改为yiy_iyi​。

请注意，一旦小 Y 买下了某件商品，之后即使这件商品的性价比降低，小 Y 也不会出售这件商品。

每次事件后，计算小 Y 已买下商品中的最低性价比LLL，小 Y 会在此时买下所有性价比≥L\ge L≥L的未被购买的商品。

作为小 Y 的生活助理，你需要统计每次事件后小 Y 的总花销。

输入格式

第一行，两个整数n,mn, mn,m，分别表示商品数与事件数。

接下来nnn行，第iii行包含两个整数vi,wiv_i, w_ivi​,wi​。

接下来mmm行，第iii行包含三个整数oi,xi,yio_i, x_i, y_ioi​,xi​,yi​，其中oi=1o_i = 1oi​=1表明事件iii是新增商品事件，oi=2o_i = 2oi​=2表明事件iii是修改性价比事件。

输出格式

输出共mmm行。第iii行包含一个整数，表示事件iii后小 Y 的总花销。

输入输出样例 #1

输入 #1

6 4 1 1 1 2 1 3 1 4 1 5 1 5 2 5 4 1 10 3 2 8 4 2 5 2

输出 #1

3 3 13 15

输入输出样例 #2

输入 #2

5 5 11 4 13 6 14 3 20 8 0 5 2 4 5 2 5 0 2 4 10 1 12 2 2 1 0

输出 #2

33 58 58 70 70

说明/提示

样例解释 1

初始，编号为5,65, 65,6的商品性价比最高，因此所有小 Y 购买的商品为{5,6}\{5, 6\}{5,6}。

事件111中，商品555的性价比被修改为444。此时有w4≥w5w_4 \geq w_5w4​≥w5​，因此小 Y 购买商品444，而其余商品仍未被购买。此时所有小 Y 购买的商品为{4,5,6}\{4, 5, 6\}{4,5,6}。

事件222中，新增了一件商品，其编号为6+2=86+2=86+2=8，但其性价比只有333，因此小 Y 没有购买它。

事件333中，商品888的性价比被修改为444，此时小 Y 购买商品888，现在所有她购买的商品为{4,5,6,8}\{4, 5, 6, 8\}{4,5,6,8}。

事件444中，商品555的性价比被修改为222，最终所有小 Y 购买的商品为{2,3,4,5,6,8}\{2, 3, 4, 5, 6, 8\}{2,3,4,5,6,8}。

数据范围

对于所有数据：保证1≤n≤2×1051 \leq n \leq 2\times 10^51≤n≤2×105，1≤m≤2×1051 \leq m \leq 2\times 10^51≤m≤2×105，0≤vi,wi,yi≤1090 \leq v_i, w_i, y_i \leq 10^90≤vi​,wi​,yi​≤109，oi∈{1,2}o_i \in \{1, 2\}oi​∈{1,2}。若oi=1o_i = 1oi​=1，则0≤xi≤1090 \leq x_i \leq 10^90≤xi​≤109，否则保证编号为xix_ixi​的商品已经存在。

思路

用两个堆维护即可。

代码见下

#include<bits/stdc++.h>usingnamespacestd;longlongn,m,op=0,l=0,o,x,y;structone{longlongu,w,i,x,zw;}a[500005];structtwo{longlongw,i,zw;};booloperator<(one a1,one b1){returna1.w<b1.w;}booloperator<(two a1,two b1){returna1.w>b1.w;}priority_queue<one>q;priority_queue<two>w;map<longlong,longlong>mp;intmain(){cin>>n>>m;for(inti=1;i<=n;i++){scanf("%lld%lld",&a[i].u,&a[i].w);a[i].i=i;l=max(l,a[i].w);q.push(a[i]);mp[i]=0;}while(q.size()>=1&&q.top().w>=l){a[q.top().i].x=1;op+=q.top().u;w.push({q.top().w,q.top().i,q.top().zw});q.pop();}//cout<<op<<endl;for(inti=1;i<=m;i++){scanf("%lld%lld%lld",&o,&x,&y);if(o==1){//n++;a[n+i]=(one){x,y,n+i,0,i};q.push(a[n+i]);mp[n+i]=i;}else{a[x].w=y;a[x].zw=i;mp[x]=i;if(a[x].x==1){//cout<<"d"<<endl;l=min(l,a[x].w);w.push({a[x].w,a[x].i,a[x].zw});}else{q.push(a[x]);}}while(w.size()>=1&&w.top().zw!=mp[w.top().i]){w.pop();}while(q.size()>=1&&q.top().w>=w.top().w){if(q.top().zw==mp[q.top().i]){a[q.top().i].x=1;op+=q.top().u;w.push({q.top().w,q.top().i,q.top().zw});}q.pop();}cout<<op<<'\n';}return0;}