线段树优化$dp$入门题。

要求把$n$个数分成$k$段，每段价值为里面不相同的数的个数，求所有段的价值之和最大值。$n\le 35000,k\le 50$

---

先考虑直接暴力$dp$，fj,if_{j,i}fj,i​表示把前$i$个分成$j$组的最优值。

显然fj,i=max⁡j−1≤k≤i−1{fj−1,k+W(k+1,i)}f_{j,i}=\max\limits_{j-1\le k\le i-1}\{f_{j-1,k}+W(k+1,i)\}fj,i​=j−1≤k≤i−1max​{

fj−1,k​+W(k+1,i)}

于是就有了一个O(n2k)O(n^2k)O(n2k)的做法。

现在考虑优化求fj,i+W(k+1,i)f_{j,i}+W(k+1,i)fj,i​+W(k+1,i)的做法。

我们考虑增量法，即枚举当前层的$i$的时候考虑coloricolor_icolori​对之前所有的$f$的贡献。

对于这种相同颜色只考虑一次贡献的题有这么一个固定的套路：我们记当前颜色上一次出现的位置为pre，则这个颜色会对[pre+1,i]或者[pre,i-1]这一段产生贡献。

对于这道题可以动态维护fj−1,k+W(k+1,j)f_{j-1,k}+W(k+1,j)fj−1,k​+W(k+1,j)这个值，因此我们最开始将fj−1,if_{j-1,i}fj−1,i​全部放到一棵线段树上面作为初始值，走到位置$i$时把[prei,i−1][pre_i,i-1][prei​,i−1]维护的值全部加$1$即可。

代码：

#include
    
     #define ri register intusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}const int N=35005,K=55;int tmp=0,a[N],f[2][N],n,k,pre[N],mp[N];namespace SGT{
    	#define lc (p<<1)	#define rc (p<<1|1)	#define mid (l+r>>1)	int mx[N<<2],add[N<<2];	inline void pushup(int p){
    mx[p]=max(mx[lc],mx[rc]);}	inline void pushnow(int p,int v){
    mx[p]+=v,add[p]+=v;}	inline void pushdown(int p){
    if(add[p])pushnow(lc,add[p]),pushnow(rc,add[p]),add[p]=0;}	inline void build(int p,int l,int r){
    		add[p]=0;		if(l==r){
    mx[p]=f[tmp^1][l];return;}		build(lc,l,mid),build(rc,mid+1,r),pushup(p);	}	inline void update(int p,int l,int r,int ql,int qr,int v){
    		if(ql>qr)return;		if(ql<=l&&r<=qr)return pushnow(p,v);		pushdown(p);		if(qr<=mid)update(lc,l,mid,ql,qr,v);		else if(ql>mid)update(rc,mid+1,r,ql,qr,v);		else update(lc,l,mid,ql,mid,v),update(rc,mid+1,r,mid+1,qr,v);		pushup(p);	}	inline int query(int p,int l,int r,int ql,int qr){
    		if(ql>qr)return -0x3f3f3f3f;		if(ql<=l&&r<=qr)return mx[p];		pushdown(p);		if(qr<=mid)return query(lc,l,mid,ql,qr);		if(ql>mid)return  query(rc,mid+1,r,ql,qr);		return max(query(lc,l,mid,ql,mid),query(rc,mid+1,r,mid+1,qr));	}	#undef lc	#undef rc	#undef mid}int main(){
    	n=read(),k=read();	memset(mp,-1,sizeof(mp));	for(ri i=1;i<=n;++i)a[i]=read(),pre[i]=mp[a[i]],mp[a[i]]=i;	memset(f[tmp],-0x3f,sizeof(f[tmp]));	f[tmp][0]=0;	for(ri tt=1;tt<=k;++tt){
    		tmp^=1;		memset(f[tmp],-0x3f,sizeof(f[tmp]));		SGT::build(1,0,n);		for(ri i=1;i<=n;++i){
    			SGT::update(1,0,n,pre[i],i-1,1);			f[tmp][i]=SGT::query(1,0,n,tt-1,i-1);		}	}	cout<