专栏文章

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

lliu鲤鱼
P14293题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minih9pz
此快照首次捕获于
2025/12/02 02:57
3 个月前
此快照最后确认于
2025/12/02 02:57
3 个月前
查看原文
题目。

思路

二分、前缀和。
对于每一次询问，我们可以先求出正常情况下从 LL 到 RR 中所有商品的价值，然后减去在区间内第 DD 天商品的折扣价。
前一部分很显然可以通过前缀和完成。
然后，我们开一个 vector 数组 tt，其中 tit_i 存放第 ii 天的所有商品的价值与下标。
每一次询问中，我们对于 tdt_d 二分查找，分别找到第一个下标大于 LL 的和最后一个下标小于 RR 的商品。将这个区间内的商品价值相加，再除以 22，就可以得到这一天在区间内的商品的折扣价。这个相加的过程同样可以前缀和优化。

代码

CPP
//846ms / 18.12MB / 950B C++17 O2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,q,p[200010],d,l,r,ans;
struct node{
	ll v,id;
};
vector<node> t[200010];
ll erfen(const vector<node>&y){//求折扣价
	ll len=y.size();
	if(len<=1) return 0;//如果这一天没有商品，就没有折扣
	ll left=len,nl=1,nr=len-1,mid=0,right=0;
	while(nl<=nr){//二分左端点
	    mid=(nl+nr)/2;
	    if(y[mid].id>=l)
	        left=mid,nr=mid-1;
	    else nl=mid+1;
	}nl=1,nr=len-1;
	while(nl<=nr){//二分右端点
	    mid=(nl+nr)/2;
	    if(y[mid].id<=r)
	        right=mid,nl=mid+1;
	    else nr=mid-1;
	}if(left>right) return 0;//不存在
	return (y[right].v-y[left-1].v)/2;//别忘了价格减半
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&q);
	for(ll i=1;i<=m;i++) t[i].push_back({0,0});
	for(ll i=1;i<=n;i++){
		ll pp,a;
		scanf("%lld%lld",&pp,&a);
		t[a].push_back({pp,i});
		p[i]=p[i-1]+pp;//计算前缀和
	}for(ll i=1;i<=m;i++){
		for(ll j=2;j<t[i].size();j++)
			t[i][j].v+=t[i][j-1].v;//依旧前缀和
	}while(q--){
		scanf("%lld%lld%lld",&d,&l,&r);
		ans=p[r]-p[l-1];
		printf("%lld\n",ans-erfen(t[d]));
	}return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...