拒绝原因特定的、约定俗成的函数名称应该使用正体，如

\gcd, \max, \min, \log, \det

（ $\gcd, \max, \min, \log, \det$ ）。特别地，对于一些未定义的函数，应使用 \operatorname，如

\operatorname{lcm}

（\operatorname{lcm}）；【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格。

~~写这道题时LyhLxWq123456789大佬的神奇思路，于是有了这篇题解~~

P14962 一次买够题解

题目大意

#给定

n

个商品，每个商品有价格

v

和性价比

w

两个属性，初始时需要购买所有性价比最高的商品；之后有

m

次操作操作分为两种类型：

1．新增商品：输入新商品的价格

x

和性价比

y

，添加该商品到商品列表；　　　　　　　　　　　

2．修改商品：输入商品编号 x和新性价比

y

，将编号为

x

的商品性价比修改为

y

。

每次操作后，需要遵循以下规则更新已购买商品：记当前已购买商品的最小性价比为

L

；购买所有未购买且性价比

\le L

的商品；输出每次操作后的总花费。

数据范围：

n,m≤2×10^5

，要求算法时间复杂度为

O((n+m)logn)

，否则会超时或部分得分。

二、解题思路

核心思想

动态维护已购买或未购买商品，利用集合的自动排序特性，高效完成 “查找最小性价比”“筛选符合条件商品” 等核心操作，避免暴力遍历导致的超时。

具体步骤

遍历所有初始商品，找到最大性价比 max_w（初始时 L=max_w）；将所有性价比等于 max_w 的商品标记为 “已购买”，累加价格到总花费，并将其性价比存入 multiset（维护已购商品的性价比）；其余商品存入 set（按性价比降序排列，维护未购买商品）。

新增商品：若新商品性价比

\le1

当前

L

，直接标记为已购买并更新总花费；否则加入未购买集合，最后执行 “批量购买逻辑”。

修改商品：若商品已购买：从 multiset 中删除原性价比，插入新性价比，更新

L

为 multiset 的最小值；若商品未购买：从未购买集合中删除旧商品信息，插入修改后的新信息；

三、注意事项

1. 避免运行时错误（RE）

迭代器失效问题：set.erase(it) 后，原迭代器 it 会失效，需重新调用 set.begin() 获取新迭代器，否则访问失效迭代器会导致崩溃；空容器访问：访问 multiset.begin() 前需判断容器非空，否则会触发空指针错误；数组越界：商品编号需覆盖 “初始 $n$ 个 $+$ 新增 $m$ 个”，数组大小至少设为 $4×10^5$ （而 $2×10^5$ ）；
精准删除元素：未购买集合存储的商品需包含唯一 ID（仅存价格 $+$ 性价比会导致 find/erase 匹配失败），结构体需重载 $<$ 运算符（按性价比降序、ID 升序排序）。

亲身经历

2. 避免部分得分（50 分）

购买逻辑触发不全：新增商品、修改商品后必须统一执行批量购买逻辑（原代码仅修改已购商品时执行，导致新增商品后漏买）；
最小性价比更新滞后：每次执行购买逻辑前，需重新获取 multiset 的最小值作为新的 $L$ ，避免使用旧值导致筛选错误；重复购买问题：通过布尔数组标记商品是否已购买，购买前判断标记，避免同一商品被多次累加价格。

亲身经历

3. 效率优化输入输出：

数据量较大时，优先使用 scanf/printf 而非 cin/cout（或关闭 cin 同步），避免超时；函数封装：将批量购买逻辑封装为独立函数，减少代码冗余，避免漏写核心逻辑；减少冗余操作：erase 元素前先调用 find 确认元素存在，避免删除不存在的元素导致性能损耗或错误。

4. 关键细节

结构体排序规则：按性价比降序、ID 升序，确保 set 中商品排序唯一且符合 “优先购买高性价比” 的逻辑； multiset 删值注意：使用 erase(find(val)) 而非直接 erase(val)（后者会删除所有等于 val 的元素，而非单个）。

code(

O((n+m)logn)

)

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAIN signed main()
const int N=2e5;
struct G
{
   int v,w,i;
   bool operator<(const G&B)const
   {
       if(w!=B.w)return w>B.w;
       else return i<B.i;
   }
} g[4*N];

bool p[4*N];//标记是否购买
int n,m;
multiset<int> s;
multiset<int>::iterator it_s;
int L=-INT_MAX;//已购商品最小性价比
int a;
set<G> q;
set<G>::iterator it_q;
// 统一购买逻辑函数
void b()
{
   if(s.empty())return;
   L=*s.begin();
   while(!q.empty())
   {
       it_q=q.begin();
       if((*it_q).w>=L)
       {
           G t=(*it_q);
           q.erase(it_q);
           if(p[t.i])continue;
           p[t.i]=true;
           a+=t.v;
           s.insert(t.w);
       }
       else break;
   }
}
MAIN{
   scanf("%lld%lld",&n,&m);
   for(int i=1;i<=n;i++)
   {
       int x,y;
       scanf("%lld%lld",&x,&y);
       g[i]={x,y,i};
       L=max(L,y);
   }
   // 初始化购买最高性价比商品
   for(int i=1;i<=n;i++)
   {
       if(g[i].w==L)
       {
           p[i]=true;
           a+=g[i].v;
           s.insert(g[i].w);
       }
       else q.insert(g[i]);
   }

   for(int k=1;k<=m;k++)
   {
       int o,x,y;
       scanf("%lld%lld%lld",&o,&x,&y);
       if(o==1)
       {
           // 新增商品
           int j=k+n;
           g[j]={x,y,j};
           if(y>=L){
               p[j]=true;
               a+=g[j].v;
               s.insert(g[j].w);
           }
           else q.insert(g[j]);
           b();// 执行购买逻辑
       }
       else
       {
           // 修改商品
           if(p[x])
           {
               it_s=s.find(g[x].w);
               if(it_s!=s.end())s.erase(it_s);
               s.insert(y);
               g[x].w=y;
           }
           else
           {
               it_q=q.find(g[x]);
               if(it_q!=q.end())q.erase(it_q);
               g[x].w=y;
               if(y>=L)
               {
                   p[x]=true;
                   a+=g[x].v;
                   s.insert(y);
               }else q.insert(g[x]);
           }
           b();// 执行购买逻辑
       }
       printf("%lld\n",a);
   }
   return 0;
}

问哪里有问题

讨论操作