题解：P14293 [JOI2024 预选赛 R2] 购物 2 / Shopping 2

No_coding_extra · 2025-10-22 21:06:58 · 题解

题目大意：

传送门

JOI 商店有 N 件商品，每件商品有价格和种类。促销活动持续 M 天，第 j 天所有种类为j的商品打 5 折。有 Q 位顾客，每位顾客在第 T_k 天购买编号在 [L_k, R_k] 范围内的所有商品。需要计算每位顾客的总花费。

题目思路：

显然要用前缀和，不会戳这里，应该都会。

很显然，答案就是：

• 区间内所有商品原价总和 - 第 t_k 天区间内种类为 t_k 的商品的原价一半。

前半部分就可以用前缀和 f 在 O(1) 快速求出，那就会有人问了，后面呢怎么算呢？

其实也是前缀和思想，我们定义：

利用前缀和思想，可以预处理出第 j 类商品在任意子区间的半价总和，显然公式为：

• s[i][j+1]=s[i][j] + p[it[i][j]] \div 2

注：p[i] 为商品 i 的定价。

后面统计时候，使用二分找到找到第一个可以享受折扣的商品 l 和找到最后一个可以享受折扣的商品 r，右半部分答案就为 s[t_k][r+1]-s[t_k][l]，整题答案就是 f[r_k]-f[l_k-1]-(s[t_k][r+1]-s[t_k][l])，这题就写完了。

注：f[i] 为商品 i 的定价 p_i 的前缀和。

思路讲得很清楚，代码就不放了。