题解 CF833B 【The Bakery】

Jμdge

2019-10-29 10:11:56

Solution

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]); } ```