[CF833B Round#426 Div.1]The Bakery--[세그먼트 트리+DP]

[원제] Some time ago Slastyona the Sweetmaid decided to open her own bakery!She bought required ingredients and a wonder-oven which can bake several types of cakes, and opened the bakery.
Soon the expenses started to overcome the income, so Slastyona decided to study the sweets market. She learned it’s profitable to pack cakes in boxes, and that the more distinct cake types a box contains (let’s denote this number as the value of the box), the higher price it has.
She needs to change the production technology! The problem is that the oven chooses the cake types on its own and Slastyona can’t affect it. However, she knows the types and order of n cakes the oven is going to bake today. Slastyona has to pack exactly k boxes with cakes today, and she has to put in each box several (at least one) cakes the oven produced one right after another (in other words, she has to put in a box a continuous segment of cakes).
Slastyona wants to maximize the total value of all boxes with cakes. Help her determine this maximum possible total value.
【제목번역】 길이가 n인 서열을 k단으로 나누어 총 가치가 가장 크다.
구간의 가치는 구간 내의 서로 다른 숫자의 개수를 나타낸다
n<=35000,k<=50
[입력 형식] 첫 번째 줄의 두 개 수 n, k의 두 번째 줄의 n 개 수는 이 서열을 나타낸다
S a m p l e    I n p u t Sample~~Input Sample  Input
4 1 1 2 2 1
S a m p l e    O u t p u t Sample~~Output Sample  Output
2
[제목 분석]
소박 dp 매우 생각 dp[i][j] 은 앞 i 개 가 j 단 으로 나뉘 는 최대 가치 를 표시 하 면 매거 단점 k
d p [ i ] [ j ] = max ⁡ ( d p [ i ] [ j ] , d p [ k ] [ j − 1 ] + p [ k + 1 ] [ i ] ) dp[i][j]=\max(dp[i][j],dp[k][j-1]+p[k+1][i]) dp[i][j]=max(dp[i][j],dp[k][j−1]+p[k+1][i])
그중p[i][j]은 i에서 j까지 몇 가지 색깔이 있음을 나타낸다.
이렇게 하면 분명히 별을 볼 수 있다. 우리는 이 max()가 라인 트리로 최적화할 수 있을 것 같다. 그러면 이p[i][j]는 어떻게 하지?
우리는 구간 최대치의 라인 트리를 만들고 각 점의 공헌을 고려한다. 이것은 단지 지난번에 출현한 위치에서 현재의 위치까지 단위의 공헌을 할 수 있을 뿐이다. 그러면 라인 트리로 할 수 있다.
매번 나무가 제로로 지어질 때마다 주의해라.
Code:

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 1 << 28
#define MAXN 100000
using namespace std;

int pos[MAXN], pre[MAXN], dp[MAXN][60], res, n, k; 

struct segtree {
    
    int tree[MAXN << 2], lazy[MAXN << 2];
    
    void clear () {
        memset (tree, 0, sizeof tree);
        memset (lazy, 0, sizeof lazy);
    }
    
    inline void pushup (int now) {
        tree[now] = max (tree[now << 1], tree[now << 1 | 1]);
    }
    
    inline void pushdown (int now, int l, int r) {
        if (lazy[now]) {
            int mid = l + r >> 1;
            tree[now << 1] += lazy[now];
            tree[now << 1 | 1] += lazy[now];
            lazy[now << 1] += lazy[now];
            lazy[now << 1 | 1] += lazy[now];
            lazy[now] = 0;
        }
    }
    
    void build (int now, int l, int r, int o) {
        if (l == r) {
            tree[now] = dp[l - 1][o];
            return;
        }
        int mid = l + r >> 1;
        build (now << 1, l, mid, o);
        build (now << 1 | 1, mid + 1, r, o);
        pushup (now);
    }
    
    void update (int now, int l, int r, int L, int R, int o) {
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            tree[now] += o, lazy[now] += o;
            return;
        }
        pushdown (now, l, r);
        int mid = l + r >> 1;
        update (now << 1, l, mid, L, R, o);
        update (now << 1 | 1, mid + 1, r, L, R, o);
        pushup (now);
    }
    
    void query (int now, int l, int r, int L, int R) {
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            res = max (res, tree[now]);
            return;
        }
        pushdown (now, l, r);
        int mid = l + r >> 1;
        query (now << 1, l, mid, L, R);
        query (now << 1 | 1, mid + 1, r, L, R);
    }
    
}tree;

int main () {
    scanf ("%d%d", &n, &k);
    for (register int i = 1; i <= n; i++) {
        int x; scanf ("%d", &x);
        pre[i] = pos[x], pos[x] = i;
    }
    for (register int i = 1; i <= k; i++) {
        tree.clear (), tree.build (1, 1, n, i - 1);
        for (register int j = 1; j <= n; j++) {
            tree.update (1, 1, n, pre[j] + 1, j, 1);
            res = -INF; tree.query (1, 1, n, 1, j);
            dp[j][i] = res;
        }
    }
    printf ("%d
", dp[n][k]);
    return 0;
}