# 單調隊列
## [a146. Sliding Window](https://zerojudge.tw/ShowProblem?problemid=a146)

## [Nearest Smaller Values](https://cses.fi/problemset/task/1645)

## [Advertisement](https://cses.fi/problemset/task/1142)

## 有限個數的多重背包問題

# 斜率優化
## [Monster Game I](https://cses.fi/problemset/task/2084)
$$
dp[i]=\min_{j<i} \{ f_j\times s_i+dp[j]\}
$$
### 觀察1
很像直線$y=ax+b$的形式

所以我們可以維護一個直線的集合，每次詢問找將$s_i$帶入這些直線的最小值。

詢問後加入集合
### 觀察2
對於所有的$j<i$，我們只需要存黑色的就好。
剛好會是一個凸包

### 觀察3
計算答案
因為詢問單調，如果詢問是藍色，那麼斜率比轉移點大的都可以刪掉了。

### 觀察4

將直線加入凸包後，可能會有一些斜率小且**連續**的直線被淘汰。

### 實作

維護一個直線的deque，斜率遞減。

詢問時:
重複比較斜率最**大**的兩條直線$L_1$、$L_2$，如果$L_2$的答案比$L_1$還要好的話就可以將$L_1$丟掉，反之$L_1$就會是轉移點。

加入時:
對於斜率最**小**的兩條直線$L_1$、$L_2$及加入的直線$L$，有兩種情形:

若$L$、$L_2$的交點$C$的$x$座標小於$L_1$、$L_2$的交點$D$的$x$座標，則可以把$L_1$丟掉。(這一題斜率都是正的，所以也可以看$y$座標)
即
$$
\begin{cases}
C_y=L_{a}C_x+L_b
\\C_y=L_{2_a}C_x+L_{2_b}
\\D_y=L_{1_a}D_x+L_{1_b}
\\D_y=L_{2_a}D_x+L_{2_b}
\end{cases}
$$
中，判斷是否有$C_x<D_x$，由上式可知
$$
\begin{cases}
C_x=\frac{L_b-L_{2_b}}{L_{2_a}-L_a}
\\D_x=\frac{L_{1_b}-L_{2_b}}{L_{2_a}-L_{1_a}}
\end{cases}
$$
為了避免浮點數誤差，交叉相乘，所以要檢查
$$
(L_b-L_{2_b})(L_{2_a}-L_{1_a})\leq (L_{2_a}-L_a)(L_{1_b}-L_{2_b})
$$
是否成立
### code

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct F{
    int a,b;
    F(int _a,int _b):a(_a),b(_b){}
    int operator()(int x){
        return a*x+b;
    }
};
bool check(F l1,F l2,F l){
    return (l.b-l2.b)*(l2.a-l1.a)<=(l2.a-l.a)*(l1.b-l2.b);
}
signed main(){
    int n,x;
    cin>>n>>x;
    vector<int> s(n+1),f(n+1),dp(n+1,1e18);
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) cin>>f[i];
    dp[0]=0;
    f[0]=x;
    deque<F> dq;
    dq.push_back(F(x,0));
    for(int i=1;i<=n;i++){
        while(dq.size()>=2&&dq[1](s[i])<=dq[0](s[i])){
            dq.pop_front();
        }
        dp[i]=dq[0](s[i]);
        F l(f[i],dp[i]);
        while(dq.size()>=2&&check(dq.back(),dq[dq.size()-2],l)){
            dq.pop_back();
        }
        dq.push_back(l);
    }
    cout<<dp[n]<<endl;
}

## [Monster Game II](https://cses.fi/problemset/task/2085)
查詢和斜率都不單調的版本

李超線段樹

查詢不單調:
對每個直線存他是最佳答案的區間，二分搜

斜率不單調:
動態凸包