决策单调性
四边形不等式
对于一个序列 \(w\)，称其满足四边形不等式当且仅当 ：
\[\forall a<b\le c<d,w_{a,d}+w_{b,c}\ge w_{a,c}+w_{b,d} \]\(\forall i,j,w_{i,j+1}+w_{i+1,j}\ge w_{i,j}+w_{i+1,j+1}\) 是 \(w\) 满足四边形不等式的充要条件。
proof：
必要性显然，考虑证明充分性。
上面式子移项可得：\(w_{i,j+1}-w_{i,j}\ge w_{i+1,j+1}-w_{i+1,j}\)，也就是说第二位相邻两项的差值随着第一维的增大而减小，那么相邻两项的差值可以放缩为任意两项的差值，即 \(w_{i,j+q}-w_{i,j}\ge w_{i+1,j+q}-w_{i,j}\)，那么显然第一维也是可以这样处理的，得到 \(w_{i,j+q}-w_{i,j}\ge w_{i+p,j+q}-w_{i,j}\)，再简单整理一下就是四边形不等式。
因此满足四边形不等式的判定可以使用这个式子。
然后考虑如下 DP：
\[f_i=\min g_j+w_{j,i} \]设 \(c\) 的转移点为 \(b\)，\(d\) 的转移点为 \(a\)，\(c<d,a< b\)，那么有：
\[f_c=g_b+w_{b,c},f_d=g_a+w_{a,d} \]考虑交换转移点得到：
\[f_c'=g_a+w_{a,c},f_d'=g_b+w_{b,d} \]由四边形不等式得：\(f_c'+f_d'\le f_c+f_d\)，矛盾，所以 \(a\) 肯定大于等于 \(b\)，即存在决策单调性。
实现
决策单调性的实现一般有分治做法和二分栈两种做法。
- 分治，
solve(l,r,x,y)表示要处理 \([l,r]\) 的 DP 值，且决策点的取值范围是 \([x,y]\)，每次取出 \(l,r\) 中点暴力枚举然后缩小决策点取值范围即可，时间 \(\mathcal{O}(n\log n)\)。 - 二分栈，每个决策点可以更新到的是一个区间，考虑从左往右加入决策点，且目前我们已经知道整个序列被前面的决策点支配的情况，用一个栈来储存，发现这个决策点加入后支配的区间一定是一个后缀。所以如果栈顶决策点支配的整段区间都应该被新决策点取代就出栈，最后对于一个不能取代完的区间就二分一下把区间裂开。时间 \(\mathcal{O}(n\log n)\)。
分治做法的缺点是不能处理自己转移自己的情况，只能处理分层的情况，但是它的优点是当 \(w\) 不太好计算，但是简单可以从两边加入删除一个数，直接暴力加入删除时间还是 \(\mathcal{O}(n\log n)\) 的。
但是如果出现自己转移自己而且又需要像上面那样计算 \(w\) 呢？可以考虑 CDQ 分治，每次左边贡献右边的时候就跑一边上面那个分治就好了，时间 \(\mathcal{O}(n\log^2 n)\)。
「USACO 2019.2 Platinum」Mowing Mischief
题意
给定平面上的一些点，你需要选取一些点使得横坐标纵坐标都递增，且选取的点尽量多。在点数尽量多的前提下，使相邻点的 \(\Delta x\cdot \Delta y\) 之和最小。
所有点的横纵坐标都不相同 。
题解
第一个问题就是 LIS，我们先求出 \(f_i\) 表示做到前 \(i\) 个点的且第 \(i\) 个点必选的最多选取的点数。
然后处理第二问，先按照 \(f\) 进行分层。对于一个点 \(i\)，能转移到它的点需要满足是上一层的，而且横纵坐标都比 \(i\) 的小。
发现一个性质：在同一层中，按照横坐标从小到大排序，则纵坐标也会递减。这是因为层内的点都是不能出现 \(x_1<x_2\) 且 \(y_1<y_2\) 的情况的，所以显然能转移到 \(i\) 的点在上一层中形成了一个区间，这个区间可以二分找到。
假设没有横纵坐标都比 \(i\) 小的限制，如何快速地转移，考虑决策单调性。设上一层的两个决策点 \(j<k\)。如果 \(k\) 比 \(j\) 更优：
\[\begin{aligned} dp_k+(x_i-x_k)(y_i-y_k)&\le dp_j+(x_i-x_j)(y_i-y_j)\\ x_i(y_j-y_k)+y_i(x_j-x_k)&\le (dp_j+x_jy_j)-(dp_k+x_ky_k) \end{aligned} \]所以 \(i\) 越大，上面的不等式越不容易满足，所以决策点是随着 \(i\) 的变大而变小的。
考虑区间的限制，可以使用线段树分治，把询问点按照可行的决策点区间放入 log 个线段树节点，然后再在每个线段树的节点内跑决策单调性。
时间 \(\mathcal{O}(n\log^2 n)\)。
#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#define N 200005
#define ls k<<1
#define rs k<<1|1
#define int long long
using namespace std;
inline int read(){
int x=0,f=0; char ch=getchar();
while(!isdigit(ch)) f|=(ch==45),ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
struct node{
int x,y,f;
}a[N];
int n,t,st[N],top,rev[N],dp[N],cnt,q[N],fick[N];
inline bool cmp1(node x,node y){
return x.x<y.x;
}
inline bool cmp2(node x,node y){
if(x.f==y.f) return x.x<y.x;
return x.f<y.f;
}
vector<int> mp[4*N];
void insert(int k,int l,int r,int x,int y,int i){
if(x<=l && r<=y) return (void)(mp[k].push_back(i));
int mid=l+r>>1;
if(x<=mid) insert(ls,l,mid,x,y,i);
if(mid+1<=y) insert(rs,mid+1,r,x,y,i);
}
void solve(int l,int r,int x,int y){
int mid=x+y>>1,id=0;
fick[q[mid]]=1e18;
for(int i=l;i<=r;++i){
int tmp=dp[rev[i]]+(a[q[mid]].x-a[rev[i]].x)*(a[q[mid]].y-a[rev[i]].y);
if(tmp<fick[q[mid]]) fick[q[mid]]=tmp,id=i;
}
if(x<mid) solve(id,r,x,mid-1);
if(mid<y) solve(l,id,mid+1,y);
}
void work(int k,int l,int r){
if(!mp[k].empty()){
for(int i=0;i<mp[k].size();++i) q[i+1]=mp[k][i];
solve(l,r,1,mp[k].size());
for(int i=1;i<=mp[k].size();++i) dp[q[i]]=min(dp[q[i]],fick[q[i]]);
mp[k].clear();
}
if(l==r) return;
int mid=l+r>>1;
work(ls,l,mid),work(rs,mid+1,r);
}
signed main(){
n=read(),t=read();
for(int i=1;i<=n;++i){
a[i].x=read(),a[i].y=read();
}
a[++n]={0,0,0},a[++n]={t,t,0};
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;++i){
int l=1,r=top;
while(l<=r){
int mid=l+r>>1;
if(a[i].y>st[mid]) l=mid+1;
else r=mid-1;
}
if(r==top) top++;
st[r+1]=a[i].y;
a[i].f=r+1;
}
sort(a+1,a+n+1,cmp2);
memset(dp,0x3f,sizeof(dp));
rev[1]=cnt=1,dp[1]=0;
for(int l=2,r=2;l<=n;l=++r){
while(r+1<=n && a[r+1].f==a[l].f) r++;
for(int i=l;i<=r;++i){
int L=1,R=cnt;
while(L<=R){
int mid=L+R>>1;
if(a[rev[mid]].x<a[i].x) L=mid+1;
else R=mid-1;
}
int y=R;
L=1,R=y;
while(L<=R){
int mid=L+R>>1;
if(a[rev[mid]].y<a[i].y) R=mid-1;
else L=mid+1;
}
int x=L;
insert(1,1,cnt,x,y,i);
}
work(1,1,cnt);
cnt=r-l+1;
for(int i=l;i<=r;++i) rev[i-l+1]=i;
}
cout<<dp[n];
return 0;
}
凸优化
如果一个 \(f\) 说它是凸的，则 \(f\) 差分后单调。
\(f_i\) 表示流量为 \(i\) 时的最小费用，这就是一个经典的下凸函数。
有些凸性多少和费用流搭点关系。
考虑如下 DP：
\[f_i=\max_{j+k=i} g_j+h_k \]这是一个经典的 max + 卷积，如果 \(g,h\) 都是上凸的，则可以优化到 \(\mathcal{O}(n)\)。
考虑把 \(g,h\) 差分，\(f_i\) 其实就是两边选前几个然后一共选 \(i\) 个，发现我们是可以选到前 \(i\) 大的，因为 \(g,h\) 差分后单调不增，所以归并即可。
其实这个也可以理解为做闵可夫斯基和。
Gym102331J Jiry Matchings
题意
给定一棵树，边有边权，对于每个 \(k\) 求出 \(k\) 条边的匹配的最大权值和。
解法
\(f_{u,i}\) 表示 \(u\) 子树中匹配了 \(i\) 条边的最大权值和，\(g_{u,i}\) 同理，但是强制不选 \(i\)，因为是费用流模型， \(f,g\) 都是上凸的。所以可以简单做到 \(\mathcal{O}(n^2)\)。
但是第二维的大小是子树大小的一半，还是可以优化的。
优化复杂度的关键肯定是找带权中心分治然后卷积。首先肯定是重链剖分，对于一个点的轻子树我们需要先合并好，这个直接分治乘就好，先找到带权中心，做好左右儿子的 \(f,g\) 然后闵可夫斯基和。
之后就是一条重链上的问题，这就变成序列问题了，同样也是分治乘，不过要记一下左右端点用没用。
总的时间 \(\mathcal{O}(n\log^2 n)\)。
#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<vector>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&-(x))
#define popcount(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define umap unordered_map
#define int long long
#define N 200005
using namespace std;
inline int read(){
int x=0,f=0; char ch=getchar();
while(!isdigit(ch)) f|=(ch==45),ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
vector<int> merge(vector<int> A,vector<int> B){
int i=0,j=0;
vector<int> res;
res.push_back(max(-infll,A[0]+B[0]));
while(i+1<A.size() || j+1<B.size()){
if(j+1==B.size() || (i+1<A.size()&&A[i+1]+B[j]>A[i]+B[j+1])) i++;
else j++;
res.push_back(max(-infll,A[i]+B[j]));
}
return res;
}
struct edge{
int b,c,n;
}e[N*2];
int n,h[N],tot,sze[N],son[N],len[N];
inline void charu(int a,int b,int c){
e[++tot].b=b,e[tot].c=c,e[tot].n=h[a],h[a]=tot;
}
void dfs1(int u,int fa){
sze[u]=1;
for(int i=h[u];i;i=e[i].n){
int v=e[i].b;
if(v==fa) continue;
dfs1(v,u);
sze[u]+=sze[v];
if(sze[v]>sze[son[u]]) son[u]=v,len[v]=e[i].c;
}
}
inline vector<int> mx(vector<int> F,vector<int> G){
vector<int> res;
res.resize(max(F.size(),G.size()));
for(int i=0;i<min(F.size(),G.size());++i) res[i]=max(F[i],G[i]);
for(int i=min(F.size(),G.size());i<F.size();++i) res[i]=F[i];
for(int i=min(F.size(),G.size());i<G.size();++i) res[i]=G[i];
return res;
}
inline vector<int> get(vector<int> F,int x){
F.push_back(0);
for(int i=(int)F.size()-1;i>=1;--i) F[i]=F[i-1]+x;
F[0]=-infll;
return F;
}
vector<int> f[N],g[N];
int id[N],cnt;
void solve1(int l,int r,vector<int> &F,vector<int> &G){
if(l==r){
G=f[id[l]];
F=mx(f[id[l]],g[id[l]]);
return;
}
int mid=l,sum=0,now=f[id[l]].size();
for(int i=l;i<=r;++i) sum+=f[id[i]].size();
while(mid+1<r && 2*now<sum) mid++,now+=f[id[mid]].size();
vector<int> lf,lg,rf,rg;
solve1(l,mid,lf,lg),solve1(mid+1,r,rf,rg);
F=mx(merge(lf,rg),merge(lg,rf));
G=merge(lg,rg);
}
struct node{
vector<int> a00,a01,a10,a11;
};
node solve2(int l,int r){
node res;
if(l==r){
res.a00.push_back(-infll);
res.a01=res.a10=g[id[l]];
res.a11=mx(f[id[l]],g[id[l]]);
return res;
}
int mid=l,sum=0,now=f[id[l]].size();
for(int i=l;i<=r;++i) sum+=f[id[i]].size();
while(mid+1<r && 2*now<sum) mid++,now+=f[id[mid]].size();
node L=solve2(l,mid),R=solve2(mid+1,r);
int x=len[id[mid+1]];
res.a00=mx(merge(L.a01,R.a10),get(merge(L.a00,R.a00),x));
res.a01=mx(merge(L.a01,R.a11),get(merge(L.a00,R.a01),x));
res.a10=mx(merge(L.a11,R.a10),get(merge(L.a10,R.a00),x));
res.a11=mx(merge(L.a11,R.a11),get(merge(L.a10,R.a01),x));
return res;
}
void dfs2(int rt){
for(int u=rt;u;u=son[u]){
for(int i=h[u];i;i=e[i].n){
int v=e[i].b;
if(sze[v]<sze[u] && v!=son[u]) dfs2(v);
}
cnt=0;
for(int i=h[u];i;i=e[i].n){
int v=e[i].b;
if(sze[v]<sze[u] && v!=son[u]){
id[++cnt]=v;
g[v]=get(g[v],e[i].c);
}
}
if(cnt==0){
f[u].push_back(0);
g[u].push_back(0);
continue;
}
solve1(1,cnt,f[u],g[u]);
}
cnt=0;
for(int u=rt;u;u=son[u]) id[++cnt]=u;
node tmp=solve2(1,cnt);
g[rt]=max(tmp.a00,tmp.a01);
f[rt]=max(tmp.a10,tmp.a11);
}
signed main(){
n=read();
for(int i=1;i<n;++i){
int x=read(),y=read(),z=read();
charu(x,y,z),charu(y,x,z);
}
dfs1(1,0);
dfs2(1);
for(int i=1;i<f[1].size();++i){
if(f[1][i]>=(int)-1e15) printf("%lld ",f[1][i]);
else printf("? ");
}
for(int i=f[1].size();i<n;++i) printf("? ");
return 0;
}