标签：pre CF833B int max tree 35001 Bakery news
#include<bits/stdc++.h>
using namespace std;
class tree{
public:
int f[51][35001];
int pre[35001];
int news[35001];
int max_tree[35000*4];
int lazy_tag[35000*4];
void build(int k,int l,int r,int i)
{
if(l==r)
{
max_tree[k]=f[i][l-1];
}
else
{
int mid=(l+r)>>1;
build(k<<1,l,mid,i);
build(k<<1|1,mid+1,r,i);
max_tree[k]=max(max_tree[k<<1],max_tree[k<<1|1]);
}
}
void push_down(int k)
{
lazy_tag[k<<1]+=lazy_tag[k];
lazy_tag[k<<1|1]+=lazy_tag[k];
max_tree[k<<1]+=lazy_tag[k];
max_tree[k<<1|1]+=lazy_tag[k];
lazy_tag[k]=0;
}
void update(int k,int l,int r,int x,int y,int p)
{
if(l>=x&&r<=y)
{
max_tree[k]+=p;
lazy_tag[k]+=p;
return;
}
int mid=(l+r)>>1;
push_down(k);
if(x<=mid)update(k<<1,l,mid,x,y,p);
if(y>mid)update(k<<1|1,mid+1,r,x,y,p);
max_tree[k]=max(max_tree[k<<1],max_tree[k<<1|1]);
}
int query(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return max_tree[k];
int mid=(l+r)>>1,res=-(1<<30);
push_down(k);
if(x<=mid)res=max(query(k<<1,l,mid,x,y),res);
if(y>mid)res=max(query(k<<1|1,mid+1,r,x,y),res);
return res;
}
int n,m;
int work()
{
memset(f,0,sizeof(f));
memset(pre,0,sizeof(pre));
memset(news,0,sizeof(news));
cin>>n>>m;
for(int i=1,x; i<=n; i++)
{
cin>>x;
pre[i]=news[x]+1;
news[x]=i;
}
for(int i=1; i<=m; i++)
{
memset(max_tree,0,sizeof(max_tree));
memset(lazy_tag,0,sizeof(lazy_tag));
build(1,1,n,i-1);
for(int j=1; j<=n; j++){
update(1,1,n,pre[j],j,1);
f[i][j]=query(1,1,n,1,j);
}
}
return f[m][n];
}
}x;
int main()
{
cout<<x.work();
}
标签：pre,
CF833B,
int,
max,
tree,
35001,
Bakery,
news
From： https://www.cnblogs.com/dadidididi/p/16750285.html