线段树 分成几 段和最大

题目传送

#include<cstdio>
#include<algorithm>
#include<cstring>
#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);//左孩子   l,m,rt<<1
    build(rson);// 右孩子  rt<<1|1
}
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]);
}

//update(pre[j],j-1,1,0,n,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\n",f[n]);
    return 0;
}