CF1175G - Yet Another Partiton Problem

Posted on Edited on In

CF1175G - Yet Another Partiton Problem

题目大意

给定序列 \(a_i\) ，现在将其分成 \(k\) 段，每段 \([l,r]\) 的权值定义为 \((r-l+1)\max\{a_{l..r}\}\)

求最小化权值总和


分析

显然有 \(\mathbb{Naive}\) 的 \(dp\)

\(dp_{i,j}\) 表示前 \(i\) 个分了 \(j\) 段的答案，直接做复杂度为 \(O(n^2k)\)

优化它有几种常见思路：

1.贪心简化决策

设每个段最大值 \(b_i\) ，则一个段不能向左边扩展的条件是

两端的 \(b_{i-1}<b_i\) （扩展会亏），或者 \(a_{l_i-1}>b_i\) （扩展会改变 \(b_i\) ）

这样能稍微限制一下转移，然而并不好优化

2.决策单调性

枚举区间进行决策的问题通常具有单调性

于是尝试通过分治决策单调性优化到 \(O(nk\log n)\)

然而已经被垃圾数据击毙 尝试证明这是假的

3.斜率优化

考虑确定 \(\max a_i\) 之后，两侧 \(r-l+1\) 就是一个斜率优化的转移形式

考虑如何实现这个斜率优化

首先将 \(dp_{i,j}\) 两个维护交换，按照分段数一层层进行转移

每一层，可以考虑在 \(a_i\) 的笛卡尔树上进行转移

每次考虑所有跨过当前节点的转移区间

那么就要支持：

1.查询左子树 \(dp_l-l \cdot a_u\) 的最小值

2.更新右子树 \(dp'_r+r\cdot a_u\) 的最小值


option1

为了实现1操作，容易想到从子树中合并凸包，或者直接进行区间凸包查询

合并凸包的问题可以暴力李超树合并维护

但事实上区间凸包是可以维护的，方法如下

1.维护一个静态线段树， \(O(n\log n)\) 归并预处理凸包

2.查询 \(a_u\) 递增，具有单调性，可以在每个被查询节点上处理一个指针

复杂度为就是均摊 \(O(n\log n)\)


option2

子树更新答案，可以通过可持久化李超树|李超树区间修改实现

复杂度分别为 \(O(n\log n),O(n\log^2n)\) ，鉴于区间修改常数不满，差别不会太大

但实际上也可以通过朴素凸包实现：

从根开始dfs，每次插入一个 \(x+y \cdot i\) 的线段形式

\(y\) 是递增的，插入具有单调性，可以维护一个栈凸包

每次二分弹掉节点，插入自己

（不能直接弹，因为要支持回撤，会使得原先是均摊 \(O(n)\) 的弹栈操作退化为 \(O(n^2)\) ）

查询也可以通过二分解决（这实际上是一个经典树上斜率优化问题）



我当然写了李超树啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int N=2e4+10,U=2e4,INF=1e9+10;

int n,m,A[N];
struct Node{
	ll k,b;
	Node(){}
	Node(ll k,ll b):k(k),b(b){}
	ll operator [] (ll x) const { return k*x+b; }
};
struct Tree{
	static const int M=N*20;
	Node s[M];
	int ls[M],rs[M],cnt;
	int New(){
		int u=++cnt;
		ls[u]=rs[u]=0,s[u]=Node(INF,INF);
		return u;
	}
	void Upd(int &p,int l,int r,int ql,int qr,Node x){
		if(x.k==INF) return;
		if(!p) p=New();
		int mid=(l+r)>>1;
		if(ql<=l && r<=qr) {
			if(x[mid]<s[p][mid]) swap(s[p],x);
			if(l==r) return;
			if(x[l]<s[p][l]) Upd(ls[p],l,mid,ql,qr,x);
			if(x[r]<s[p][r]) Upd(rs[p],mid+1,r,ql,qr,x);
			return;
		}
		if(ql<=mid) Upd(ls[p],l,mid,ql,qr,x);
		if(qr>mid) Upd(rs[p],mid+1,r,ql,qr,x);
	}
	ll Que(int p,int l,int r,int x){
		if(!p) return INF;	
		if(l==r) return s[p][x];
		int mid=(l+r)>>1;
		return min(s[p][x],x<=mid?Que(ls[p],l,mid,x):Que(rs[p],mid+1,r,x));
	}
	int Union(int x,int y,int l,int r){
		if(!x||!y) return x|y;
		Upd(x,l,r,l,r,s[y]);
		int mid=(l+r)>>1;
		ls[x]=Union(ls[x],ls[y],l,mid),rs[x]=Union(rs[x],rs[y],mid+1,r);
		return x;
	}
} X,Y;

int ls[N],rs[N],stk[N],top,mk[N];
int dp[110][N];

int rt[N],Rt;
void Solve(int k,int u,int l,int r){
	if(l>r) return;
	Solve(k,ls[u],l,u-1),Solve(k,rs[u],u+1,r);
	rt[u]=rt[ls[u]];
	if(u>1) X.Upd(rt[u],1,U,1,U,Node(-(u-1),dp[k][u-1]));
	int res=X.Que(rt[u],1,U,A[u]);
	Y.Upd(Rt,1,n,u,r,Node(A[u],res));
	rt[u]=X.Union(rt[u],rt[rs[u]],1,U);
}

int main(){
	X.s[0]=Y.s[0]=Node(INF,INF);
	n=rd(),m=rd();
	rep(i,1,n) {
		A[i]=rd();
		while(top && A[stk[top]]<A[i]) ls[i]=stk[top--];
		if(top) rs[stk[top]]=i;
		stk[++top]=i;
	}
	rep(i,1,n) mk[ls[i]]=mk[rs[i]]=1;
	int rt=0;
	rep(i,1,n) if(!mk[i]) rt=i;
	int ma=0;
	rep(i,1,n) cmax(ma,A[i]),dp[1][i]=ma*i;
	rep(i,1,m-1) {
		X.cnt=0,Y.cnt=0;
		Solve(i,rt,1,n);
		rep(j,1,n) dp[i+1][j]=Y.Que(1,1,n,j);
	}
	printf("%d\n",dp[m][n]);
}