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

· · 题解

题目。

思路

二分、前缀和。

对于每一次询问，我们可以先求出正常情况下从 L 到 R 中所有商品的价值，然后减去在区间内第 D 天商品的折扣价。

前一部分很显然可以通过前缀和完成。

然后，我们开一个 vector 数组 t，其中 t_i 存放第 i 天的所有商品的价值与下标。

每一次询问中，我们对于 t_d 二分查找，分别找到第一个下标大于 L 的和最后一个下标小于 R 的商品。将这个区间内的商品价值相加，再除以 2，就可以得到这一天在区间内的商品的折扣价。这个相加的过程同样可以前缀和优化。

代码

//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;
}