本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}

自认为码风良好。