题解 P2943 【[USACO09MAR]清理Cleaning Up】
_虹_
2019-12-30 15:56:03
这里是：**菜的真实**的O(nsqrtnlogn)做法
发现每个划分内部显然不能超过sqrtn种食物，否则还不如一个一个分开优。
所以对于i点，我们可以枚举i点为划分的右端点时的食物种类数x，显然x相同的源状态j，必然是连续的一段。
我们维护以i为划分右端点时，食物种类数量在哪些点发生变化，枚举前sqrtn段转移即可。
对于食物种类数相同的一段，转移取min，可以用线段树维护。
用了set，需要吸氧。
现在luogu氧气好像炸了，所以手开了O2。。。
~~编译需要c++11~~
```cpp
#pragma GCC optimize(2)
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
const int kmaxn=40000+5;
typedef long long ll;
const ll inf=1e15;
int lst[kmaxn];
int a[kmaxn];
int n,m;
struct node{
int l,r;
ll v=inf;
};
node T[kmaxn<<2];
#define LS (ls(p))
#define RS (rs(p))
#define LEAF (T[p].l==T[p].r)
#define TARGET (T[p].l==l&&T[p].r==r)
#define UPD upd(p)
#define CALMID int mid=((T[p].l+T[p].r)>>1)
inline int ls(int i){return i<<1;}
inline int rs(int i){return ls(i)|1;}
inline void upd(int p)
{
if(LEAF)return;
T[p].v=min(T[LS].v,T[RS].v);
}
void build(int l,int r,int p){
T[p].l=l;T[p].r=r;
if(LEAF)return;
CALMID;
build(l,mid,LS);
build(mid+1,r,RS);
}
ll qry(int l,int r,int p)
{
if(TARGET)
return T[p].v;
CALMID;
if(r<=mid)return qry(l,r,LS);
else if(l>mid)return qry(l,r,RS);
else{
return min(qry(l,mid,LS),
qry(mid+1,r,RS));
}
}
void ins(int k,ll v,int p)
{
if(LEAF){
T[p].v=v;
return;
}
CALMID;
if(k<=mid)ins(k,v,LS);
else ins(k,v,RS);
UPD;
}
int srt;
set<int,greater<int> > st;
void solve(int p)
{
int cnt=1;
auto itr=st.begin();
int ls=p;
ll ans=p*p;
++itr;
while(cnt<=srt && itr!=st.end())
{
ans=min(ans,qry((*itr),ls,1)+cnt*cnt);
ls=*itr;
++cnt;
++itr;
}
ins(p,ans,1);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
build(0,n,1);
ins(0,0,1);
srt=sqrt(n)+1;
st.insert(0);
for(int i=1;i<=n;++i)
{
if(lst[a[i]])
st.erase(lst[a[i]]);
lst[a[i]]=i;
st.insert(i);
solve(i);
}
cout<<qry(n,n,1)<<endl;
return 0;
}
```