【题意】n个数字分成k段，每一段的价值是段内不同数字的个数，求最大价值。n<=35000,k<=50。
【算法】分治决策单调+主席树（可持久化线段树）
【题解】
f[i][j]表示前i天分成j段的最大价值。
f[i][j]=max(f[k][j-1]+work(k+1,i))，j-1<=k<i。
首先打表发现有决策单调性（把j提到第一维）。
然后有经典写法：主席树维护区间不同数字个数。
那么根据决策单调性进行分治，在每次l,r（mid=l+r>>1）从L,R中转移时，用主席树求R~mid，然后从右到左每个位置若nex>mid则sum++，统计答案。
这样每个分治区域使用一次主席树，共有至多4*n次分治（类比线段树节点数），这样主席树的复杂度和分治并列，复杂度可以满足。
复杂度O(k*n log n+4*n log n)。
主席树空间注意不要自信预估……开大两倍。
#include<cstdio> #include<algorithm> #include<cstring> #include<cctype> using namespace std; const int maxn=35010,maxk=60; int f[2][maxn],sz,tot,root[maxn],nex[maxn],last[maxn],x,n,kind,a[maxn],b[maxn],c[maxn]; struct tree{int l,r,sum;}t[600010]; inline int min(int a,int b){return a<b?a:b;} inline int max(int a,int b){return a>b?a:b;} int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } void build(int l,int r,int &x,int y,int c){ x=++sz; t[x]=t[y];t[x].sum++; if(l==r)return; int mid=(l+r)>>1; if(c<=mid)build(l,mid,t[x].l,t[y].l,c); else build(mid+1,r,t[x].r,t[y].r,c); } int ask(int l,int r,int x,int c){ if(x==0)return 0; if(r<=c)return t[x].sum; int mid=(l+r)>>1,ans=0; if(c>mid)ans+=ask(mid+1,r,t[x].r,c); ans+=ask(l,mid,t[x].l,c); return ans; } int calc(int l,int r) {return ask(0,n,root[r],l-1)-ask(0,n,root[l-1],l-1);} void find(int l,int r,int L,int R){ if(l>r||L>R)return; int mid=(l+r)>>1,sum=calc(min(R+1,mid),mid); int wh=0; for(int i=min(R,mid-1);i>=L;i--){ if(f[x][mid]<f[1-x][i]+sum){ f[x][mid]=f[1-x][i]+sum; wh=i; } if(nex[i]>mid)sum++; } find(l,mid-1,L,wh); find(mid+1,r,wh,R); } int main(){ n=read();kind=read(); for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; sort(b+1,b+n+1);tot=n; tot=unique(b+1,b+tot+1)-b-1; for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot+1,a[i])-b; for(int i=1;i<=n;i++){ last[i]=c[a[i]]; c[a[i]]=i; } memset(c,0,sizeof(c)); for(int i=n;i>=1;i--){ nex[i]=c[a[i]]==0?n+1:c[a[i]]; c[a[i]]=i; } for(int i=1;i<=n;i++)build(0,n,root[i],root[i-1],last[i]); x=0; memset(f[x],-1,sizeof(f[x])); f[x][0]=0; for(int j=1;j<=kind;j++){ x=1-x; memset(f[x],-1,sizeof(f[x])); find(0,n,0,n); } printf("%d",f[x][n]); return 0; }
另一种写法：线段树
DP的瓶颈主要在于work(k+1,i)部分，否则就可以线段树查询max了。
对于已有的k~i-1，加入新的数字i（i上一次出现的位置为p），只有左端点p+1及之后的点才会+1，这就是个区间加操作。
那么每次区间加和区间查，j作为第一维换的时候重建树。