专栏文章

P12581 [UOI 2021] 敌人与军刀 题解

TTimSwn090306
P12581题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip7m710
此快照首次捕获于
2025/12/03 07:28
3 个月前
此快照最后确认于
2025/12/03 07:28
3 个月前
查看原文

Description

初始有 nn 把军刀和 mm 个敌人，军刀有属性 a,b,costa,b,cost，敌人有属性 c,d,profitc,d,profit。军刀 ii 能杀死敌人 jj 当且仅当 ai≥cj,bi≥dja_i\ge c_j ,b_i\ge d_j。你需要选出若干军刀和若干敌人，使得每一个选出的敌人都可以被至少一把选出的军刀杀死，并最大化选出的敌人的 profitprofit 之和减去选出的军刀的 costcost 之和。
数据范围：n,m≤106,a,b,c,d,cost,profit≤109n,m\le 10^6,a,b,c,d,cost,profit\le 10^9。

Solution

把军刀和敌人放到二维平面上，对于选定的若干军刀，有贡献的敌人呈阶梯状（如下图）。
将所有点按 yy 排序，设 fif_i 表示考虑前 ii 把军刀，钦定第 ii 把必选的最大收益（∑profit−∑cost\sum profit-\sum cost）。则有 fi=max⁡(fj+w(j,i))−costif_i=\max (f_j+w(j,i))-cost_i，其中 w(j,i)w(j,i) 表示上一把军刀为 jj，新增一把军刀为 ii 的 ∑profit\sum profit 增量。简单实现可以做到 O(n2)∼O(n3)O(n^2)\thicksim O(n^3)，无法通过此题，需要优化。
注意到计算 w(j,i)w(j,i) 时产生贡献的敌人的范围是一个 ([1,xi],[yj,yi])([1,x_i],[y_j,y_i]) 的矩形（如下图）。注意：若 xj<xix_j<x_i，转移本身是不优的，因为军刀之间存在偏序关系不优。同时 jj 到 ii 的转移的 w(j,i)w(j,i) 也不是上述矩形，计算出来是小于真实值的，但又因为这个转移本身是不优的，故不用考虑该情况。形式化的讲，wreal(j,i)≥w(j,i),fj+wreal(j,i)≤fi⟶fj+w(j,i)≤fiw_{real}(j,i)\ge w(j,i),f_j+w_{real}(j,i)\le f_i \longrightarrow f_j+w(j,i)\le f_i。
发现 w(j,i)w(j,i) 和 xjx_j 半毛钱关系没有，所以对于所有 yy 坐标相等的军刀，我只关心里面 ff 值最大的那一个，设 lil_i 表示 yy 坐标为 ii 的军刀里的 ff 最大值。
仍是从下到上枚举纵坐标 yy，设 pip_i 表示若新增军刀坐标为 (i,y)(i,y)，costcost 为 00，其 ff 值是多少，具体的，pi=max⁡j∈[1,y−1](lj+sum([1,i],[j,y]))p_i=\max_{j\in[1,y-1]}(l_j+sum([1,i],[j,y]))，其中 sum([sx,ex],[sy,ey])sum([sx,ex],[sy,ey]) 表示矩形内敌人的 profitprofit 之和。fi=pxi−costif_i=p_{x_i}-cost_i。
尝试维护 pp。不难发现新增第 ii 个敌人对 pp 的影响是 [xi,109][x_i,10^9] 区间加 profitiprofit_i，新增第 ii 个军刀对 pp 的影响是 [1,109][1,10^9] 全局对 fif_i 取 max⁡\max。区间加，全局取 max⁡\max，单点查，线段树容易维护。
时间复杂度 O(nlog⁡n)O(n\log n)。

Code

CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=2e6+5;
const ll INF=1e16;

int n,m,tot,b[maxn];
struct node{
	int type,x,y,c;
	inline bool operator < (node tmp) const{
		if (y!=tmp.y) return y<tmp.y;
		if (x!=tmp.x) return x<tmp.x;
		if (type!=tmp.type) return type<tmp.type;
		return c<tmp.c;
	}
}s[maxn];

namespace SGT{
	#define lc(rt) ((rt)<<1)
	#define rc(rt) ((rt)<<1|1)
	const int maxc=(maxn<<2);
	ll add[maxc],getmax[maxc];
	inline void lazy_add(int rt,ll k){
		add[rt]+=k;
	}
	inline void lazy_max(int rt,ll k){
		getmax[rt]=max(getmax[rt],k-add[rt]);
	}
	inline void pushdown(int rt){
		if (getmax[rt]){
			lazy_max(lc(rt),getmax[rt]);
			lazy_max(rc(rt),getmax[rt]);
			getmax[rt]=0;
		}
		if (add[rt]){
			lazy_add(lc(rt),add[rt]);
			lazy_add(rc(rt),add[rt]);
			add[rt]=0;
		}
	}
	inline void update_add(int rt,int l,int r,int ql,int qr,ll k){
		if (l>=ql && r<=qr){
			lazy_add(rt,k);
			return ;
		}
		pushdown(rt);
		int mid=(l+r)>>1;
		if (ql<=mid) update_add(lc(rt),l,mid,ql,qr,k);
		if (qr>mid) update_add(rc(rt),mid+1,r,ql,qr,k);
	}
	inline void update_max(int rt,int l,int r,int ql,int qr,ll k){
		if (l>=ql && r<=qr){
			lazy_max(rt,k);
			return ;
		}
		pushdown(rt);
		int mid=(l+r)>>1;
		if (ql<=mid) update_max(lc(rt),l,mid,ql,qr,k);
		if (qr>mid) update_max(rc(rt),mid+1,r,ql,qr,k);
	}
	inline ll query(int rt,int l,int r,int p){
		if (l==r){
			return max(0ll,getmax[rt])+add[rt];
		}
		pushdown(rt);
		int mid=(l+r)>>1;
		if (p<=mid) return query(lc(rt),l,mid,p);
		else return query(rc(rt),mid+1,r,p);
	}
}

ll f[maxn];

inline int rd(){
	int x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch-'0');
		ch=getchar();
	}
	return x;
} 

int main(){
	n=rd(),m=rd();
	for (int i=1;i<=n;i++) s[i].x=rd(),s[i].y=rd(),s[i].c=rd(),s[i].type=-1;
	for (int i=1;i<=m;i++) s[i+n].x=rd(),s[i+n].y=rd(),s[i+n].c=rd(),s[i+n].type=+1;
	
	for (int i=1;i<=n+m;i++) b[++tot]=s[i].x;
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-b-1;
	for (int i=1;i<=n+m;i++) s[i].x=lower_bound(b+1,b+tot+1,s[i].x)-b;
	
	sort(s+1,s+n+m+1);
	memset(SGT::getmax,-0x3f,sizeof(SGT::getmax));
	
	for (int i=1;i<=n+m;i++){
		int j=i;
		while (j<=n+m && s[j].y==s[i].y) j++;
		for (int k=i;k<j;k++){
			if (s[k].type==+1){
				SGT::update_add(1,1,tot,s[k].x,tot,s[k].c);
			}
		}
		ll maxx=-INF;
		for (int k=i;k<j;k++){
			if (s[k].type==-1){
				f[k]=SGT::query(1,1,tot,s[k].x)-s[k].c;
				maxx=max(maxx,f[k]);
			}
		}
		SGT::update_max(1,1,tot,1,tot,maxx);
		
		i=j-1;
	}
	
	ll ans=-INF;
	for (int i=1;i<=n+m;i++) ans=max(ans,f[i]);
	
	printf("%lld\n",ans);
	
	return 0;
}

评论

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

正在加载评论...