题解 CF833B 【The Bakery】
Jμdge
2019-10-29 10:11:56
1 A 了
原因竟是做了类似的题: [ hdu 双倍不完全经验](http://acm.hdu.edu.cn/showproblem.php?pid=6070)
做法极其类似,只不过一个是二分一个是 dp
大概考虑一下这个数据范围,一看就是 nk 要的,然后 nk 之后好像还蛮富足(否则 n 就 1e5 了),那么大胆猜测还有个 log ,那么估计就是个 $n ~k\log n $ 的线段树优化 dp 了,事实上证明确实是这样
然后难点就是考虑一段中出现的**不同的**数的个数
这个可以对于每个点 i 记一下上次出现的位置 $p[i]$ ,然后线段树区间覆盖的时候覆盖 $p[i]$ ~ $i-1$ 就好了
其次都是小细节
# Code
大常数 Judge
```
//by Judge (zlw ak ioi)
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstring>
#include<iostream>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define db double
using namespace std;
const int M=1e5+3;
typedef int arr[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline T Max(T a,T b){return a>b?a:b;}
inline int read(){ int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} int n,k; arr a,p,f,las;
namespace SegT{ int t[M<<2],tag[M<<2];
#define ls k<<1
#define rs k<<1|1
#define len (r-l+1)
#define lson ls,l,mid
#define rson rs,mid+1,r
inline void Add(int k,int v){ tag[k]+=v,t[k]+=v; }
inline void Psd(int k){ if(!tag[k]) return ;
Add(ls,tag[k]),Add(rs,tag[k]),tag[k]=0;
}
void Bud(int k,int l,int r){ tag[k]=0;
if(l==r) return t[k]=f[l],void(); int mid=(l+r)>>1;
Bud(lson),Bud(rson),t[k]=Max(t[ls],t[rs]);
}
void Upd(int k,int l,int r,int L,int R){
if(L<=l&&r<=R) return Add(k,1),void();
if(l>R||L>r) return ; int mid=(l+r)>>1; Psd(k);
Upd(lson,L,R),Upd(rson,L,R),t[k]=Max(t[ls],t[rs]);
}
int Que(int k,int l,int r,int R){ int mid=(l+r)>>1;
if(l>R) return 0; if(r<=R) return t[k];
return Psd(k),Max(Que(lson,R),Que(rson,R));
}
} using namespace SegT;
int main(){ n=read(),k=read(); fp(i,1,n) las[i]=0;
fp(i,1,n) a[i]=read(),p[i]=las[a[i]],
f[i]=f[i-1]+!las[a[i]],las[a[i]]=i;
fp(i,2,k){ Bud(1,1,n);
fp(j,1,n) Upd(1,1,n,p[j],j-1),f[j]=Que(1,1,n,j);
} return !printf("%d\n",f[n]);
}
```