题解：P11268 【MX-S5-T2】买东西题

zibenlun · 2024-11-10 17:13:57 · 题解

来一篇线段树题解吧

首先考虑简化问题，看到每一个物品的原本折扣，很显然可以把它当作每一个物品本来就有一个优惠券，所以问题就变成了给所有物品更新优惠券。

思考怎么更新优惠券，显然可以想到，对于每一个优惠券，如果它更新的物品原本的优惠越少，那么这张优惠券的贡献就越大。所以就可以每一次找出能更新的里面原本优惠最小的即可。更新的时候按照 w 从大到小开始。实现这个操作可以通过把物品按照 a 排序，这样每一次查询的范围就是一段后缀。只需要查后缀最小值再修改就可以了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct nd{int a,b,c;}a[N];
struct {int l,r,minn;}c[N<<2];
int n,m,k[N],ans;
struct node{int w,v;}t[N];
bool cmpp(node x,node y){return x.w>y.w;}
bool cmp(nd x,nd y){return x.a<y.a;}
void pushup(int pos){
    if(a[c[pos<<1].minn].c<a[c[pos<<1|1].minn].c)c[pos].minn=c[pos<<1].minn;
    else c[pos].minn=c[pos<<1|1].minn;
}
void build(int pos,int l,int r){
    c[pos].l=l,c[pos].r=r;
    if(l==r){
        c[pos].minn=l;
        return ;
    }
    build(pos<<1,l,(l+r)/2);
    build(pos<<1|1,(l+r)/2+1,r);
    pushup(pos);
}
void change(int pos,int x,int v){
    if(c[pos].l>x||c[pos].r<x) return ;
    if(c[pos].l==x&&c[pos].r==x){
        a[x].c=v;
        return ;
    }
    change(pos<<1,x,v);
    change(pos<<1|1,x,v);
    pushup(pos);
}
int ask(int pos,int l,int r){
    if(c[pos].l>r||c[pos].r<l) return 0;
    if(c[pos].l>=l&&c[pos].r<=r)return c[pos].minn;
    int x=ask(pos<<1,l,r),y=ask(pos<<1|1,l,r);
    if(a[x].c<a[y].c) return x;
    else return y;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
        a[i].c=a[i].a-a[i].b;
    }
    for(int i=1;i<=m;i++) cin>>t[i].w>>t[i].v;
    a[0].c=1e18;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) k[i]=a[i].a;
    sort(t+1,t+1+m,cmpp);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int x=ask(1,lower_bound(k+1,k+1+n,t[i].w)-k,n);
        if(a[x].c<t[i].v) change(1,x,t[i].v);
    }
    for(int i=1;i<=n;i++)ans+=a[i].a-a[i].c;cout<<ans;
    return 0;
}

自认为码风良好。