# 練題 洛谷P1295 [TJOI2011]書架 (2022.2.17)
###### tags: `競程筆記`

## 題意
https://www.luogu.com.cn/problem/P1295
給出一個長度為 $n$ 的序列 $h$，請將 $h$ 分成若干段，滿足每段數字之和都不超過 $m$，最小化每段的最大值之和。
$n \le 10^5$, $h_i \le m \le 10^9$

## 想法
很容易推出dp式
$dp(i) = \min(dp(j)+\max(h_{j+1}...h_{i})), ~~j=1\cdots i-1$ 且 $sum(h_{j+1}...h_i)\le m$
但直接做是 $O(n^2)$

定義$mx(j)$為 $h_{j+1}$ 到 $h_i$ 的最大值，發現當i遞增時，可以視為$mx(i)$的動態更新，而$dp(i)$就是合法區間內 $dp(j)+mx(j)$ 的最小值。

可以轉化為資結問題：給序列$a,b$，求下列兩種操作：
1. 區間修改$a$的值
2. 求區間內$a_i+b_i$的最小值

這題還要利用$mx$序列必遞減，$dp$序列必遞增，所以比較好維護。

* 操作1：先二分出要「改值」的區間，然後改值打懶標。我用一個vector存「$mx$值」及「該值最左邊出現的位置」的 pair，不然如果是直接紀錄就沒意義了
* 操作2：先利用前綴和，二分出$j$的合法區間，然後就一般線段樹會做的事
* push：兩個子區間的所有 $mx$ 都要被改成某數，因此 $mx+dp$ 的最小值一定出現在 $dp$ 值最小的那個位置，也就是「該區間的最左邊」
* pull：直接繼承兩個子區間的$data$的較小者

:::spoiler AC Code

// Cookie197 
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
//#define mod 998244353
#define mod 1000000007
#define endl "\n"
#define inf (ll)(1e18)
#define out(x) cout << #x << " = " << x <<endl;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll arr[100005],pre[100005];
ll n,m;
ll dp[100005];

struct node{
    ll tag,data;
    // tag = a的改值tag  data = a+b的min
}st[400005];

void push(ll l,ll r,ll id){
    if (!st[id].tag) return;
    st[id*2].tag = st[id].tag;
    st[id*2+1].tag = st[id].tag;
    st[id*2].data = st[id].tag + dp[l]; // 可以醬是因為dp是遞增
    ll mid = (l+r)>>1;
    st[id*2+1].data = st[id].tag + dp[mid+1];

    st[id].tag = 0;
}
void pull(ll l,ll r,ll id){
    st[id].data = min(st[id*2].data, st[id*2+1].data);
}

void a_change(ll l,ll r,ll L,ll R,ll id,ll x){
    if (R<l || r<L) return;
    if (l<=L && R<=r){
        st[id].tag = x;
        st[id].data = x+dp[L];
        return;
    }
    push(L,R,id);
    ll mid = (L+R)>>1;
    a_change(l,r,L,mid,id*2,x), a_change(l,r,mid+1,R,id*2+1,x);
    pull(L,R,id);
}

ll query(ll l,ll r,ll L,ll R,ll id){
    if (R<l || r<L) return 1e9;
    if (l<=L && R<=r){
        return st[id].data;
    }
    push(L,R,id);
    ll mid = (L+R)>>1;
    return min(query(l,r,L,mid,id*2),query(l,r,mid+1,R,id*2+1));
}

vector<pii> mx; // value of mx, starting pos
signed main(){
    Why_does_competitive_programming_even_exist;
    n=read(); m=read(); n++;
    for (ll i=2;i<=n;i++) arr[i]=read();
    for (ll i=2;i<=n;i++) pre[i] = pre[i-1]+arr[i];
    
    mx.push_back(mp(arr[2],1));
    a_change(1,1,1,n,1,arr[2]);

    for (ll i=2;i<=n;i++){
        ll left=2,right=i,mid=(left+right)/2;
        while(left<right){
            mid=(left+right)/2;
            if (pre[i] - pre[mid-1] > m) left=mid+1;
            else right=mid;
        }
        
        dp[i] = query(left-1,i-1,1,n,1);
        
        int posinmx = lower_bound(mx.begin(),mx.end(),mp(arr[i+1],1e9),greater<pii>()) - mx.begin();
        int pos = mx [posinmx] .second;
        
        if (posinmx!=(int)mx.size()){
            a_change(pos,i,1,n,1,arr[i+1]);
            while(1){
                if (mx.empty()) break;
                if (mx.back().second>=pos) mx.pop_back();
                else break;
            }
            mx.push_back(mp(arr[i+1],pos));
        }else{ // 是目前最小的
            a_change(i,i,1,n,1,arr[i+1]);
            mx.push_back(mp(arr[i+1],i));
        }
        
    }

    cout<<dp[n]<<endl;
}
:::