出题人题解 | #小y的纸牌#

原题解链接：https://ac.nowcoder.com/discuss/181037

题目大意：

给出一个序列，分成两个子序列(长度可以不相同，位置可以不连续)，使得两个序列各个位置的前缀最大值的和最小。

一道非常巧妙的dp + 非常套路的分块题

首先考虑$O(n^2)O(n^2)$的$dpdp$怎么做

可以发现两个性质： 设原数组为$SS$ 性质$11$：假设分成的两个序列为$a,ba,b$。若其中某个位置时，$aa$中的最大值比$bb$小，那么以后肯定一直都是$aa$中的最大值比$bb$小。因为要使$aa$中的最大值比$bb$大，那么只能是有一个$s>m{x}_{b}s\; >\; mx\_b$ ​ 且$ss$被分到了$aa$数组中。显然，$ss$分到$bb$数组中会更优秀

性质$22$:假设$aa$数组中的最大值一直比$bb$小，那么所有分到$bb$数组中的数字的贡献是原序列中该数字前面所有数字的最大值。因为$bb$中的最大值一直比$aa$大，所以这个很显然。

根据上面的两个性质，我们就可以设出状态。设$f_{i}f\_i$ ​ 表示第$ii$个数字分到了$aa$数组且作为$aa$数组中的最大值最终的贡献。

那么对于原序列$SS$中第$ii$个元素我们可以分成以下两种情况，

1.将该元素放到$bb$数组中。

显然，只有当$S_{i}S\_i$ ​ 比$aa$数组中的最大值大时，我们才可能会选择这种情况。所以我们对于每个$S_i>S_{j}S\_i>S\_j$ ​ 将$f_j+=max\{S_1,S_2,\mathrm{.}\mathrm{.}\mathrm{.}{S}_i\}f\_j+=max\backslash \{S\_1,S\_2,...S\_i\backslash \}$

2.将$S_{i}S\_i$ ​ 放到$aa$数组中。

如果$S_{i}S\_i$ ​ 放到$aa$数组中且a数组中的最大值不变，即 ​ ,那么将$f_j+=S[j]f\_j+=S[j]$即可

如果$S_{i}S\_i$ ​ 放到$aa$数组中$aa$数组中的最大值变为$S_{i}S\_i$ ​ ，这时$f_i=f_j+S[i]f\_i=f\_j+S[i]$，只要找到前面最小的一个$f_{j}f\_j$ ​ 来更新$f_{i}f\_i$ ​ 即可

考虑得到了这个$O(n^2)O(n^2)$的$dpdp$之后怎么优化，可以直接对着代码考虑

现在相当于一道数据结构题，需要支持：

查询满足$a_j⩽a_{i}a\_j\; \backslash leqslant\; a\_i$的$f_{j}f\_j$的最小值

让$a_i>a_{j}a\_i\; >\; a\_j$的$f_j+=ma{x}_{i=1}^i{a}_{i}f\_j\; +=\; max\_\{i=1\}^\{i\}\; a\_i$

让$a_i⩽a_{j}a\_i\; \backslash leqslant\; a\_j$的$f_j+=a_{j}f\_j\; +=\; a\_j$ ​

这是一个经典的分块维护凸包的模型，对于每个转移点$ii$，我们可以将其看做$y=a_i\ast x+f_i+by\; =\; a\_i\; *\; x\; +\; f\_i\; +\; b$ 的形式，$f_i+bf\_i\; +\; b$是常量，$xx$是被执行过操作$33$的次数

接下来可以将每个按照$a_{i}a\_i$ ​ 分块，因为$a_i⩽Na\_i\; \backslash leqslant\; N$，所以只要分为$\sqrt{N}\backslash sqrt\{N\}$ ​ 块即可

对于每一块，可以通过打标记来维护操作$22$(相同块内加的值是相同的)。同时我们可以将块内的每个转移点看做一个函数(也就是$y=a_i\ast x+f_i+by\; =\; a\_i\; *\; x\; +\; f\_i\; +\; b$)，其中自变量$xx$每次只会$+1+1$，现在我们只需要知道对于每个$xx$，这些函数对应的最小值。

也就是说我们只需要维护出红色的线段

这又是个经典模型，，而且考虑到该题比较好的性质，对于每一块只需要从前往后扫一遍，判断一下相邻点的位置关系即可。

查询的时候由于$xx$单增，只需要判断第一个元素和第二个元素的关系，如果不满足弹出队首即可

复杂度$O(N\sqrt{N})O(N\; \backslash sqrt\{N\})$

