专栏文章

题解：P11673 [USACO25JAN] Median Heap G

GGordon_Song
P11673题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqccyn4
此快照首次捕获于
2025/12/04 02:29
3 个月前
此快照最后确认于
2025/12/04 02:29
3 个月前
查看原文
dp 题。
首先先把 aa 和 mm 离散化，变成 [1,n+q][1,n+q] 之间的数。
现在来分析这一“近似中位数”的特性：不妨设当前节点为 xx，pip_i 表示 ii 的子树操作完后，ii 这个节点上的值是多少。那么 px=yp_x = y 的充要条件是 ax′a'_x（替换操作进行完之后的 axa_x 值，与原来的 axa_x　做区分），p2xp_{2x}，p2x+1p_{2x+1} 中，恰好有一个小于等于 yy，一个等于 yy，一个大于等于 yy。
此时，就能自然而然地设出一个 dp 的状态：设 dpi,jdp_{i,j} 表示希望令 pi=jp_i = j，至少需要在子树内支付多少代价。但是我们发现直接这样设好像无法转移，还需要两个辅助数组： dp1i,jdp1_{i,j} 表示希望令 pi≤jp_i \leq j　的最小代价，dp2i,jdp2_{i,j} 表示希望令 j≤pij \leq p_i 的最小代价。转移方程比较繁琐，但不难推导（具体见文末的代码的 push_down 函数 ）。
就这样，我们有了一个 O(n2)O(n^2) 的做法。但是这样只能拿到 77 个测试点的分数，显然不够。
然而，如果考虑 jj 的值从 yy 变成 y+1y+1，会发现实际上 dpdp 值变化的点很少。对于所有 x∣ax=y−1x | a_x = y-1 以及 x∣ax=yx| a_x = y 的 xx，只有 xx 以及他到根的节点的值可能会变！由于这些数加起来一共只有 O(n)O(n) 个，所以在 jj 从 11 一直移动到 n+qn+q 的过程中总共只需要改变 nlog⁡nn \log n 个位置的 dpdp 值。
所以我们可以添加一个优化，只在 dpx,jdp_{x,j} 中更改 ax=ja_x = j 或 ax=j+1a_x = j+1 的 xx 到根的路径上的节点的 dpdp 值，从而得到 dpx,j+1dp_{x,j+1}，经过优化后的复杂度为 O((n+q)log⁡n)O((n+q) \log n)。不明白为什么开 4 秒……
CPP
int n,q;
const int MAXN=2e6+5;
int a[MAXN],c[MAXN];
int p[MAXN],l,now;
int d[MAXN]; 
vector<int>que[MAXN],poi[MAXN];
ll tox[MAXN],toe[MAXN],tod[MAXN];//tox：文中的 dp1，toe：文中的 dp，tod：文中的 dp2
void push_up(int x){//转移方程
	tox[x]=min({tox[x<<1]+(a[x]>now)*c[x],tox[x<<1|1]+(a[x]>now)*c[x],tox[x<<1]+tox[x<<1|1]});
	tod[x]=min({tod[x<<1]+(a[x]<now)*c[x],tod[x<<1|1]+(a[x]<now)*c[x],tod[x<<1]+tod[x<<1|1]});
	toe[x]=min({min(tox[x<<1]+tod[x<<1|1],tod[x<<1]+tox[x<<1|1])+(a[x]!=now)*c[x],
	toe[x<<1]+min((a[x]>now)*c[x]+tod[x<<1|1],(a[x]<now)*c[x]+tox[x<<1|1]),
	toe[x<<1|1]+min((a[x]>now)*c[x]+tod[x<<1],(a[x]<now)*c[x]+tox[x<<1])});
}
ll ans[MAXN];
void dfs(int x){
	if(x>n){
		toe[x]=1e18;
		return ;
	}
	if((x<<1)>n){
		toe[x]=(a[x]!=now)*c[x];
		tod[x]=(a[x]<now)*c[x];
		tox[x]=(a[x]>now)*c[x];
	}else{
			
		dfs(x<<1);dfs(x<<1|1);
		push_up(x);
	}
//	printf("%d  %d %d %lld %lld %lld\n",x,a[x],c[x],tod[x],tox[x],toe[x]);
}
void pus(int x){
	if(!x)return ;
	if(x*2>n){
		toe[x]=(a[x]!=now)*c[x];
		tod[x]=(a[x]<now)*c[x];
		tox[x]=(a[x]>now)*c[x];
		
	}else{
		push_up(x);
	}
	
	pus(x>>1);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&c[i]);
		p[++l]=a[i];
	}scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d",&d[i]);p[++l]=d[i];
	}

  //离散化
	sort(p+1,p+1+l);
	l=unique(p+1,p+1+l)-p-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(p+1,p+1+l,a[i])-p;
		poi[a[i]].push_back(i);
	}
	for(int i=1;i<=q;i++){
		d[i]=lower_bound(p+1,p+1+l,d[i])-p;
		que[d[i]].push_back(i);
	}


	dfs(1);
//	now=4;
//	dfs(1);
	
	for(int i=1;i<=l;i++){
		now=i;
//		dfs(1);
		
		for(int j=0;j<poi[i-1].size();j++){
			pus(poi[i-1][j]);
		}
		for(int j=0;j<poi[i].size();j++){
			pus(poi[i][j]);
		}
		for(int j=0;j<que[i].size();j++){
			ans[que[i][j]]=toe[1];
		}
	//	printf("now=%d:\n",i);
	//	for(int j=1;j<=n;j++){
	//		printf("%d %d %d %lld %lld %lld\n",j,a[j],c[j],tox[j],toe[j],tod[j]);
	//	}
	}
	for(int i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
}

评论

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

正在加载评论...