专栏文章

P11678 [USACO25JAN] Watering the Plants P

rrlc202204
P11678题解参与者 1已保存评论 0

文章操作

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

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

P11678 [USACO25JAN] Watering the Plants P

题意：
有 nn 个植物和 n−1n-1 个水管，第 ii 个水管可以给 i,i+1i,i+1 两个植物一起提供任意单位的水，每单位水的花费是 cic_i。第 ii 个植物至少需要 wiw_i 单位的水。
对于每个 1≤i<n1 \le i < n 求只考虑前 ii 个水管，满足前 i+1i+1 个植物的最小花费。
n≤5×105,ci,wi≤106n \le 5 \times 10^5,c_i,w_i \le 10^6。
思路：
注意到这个问题很想网络流，但是至少 wiw_i 单位的水不太好做，考虑对偶一下：
原来的限制为：
1≤i<n,xi+xi+1≥wiminimize∑i=1n−1cixi1 \le i < n,x_i + x_{i+1} \ge w_i\\ \text{minimize} \sum_{i=1}^{n-1}c_ix_i
对偶之后变成：
1≤i<n,yi+yi+1≤cimaximize∑i=1nwiyi1 \le i < n, y_i + y_{i+1} \le c_i\\ \text{maximize}\sum_{i=1}^n w_iy_i
这样我们就可以考虑费用流模型，和种树那题很想，大致如下：
但是显然数据范围不支持我们真的去跑费用流。所以我们只能贪心或者 dp 凸优化。这里我们考虑 dp 凸优化。
设 fi(j)f_i(j) 表示前 ii 个，满足 yi=jy_i = j 的最大的 ∑wiyi\sum w_iy_i。我们发现随着 jj 的增大 fi(j)f_i(j) 是凸函数。
这相当于不断给最后一条边加 11 的流量，由于是费用流，所以增广路不会增大，所以是凸的。
转移如下：
fi(j)=j×wi+max⁡k≤ci−jfi−1(k)f_i(j) = j \times w_i + \max_{k \le c_i - j}f_{i-1}(k)
假设我们维护了 fi−1f_{i-1} 的凸函数，那么这相当于以下三件事：
  • 将凸函数范围改成 [0,ci][0,c_i]。
  • 反转凸函数。
  • 整体取前缀 max⁡\max。
  • 加上直线 y=wixy=w_ix。
我们可以用 FHQ_Treap 来维护，一个节点储存差分相等的区间的长度，同时还要储存差分是多少，以及差分乘上区间长度的值。
我们要支持全局加法，全局反转，打两个 tag 就行。
当然这里其实可以用官方解法那样用双端队列就行，考场上没想那么多。时间复杂度 O(nlog⁡n)O(n \log n)，可以通过。
CPP
#include <iostream>
#include <cstdio>
#include <queue>
#include <ctime>
#include <random>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
const int A = 1e6 + 5;
typedef long long ll;
#define debug(x) cout << #x << "=" << x << endl 

int n;
int w[N] = {0}, c[N] = {0};

struct LazyTag {
	int rev;
	ll add;//翻转后加上 add
	LazyTag (int _rev = 0, ll _add = 0ll) :
		rev(_rev), add(_add) {}
};
LazyTag operator+(LazyTag x, LazyTag y) {
	return LazyTag((x.rev ^ y.rev), y.add + (y.rev ? -x.add : x.add));
}
struct Node {
	int ch[2], pri, sz;
	ll d, p;
	ll sd, sp, sum;//d之和, p 之和, p * d之和 
	LazyTag tag;  
	Node () {
		ch[0] = ch[1] = sz = 0, pri = -1;
		d = p = sd = sp = sum = 0ll;
		tag = LazyTag();
	}
	Node (ll _d, ll _p) {
		sd = d = _d, sp = p = _p, sum = p * d;
		ch[0] = ch[1] = 0, sz = 1, pri = rand();
		tag = LazyTag();
	}
} a[N];

#define ls(x) a[x].ch[0]
#define rs(x) a[x].ch[1]

