Codeforces-834D The Bakery(세그먼트 트리 + dp)

전송문:Codeforces-834D
w(l, r)를 [l, r] 사이의 서로 다른 숫자의 개수로 설정하면 다음과 같다. f[i] [j]=max(f[k] [j-1] [j-1] + w(k+1, r] 사이의 서로 다른 숫자의 개수는 다음과 같다. f[i] [j]=max(f[k] [j][j-1] [j-1] [j-1]++ 1]+w(k1,i-1] 우리는 라인 트리를 구축하여 이를 유지보수할 수 있다. f[i] [i] [j] [j-1] [j-1]에 대한 라인 트리를 구축하고 f[[[[i] [j[i] [j[i] [j-1] [j[j-1]]]]]]]===Query(0, i-1)))] 사이의 서로 다른 숫자의 개수를 설정하면 다음과 같이 설정하면 k][j-1]가 올라가면 f[i][j]가 되어 매 수의 a[i]를 매거할 수 있고,last[a[i]]를 이 수에 지난번에 나타난 위치로 설정하면 [last[a[i], i-1] 이 구간을 모두 1로 추가합니다.

#include
#include
#include
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MX = 35000 + 5;
int n,m,pre[MX],now[MX];
int a[MX],f[MX],maxv[MX<<2],add[MX<<2];
void build(int l,int r,int rt){
    add[rt]=0;
    if(l==r){
        maxv[rt]=f[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void PushDown(int rt){
    if(add[rt]){
        maxv[rt<<1]+=add[rt];
        maxv[rt<<1|1]+=add[rt];
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        add[rt]=0;
    }
}
void PushUP(int rt){
    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&R>=r){
        maxv[rt]+=c;
        add[rt]+=c;
        return;
    }
    PushDown(rt);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
    PushUP(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r) return maxv[rt];
    PushDown(rt);
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m) ret=max(ret,query(L,R,lson));
    if(R>m) ret=max(ret,query(L,R,rson));
    PushUP(rt);
    return ret;
}
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        pre[i]=now[a[i]];
        now[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        build(0,n,1);
        for(int j=1;j<=n;j++){
            update(pre[j],j-1,1,0,n,1);
            f[j]=query(0,j-1,0,n,1);
        }
    }
    printf("%d
",f[n]);
    return 0;
}