#pragma GCC optimize(2)
#include<bits/stdc++.h> 
#define Pair pair<int, LL>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define pb push_back 
#define LL long long 
#define ull unsigned long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7;
LL INF = 1e18;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
template <typename A, typename B> inline LL fp(A a, B p, int md = mod) {int b = 1;while(p) {if(p & 1) b = mul(b, a);a = mul(a, a); p >>= 1;}return b;}
template <typename A> A inv(A x) {return fp(x, mod - 2);}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
LL a[MAXN];
int block, Mx, ll[MAXN], rr[MAXN], belong[MAXN]; 
LL tag[MAXN], val[MAXN], num[MAXN];//mxa: 块中最大的a tag:每个块额外加的元素 num:每个块的系数 //queue<Pair> que[MAXN];//fi: x  se: b
struct Queue {
	int l, r;
	Pair q[401];
	Queue() {
		l = 1, r = 0;
		memset(q, 0, sizeof(q));
	}
	Pair front() {
		if(l > r) {puts("front is empty");exit(0);}
		return q[l];
	}
	void pop() {
		if(l > r) {puts("front is empty");exit(0);}
		l++;
	}
	bool empty() {
		return l > r;
	}
}que[401];
LL GetV(Pair x, int k) {
	return 1ll * x.fi * k + x.se;
}
LL QueryMin(int id) {//第id个块中的f最小值 
	int &l = que[id].l, &r = que[id].r;
	if(l > r) return INF;
	while(l < r && GetV(que[id].q[l], num[id]) > GetV(que[id].q[l + 1], num[id])) l++;
	LL ans = 1ll * que[id].front().fi * num[id] + tag[id] + que[id].front().se;
	return ans;
}
double GetP(Pair a, Pair b) {
	return (double)(a.se - b.se) / (b.fi - a.fi);
}
Queue Build(int ql, int qr) {
	Queue tq; int &l = tq.l, &r = tq.r; 
	for(int i = qr; i >= ql; i--) {
		while(l <= r && val[i] <= tq.q[r].se) r--;
		while(l < r && GetP({i, val[i]}, tq.q[r - 1]) < GetP(tq.q[r], tq.q[r - 1])) r--;
		tq.q[++r] = {i, val[i]};
	}
	return tq;
}
LL QueryMinF(int x) {//<=x中的f[j]的最小值 
	LL ans = INF;
	for(int i = 1; i <= Mx; i++) {
		if(rr[i] <= x) chmin(ans, QueryMin(i));
		else {
			int id = i;
			for(int j = ll[i]; j <= rr[i]; j++) {
				val[j] += 1ll * j * num[id] + tag[id];
				if(j <= x) chmin(ans, val[j]); 
			}
			num[id] = 0; tag[id] = 0;
			que[id] = Build(ll[id], rr[id]);		
			break;
		}
	}
	return ans;
}
void AddMx(int x, int v) {//a[i] <= x的位置的f全都加上v 
	for(int i = 1; i <= Mx; i++) {
		if(rr[i] <= x) tag[i] += v;
		else {
			int id = i;
			for(int j = ll[i]; j <= rr[i]; j++) {
				val[j] += 1ll * j * num[id] + tag[id];
				if(j <= x) val[j] += v;
			}
			num[id] = 0; tag[id] = 0;
			que[id] = Build(ll[id], rr[id]);	
			break;
		}
	}
}
void AddF(int x) {//a[i] >= x的位置的f全都加上a[i] 
	for(int i = Mx; i >= 1; i--) {
	int id = i;
		if(ll[i] >= x) {
			num[i]++;
		} else {
			for(int j = ll[i]; j <= rr[i]; j++) {
				val[j] += 1ll * j * num[id] + tag[id];
				if(j >= x) val[j] += j;
			}
			num[id] = 0; tag[id] = 0;
			que[id] = Build(ll[id], rr[id]);	
			break;
		}
	}
}
void AddPoint(int x, LL v) {//第x个位置新加入一个值为v的数 
	int id = belong[x];
	for(int j = ll[id]; j <= rr[id]; j++) {
		val[j] += 1ll * j * num[id] + tag[id];
	}
	chmin(val[x], v);
	num[id] = 0; tag[id] = 0;
	que[id] = Build(ll[id], rr[id]);
}
signed main() {
//	freopen("a1.in", "r", stdin);

	N = read(); block = sqrt(N);
	assert(N >= 1 && N <= 70000);
	memset(ll, 0x3f, sizeof(ll));
	memset(val, 0x7f, sizeof(val));
	belong[0] = 1; ll[1] = 0;
	for(int i = 1; i <= N; i++) {
		a[i] = read();
		assert(a[i] >= 1 && a[i] <= N);
		belong[i] = (i - 1) / block + 1;
		chmin(ll[belong[i]], i);
		chmax(rr[belong[i]], i);
		chmax(Mx, belong[i]);
	}
	AddPoint(a[0], 0);
	LL mx = 0;
	for(int i = 1; i <= N; i++) {
		LL mn = QueryMinF(a[i]);; chmax(mx, a[i]);
		AddMx(a[i] - 1, mx);
		AddF(a[i]);
		AddPoint(a[i], mn + a[i]);
	}
	for(int i = 0; i <= N; i++) {
		int id = belong[i];
		val[i] += 1ll * i * num[id] + tag[id];
	}
	LL ans = 1e18;
	for(int i = 0; i <= N; i++) 
		chmin(ans, val[i]);
	cout << ans << '\n';
    return 0;
}
/*

*/