斜率优化-李超线段树维护凸包

背景

遇到了一道矩形上的DP，点$(i,j)$的处理过后的DP为$min_{\forall{i'<=i,j'<=j,(i,j)\neq(i',j')} }(A_{(i,j)(i',j')})$。其中$A_{(i,j)(i',j')}$为$buff_{(i,j)}\times (i+j)$。看柿子很斜率优化，但是二维平面上很不好整，打了个暴力就溜了。然后发现这题人均正解，还被教练嘲讽：“这不是套路题吗？”。嘤嘤嘤自闭了。

套路

我们发现转移柿子是形如$a_{(i',j')}+b_{(i',j')}\times c_{(i,j)}$。$a,b,c$分别是只和一个点对相关的柿子。我们发现这是一个斜率优化：我们需要在很多状态中求最大值，而每个状态的大小是由自己本身的性质($k,b$)和变量组成的$x$。（P.S. 如果$a$还乘了个和$(i,j)$相关的柿子$d$，可以把$c$变成$\frac{c}{d}$然后把$d$提出去）

但是我们考虑，这道题的直线并没有单调性，所以需要两层CDQ，可能还需要个动态凸包啥的（我也没细想）。于是我们考虑使用李超线段树。

李超线段树其实就是维护了一个凸包。凸包上的每条边都代表一个转移状态（一般斜率优化的状态在点上，当然也有状态在边上的写法）。当你确定一个自变量$x$的时候，用$y=x$这条直线去切凸包，切到的直线就是最优决策。还有一个问题就是这道题从哪里转移过来的限制是一个二维前缀。以$x$递增的顺序计算DP值可以避免$x$坐标的访问越界，但是$y$坐标无法避免。解决方案只有套个树状数组，树状数组每个节点都代表了一个区间，对每个树状数组节点都建个李超树即可。（其实就是树套树）

需要注意的是：我们用树状数组维护的那一维是尽量小的那一维，这样我们的时间就能少一些。
时间复杂度：$nm\log _2{min(m,n)}$
空间复杂度：$nm\log _2^2{min(m,n)}$
代码：

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=1e5+1000;
const ll inf=1e18;
int buff[maxn],val[maxn];
int bk1[maxn],bk2[maxn];
int n,m;
int get_id(int i,int j,int g=m){return (i-1)*g+j;}
struct line{
	int k;ll b;
	ll get(int x){return 1ll*x*k+b;}
};
line mk_l(int k,ll b){line tmp;tmp.k=k,tmp.b=b;return tmp;}
struct li_chao_segment_tree_in_a_BIT{
	line val[maxn*100];
	int cnt,rt[330],ls[maxn*100],rs[maxn*100];
	void ins(int &idx,int l,int r,line L){
		if(!idx){idx=++cnt;val[idx]=L;return;}
		int mid=(l+r)>>1;
		if(val[idx].get(mid)<L.get(mid))swap(val[idx],L);
		if(val[idx].get(l)<L.get(l))ins(ls[idx],l,mid,L);
		if(val[idx].get(r)<L.get(r))ins(rs[idx],mid+1,r,L);
	}
	ll query(int idx,int l,int r,int x){
		if(!idx)return 0;
		ll res=val[idx].get(x);
		if(l==r)return res;
		int mid=(l+r)>>1;
		return max(res,(x<=mid)?query(ls[idx],l,mid,x):query(rs[idx],mid+1,r,x));
	}
	void ins(int loc,line L){
		for(int i=loc;i<=m;i+=i&(-i))ins(rt[i],1,n+m,L);
	}
	ll query(int loc,int x){
		ll ans=-inf;
		for(int i=loc;i;i-=i&(-i))ans=max(ans,query(rt[i],1,n+m,x));
		return ans;
	} 
}t;
ll dp[maxn];
ll g(int i,int j){return dp[get_id(i,j)]-1ll*buff[get_id(i,j)]*(i+j);}
int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n)rep(j,1,m)scanf("%d",&buff[get_id(i,j)]);
	rep(i,1,n)rep(j,1,m)scanf("%d",&val[get_id(i,j)]);
	if(n<m){//m作为树状数组的维度 应该尽量小
		rep(i,1,m)rep(j,1,n)bk1[get_id(i,j,n)]=buff[get_id(j,i)],bk2[get_id(i,j,n)]=val[get_id(j,i)];
		swap(n,m);rep(i,1,n*m)buff[i]=bk1[i],val[i]=bk2[i];
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[get_id(1,1)]=0;t.ins(1,mk_l(buff[get_id(1,1)],g(1,1)));
	rep(i,1,n)rep(j,1,m)if(i!=1||j!=1){
		int idx=get_id(i,j);
		dp[idx]=t.query(j,i+j)+val[idx];
		t.ins(j,mk_l(buff[idx],g(i,j)));
	}
	cout<<dp[get_id(n,m)];
	return 0;
}