CWOI S C0223 D 推销员

题意使用 openssl enc -aes256 -pbkdf2 加密。

U2FsdGVkX18ZAhe47nmNdUGMrS9vdkWsIWDnqGghbED7VEhlPEZZ351pr4QBrER6
2MdmpB3WFjcYo2XuyGuXu4vbhDOSHJN7qwolNHfgoBGk+Yg59yHnFPdJBy+J41Va
2u2SF/FzdbRZ99FKftUqvqvHL5IbBNO1IelXxoQpxmpB9TS9qRMzXrGdCNilWmcS
PZoJzbmdaP96zZSMkOKh8IK1Ny9btUxgHZLTKHKPNDB2nGr1xJaABNX/47pE+GiM
XcFt2o6tTN/RY48DvNyERIPCcU7owVYDrjgUXuk9lQFZhj90V9joIfN/wGkmWgsO

解析

假设对于 $i$，取到最小值的 $k$ 是 $p_i$，容易证得对于任意一个 $i \le j$，$p_i \le p_j$。故我们可以分治解决。

前缀前 $i$ 小的和可以用可持久化线段树做。

[robinyqc: 拉平的分治算法](https://robinyqc.cn/blogs/blogrepo/%E6%8B%89%E5%B9% B3%E7%9A%84%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95) 中，提到了一种通过更改分治顺序避免使用可持久化线段树的做法。

#include <algorithm>
#include <cstdio>
#include <limits>
#include <vector>

struct node_t
{
	int cnt, sum;
	node_t() : cnt(0), sum(0) {}
	node_t(int val) : cnt(1), sum(val) {}

	node_t &operator+=(const node_t &n)
	{
		cnt += n.cnt;
		sum += n.sum;
		return *this;
	}
};

struct segtree
{
	node_t val;
	segtree *lc, *rc;

	static segtree *empty_node;

	segtree() : val(), lc(nullptr), rc(nullptr) {}

	segtree *add(int p, const node_t &v, int ll, int rr) const
	{
		segtree *res = new segtree(*this);
		if (rr - ll == 1) {
			res->val += v;
			return res;
		}
		int mid = ll + (rr - ll) / 2;
		if (p < mid) {
			if (res->lc == nullptr) res->lc = empty_node;
			res->lc = res->lc->add(p, v, ll, mid);
		} else {
			if (res->rc == nullptr) res->rc = empty_node;
			res->rc = res->rc->add(p, v, mid, rr);
		}
		res->val = node_t();
		if (res->lc != nullptr) res->val += res->lc->val;
		if (res->rc != nullptr) res->val += res->rc->val;
		return res;
	}

	int kth(int k, int ll, int rr) const
	{
		if (rr - ll == 1) return ll;
		int mid = ll + (rr - ll) / 2;
		int lcnt = 0;
		if (lc != nullptr) lcnt = lc->val.cnt;
		if (lc != nullptr && k <= lcnt) return lc->kth(k, ll, mid);
		else if (rc != nullptr) return rc->kth(k - lcnt, mid, rr);
		return -1;
	}

	node_t prod(int l, int r, int ll, int rr) const
	{
		if (l <= ll && rr <= r) {
			return val;
		}
		int mid = (ll + rr) / 2;
		node_t res;
		if (l < mid && lc != nullptr) res += lc->prod(l, r, ll, mid);
		if (mid < r && rc != nullptr) res += rc->prod(l, r, mid, rr);
		return res;
	}

};

segtree *segtree::empty_node = new segtree();

int main()
{
	int n;
	scanf("%d", &n);
	std::vector<int> s(n);
	std::vector<int> a(n);
	for (auto &i : s) scanf("%d", &i);
	for (auto &i : a) scanf("%d", &i);

	const int MAXA = *std::max_element(a.begin(), a.end());

	std::vector<segtree *> trees;
	trees.emplace_back(segtree::empty_node);
	for (int i = 0; i < n; i++) {
		trees.emplace_back(trees.back()->add(a[i], node_t(a[i]), 
						     0, 
						     MAXA + 1));
	}

	std::vector<int> f(n + 1, std::numeric_limits<int>::max());
	auto solve = [&s, &trees, MAXA](auto &&self,
					int l, 
					int r,
					int pl,
					int pr,
					std::vector<int> &f) -> void
	{
		if (r <= l) return;
		int mid = l + (r - l) / 2;
		int min_pos = pl;
		for (int i = std::max(mid, pl); i <= pr; i++) {
			int k = trees[i]->kth(mid, 0, MAXA + 1);
			auto val = trees[i]->prod(0, k, 0, MAXA + 1);
			int res = val.sum + (mid - val.cnt) * k + s[i - 1] * 2;
			// printf("%d: %d -> %d, k = %d, (%d, %d)\n", mid, i, res, k, val.cnt, val.sum);
			if (res < f[mid]) {
				f[mid] = res;
				min_pos = i;
			}
		}
		self(self, l, mid, pl, min_pos, f);
		self(self, mid + 1, r, min_pos, pr, f);
	};

	solve(solve, 1, n + 1, 0, n, f);
	for (int i = 1; i <= n; i++) {
		printf("%d\n", f[i]);
	}
}