# 李超線段樹

### 前言
先看[題目](https://cses.fi/problemset/task/2085)，此題也就是[斜率優化](https://hackmd.io/GDLXmEqaT32xfzeHmzPxmw)的延伸，差別在於斜率的單調性有無，接下來要講解斜率無單調性的做法 : 李超線段樹。

------------
### 目標
給定一個些線($f(x)=ax+b$)，求$f(x)$的最小值。
### 概念
首先我們可以開一顆$x$值域的線段樹，每個區間存一半以上保證有最小值的線。
### 更新
在加入一條線的時候，跟原本區間存的線比較，如果$f(mid)$比原本的小，就覆蓋，接著把比較大的線往下遞迴，有可能在後面會出現最小值。
要判斷往左還往右遞迴之前，必須要先做前置作業，就是先確定誰的斜率大誰的斜率小，這裡統一$seg[now]$裡放斜率大的。

**狀況一 :** $seg[now]的f(mid)<ins的f(mid)$
代表mid發生在兩線交點的左邊，mid左邊的最小值一定是發生在$seg[now]$這條線，但是右邊不一定，所以往右邊遞迴確認。
**狀況二 :** $ins的f(mid)<seg[now]的f(mid)$
代表mid發生在兩線交點的右邊，mid右邊的最小值一定是發生在$ins$這條線，但是左邊不一定，所以往左邊遞迴確認。

最後($l=r$時)需跟已儲存的線判斷誰比較小，因為會被遞迴的區間都是待確認，所以還要再判斷一次才可更新答案。

void update(line ins,int now=1,int l=1,int r=200000){
	if(l==r){
		if(ins.f(l)<seg[now].f(l)) seg[now]=ins; //有比較小才更新
		return;
	}
	int mid=(l+r)/2,L=now*2,R=now*2+1;
	if(seg[now].m<ins.m) swap(ins,seg[now]);  //確定斜率
	
	if(seg[now].f(mid)<ins.f(mid)){  //Situation 1
        seg[now]=
		update(ins,R,mid+1,r);
	}else{  //Situation 2
		swap(ins,seg[now]);  //把seg[now]設成成ins，並把原seg[now]拿去給子樹節點更新
		update(ins,L,l,mid);
	}
	
}

### 查詢
把路徑上會遇到的線取$min\{f(x)\}$就好了。

如果$x$屬於的半邊在更新的時候是保證$seg[now]$的線為最小值，就不會繼續遞迴，有最小值的線會存在$seg[now]$，但如果最小值不確定時，就會繼續遞迴下去。但是在查詢的時候不會知道$x$屬於的半邊是有沒有確認過答案，所以不僅要繼續遞迴下去，還要跟$seg[now]$的$f(x)$取$min$。

int query(int x,int now=1,int l=1,int r=200000){
	if(l==r) return seg[now].f(x);
	
	int mid=(l+r)/2,L=now*2,R=now*2+1,cur=seg[now].f(x);
	if(x<=mid){
		return min(cur,query(x,L,l,mid));
	}else{
		return min(cur,query(x,R,mid+1,r));
	}
}

::: spoiler Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005
#define inf LLONG_MAX

int s[MAXN],f[MAXN],dp[MAXN];

struct line{
	int m,b=inf;
	int y(int x){
		return m*x+b;
	}
}seg[MAXN*4];

void update(line ins,int now=1,int l=1,int r=200000){
	if(l==r){
		if(ins.y(l)<seg[now].y(l)) seg[now]=ins;
		return;
	}
	int mid=(l+r)/2,L=now*2,R=now*2+1;
	if(seg[now].m<ins.m) swap(ins,seg[now]);
	
	if(seg[now].y(mid)<ins.y(mid)){ 
		update(ins,R,mid+1,r);
	}else{
		swap(ins,seg[now]);
		update(ins,L,l,mid);
	}
	
}

int query(int x,int now=1,int l=1,int r=200000){
	if(l==r) return seg[now].y(x);
	
	int mid=(l+r)/2,L=now*2,R=now*2+1,cur=seg[now].y(x);
	if(x<=mid){
		return min(cur,query(x,L,l,mid));
	}else{
		return min(cur,query(x,R,mid+1,r));
	}
}

signed main(){
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++) cin >> s[i];
	for(int i=1;i<=n;i++) cin >> f[i];
	
	update({k,0});
	
	for(int i=1;i<=n;i++){
		int x=s[i];
		dp[i]=query(x);
		line now={f[i],dp[i]};
		update(now);
	}
	cout << dp[n] << '\n';
}

:::