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

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+20;
int n,m,q;
struct node{
    int id,sum;
};
int x,y;
int day,l,r;
vector<node> v[N];
int sum[N];
int check(int d,int L,int R){
    int l=0,r=v[d].size()-1,res=-1,res1=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(v[d][mid].id<L) l=mid+1; 
        else r=mid-1,res=mid;
    }  //找出这段区间内种类为 d 的编号最大的
    l=0,r=v[d].size()-1;
    while(l<=r){
        int mid=l+r>>1;
        if(v[d][mid].id<=R) res1=mid,l=mid+1;
        else r=mid-1;
    } //找出这段区间内种类为 d 的编号最小的
    if(res1==-1) return 0;
    if(v[d][res1].id<L) return 0;
    if(res<=0) return v[d][res1].sum;
    else return v[d][res1].sum-v[d][res-1].sum; //前缀和
}
int k;
signed main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>y>>x;
        sum[i]=sum[i-1]+y,k=v[x].size()-1;
        if(k<0) k=y;
        else k=v[x][k].sum+y;
        v[x].push_back((node){i,k}); //这里维护每个种类的前缀和
    }
    for(int i=1;i<=q;i++){
        cin>>day>>l>>r;
        int ans=sum[r]-sum[l-1]-check(day,l,r)/2;
        cout<<ans<<"\n";
    }
}