[DP 의사 결정 단조로운 분할] Codeforces 868F.Yet Another Minimization Problem

DP 명령fi, j는 처음 i개의 수를 j개의 구간으로 나누는 최소 대가를 나타낸다
그럼fi,k=min{fj,k+cost(j+1,i)} 이 물건은 이전에 CF833B처럼 라인 트리로 유지할 수 있는 방법이 너무 보고 싶어요.
그러나cost()=∑ai∗(ai-3-1)2로 인해 이 물건은 선단수로 유지하기 어려워 이렇게 할 수 없다
그러나 g(i)=fi, k와 h(i)=cost(i, j)라는 두 함수는 철 함수이기 때문에 결정이 단조로울 가능성이 높다.
그럼 대대적으로 분치할 수 있어.
그리고 분치할 때 코스트()라는 걸 처리해야 해.
가령 이전된 구간이 [L, R]이고 이전된 구간이 [l, r]라고 가정한다면 우리는 다음 층으로 돌아가기 전에 [L, l-3] 의cost()를 처리해야 복잡도를 확보할 수 있다.
O(nklogn)

#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N=100010;

int n,k,tms,a[N];
ll f[25][N];
int b[N],t[N];

inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void rea(int &x){
    char c=nc(); x=0;
    for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

void solve(int l,int r,int L,int R,int K,ll cur){
    if(L>R) return ;
    int mid=L+R>>1,p;
    for(int i=L;i<=mid;i++) cur+=b[a[i]]++;
    for(int i=l;i<=r && i<=mid;i++){
        cur-=--b[a[i]];
        if(f[K-1][i]+cur1][i]+cur,p=i;
    }
    for(int i=L;i<=mid;i++) cur-=--b[a[i]];
    for(int i=l;i<=r && i<=mid;i++) cur+=b[a[i]]++;
    solve(l,p,L,mid-1,K,cur);
    for(int i=l;i
for(int i=L;i<=mid;i++) cur+=b[a[i]]++;
    solve(p,r,mid+1,R,K,cur);
    for(int i=l;i
for(int i=L;i<=mid;i++) b[a[i]]--;
}

int main(){
    rea(n); rea(k);
    for(int i=1;i<=n;i++) rea(a[i]);
    ll cur=0;
    for(int i=1;i<=n;i++){
        cur+=b[a[i]]++;
        f[1][i]=cur;
    }
    for(int i=2;i<=k;i++)
        for(int j=1;j<=n;j++) f[i][j]=1LL<<60;
    for(int i=2;i<=k;i++){
        for(int j=1;j<=n;j++) b[j]=0;
        solve(1,n,1,n,i,0);
    }
    cout<return 0;
}