void upd(Node &x, Node &y, Node &z) {
	x.sd = y.sd + z.sd + x.d;
	x.sp = y.sp + z.sp + x.p;
	x.sum = y.sum + z.sum + x.d * x.p;
	x.sz = y.sz + z.sz + 1;
}
void pushup(int x) {
	upd(a[x], a[ls(x)], a[rs(x)]);
}
void mdf(Node &x, LazyTag v) {
	if (v.rev) {
		x.d = -x.d;
		x.sd = -x.sd;
		x.sum = -x.sum;
		swap(x.ch[0], x.ch[1]);
	}
	x.d += v.add;
	x.sd += v.add * x.sz;
	x.sum += v.add * x.sp;
	x.tag = x.tag + v;
}
void pushtag(int x, LazyTag v) {
	mdf(a[x], v);
}
void pushdown(int x) {
	pushtag(ls(x), a[x].tag);
	pushtag(rs(x), a[x].tag);
	a[x].tag = LazyTag();
}
void spt_sp(int x, ll v, int &L, int &R) {
	if (x == 0) {
		L = R = 0;
		return;
	}
	pushdown(x);
	if (a[ls(x)].sp + a[x].p <= v)
		L = x, spt_sp(rs(x), v - a[ls(x)].sp - a[x].p, rs(x), R);
	else
		R = x, spt_sp(ls(x), v, L, ls(x));
	pushup(x);
}
void spt_d(int x, ll v, int &L, int &R) {
	if (x == 0) {
		L = R = 0;
		return;
	}
	pushdown(x);
	if (a[x].d > v)
		L = x, spt_d(rs(x), v, rs(x), R);
	else
		R = x, spt_d(ls(x), v, L, ls(x));
	pushup(x); 
}
void spt_sz(int x, int k, int &L, int &R) {
	if (x == 0) {
		L = R = 0;
		return;
	}
	pushdown(x);
	if (a[ls(x)].sz + 1 <= k)
		L = x, spt_sz(rs(x), k - a[ls(x)].sz - 1, rs(x), R);
	else	
		R = x, spt_sz(ls(x), k, L, ls(x));
	pushup(x); 
}
int mrg(int L, int R) {
	if (L == 0 || R == 0)	
		return L + R;
	if (a[L].pri > a[R].pri) {
		pushdown(L);
		rs(L) = mrg(rs(L), R);
		pushup(L);
		return L; 
	}
	else {
		pushdown(R);
		ls(R) = mrg(L, ls(R));
		pushup(R);
		return R;
	}
}

int rt;//当前的根
ll res;//初始截距
int tot = 0;//节点个数 

void show(int x) {
	if (x == 0)
		return;
	pushdown(x);
	show(ls(x));
	printf("(%lld, %lld) ", a[x].p, a[x].d);
	show(rs(x));
}

void upd_lim(ll k) {//只保留 <= k 的部分 
	int L, M, R;
	spt_sp(rt, k, L, R);
//	debug(k);
//	show(L);cout << endl; show(R);cout << endl;
	if (!R) {//表示当前不够了 
//	cout << a[L].sp << endl;
		a[++tot] = Node(0ll, k - a[L].sp);
		rt = mrg(L, tot);
//		show(rt);cout << endl;
		return;
	}
	spt_sz(R, 1, M, R);
	a[M] = Node(a[M].d, k - a[L].sp);
	rt = mrg(L, M);
} 
void upd_rev(ll v) {//整体翻转然后所有数加上 v 
	res += a[rt].sum;//截距变化 
//	show(rt);cout << endl;
//	debug(rt);
	pushtag(rt, LazyTag(1, v));
//	debug(v);
//	show(rt);cout << endl;
}
void upd_min() {//取前缀 max，只保留 d > 0 的所有部分
	int L, R;
//	show(rt);cout << endl;
	spt_d(rt, 0ll, L, R);
	rt = L; 
}


#undef ls
#undef rs 

int main() {
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	for (int i = 1; i < n; i++)
		scanf("%d", &c[i]);
	res = 0ll;
	rt = ++tot;
	a[rt] = Node(w[1], 1000000ll);
	for (int i = 2; i <= n; i++) {
//		if (i == 9)
//			cout << "\n\n\n\n";
		upd_lim(c[i - 1]);
		upd_rev(w[i]);
		upd_min();
	//	show(rt);
	//	printf("res: %lld\n", res);
		printf("%lld\n", res + a[rt].sum);
	//	cout << "nxt \n\n" << endl;
	//	if (i == 9)
	//		break;
	}
	return 0;
}

评论

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

正在加载评论...