CF868F Yet Another Minimization Problem

2018-10-09 20:14:43

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N],cnt[N];
ll f[N],g[N];
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
void solve(int l,int r,int L,int R,ll sum)//求解区间[l,r],决策区间[L,R],花费sum
{
if (l>r) return;
int mid=(l+r)>>1,pos=min(mid,R),k=0;
for (reg int i=l;i<=mid;i++) sum+=(cnt[a[i]]++);
for (reg int i=L;i<=pos;i++) {sum-=(--cnt[a[i]]); if (g[mid]>f[i]+sum) g[mid]=f[i]+sum,k=i;}
for (reg int i=L;i<=pos;i++) sum+=(cnt[a[i]]++);
for (reg int i=l;i<=mid;i++) sum-=(--cnt[a[i]]);//还原
solve(l,mid-1,L,k,sum);
for (reg int i=l;i<=mid;i++) sum+=(cnt[a[i]]++);
for (reg int i=L;i<k;i++) sum-=(--cnt[a[i]]);
solve(mid+1,r,k,R,sum);
for (reg int i=L;i<k;i++) sum+=(cnt[a[i]]++);
for (reg int i=l;i<=mid;i++) sum-=(--cnt[a[i]]);
}
int main()
{
}