有N头奶牛，每头那牛都有一个标号Pi，1 <= Pi <= M <= N <= 40000。 现在Farmer John要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有k个不同的数，那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和
这里的M貌似没什么用。
分成若干段是想分多少段就多少段。
首先需要发现这个问题。
如果在某段区间中，不同的数超过了sqrt(n)个， 那么很显然，我们还不如将整个区间分为n段。
那么我们就不用管区间不同数超过sqrt(n)的数了。
令数组b[j]表示 从b[j] + 1到i 不同的数的数量不超过j的最左端
也就是说a[b[j]] + 1]到 a[i]之间的数不超过j个
那么转移方程如下
f[i] = min(f [ b[j] ] + j * j, f[ i ] ) 1 <= j <= sqrt(n)
那么这个b[j]怎么维护呢
令c[j]表示从b[j]+1下标到i的区间中不同数的个数。
对于新加入的一个数.
如果该数之前出现的位置x 不大于b[j]，那么说明b[j] +1到i中不同数的数量要+1
然后计算完之后
可能有c[j] > j的，这显然是不应该的。
那么就要从区间头部删掉数使得c[j]不大于j。 并且要更新b[j]
这个过程实际上就是一个游标右移，直至游标左边去掉的某个数确实在游标右边不存在了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#define MAXN 111111
#define MAXM 211111
#define PI acos(-1.0)
#define eps 1e-8
#define INF 100000001
using namespace std;
int p[55555];
int a[55555], b[55555], c[55555], dp[55555];
int n, m, k;
int main()
{memset(dp, 0x3f, sizeof(dp));memset(p, -1, sizeof(p));scanf("%d%d", &n, &m);int k = (int)sqrt(n + 0.5);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);dp[0] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= k; j++)if(p[a[i]] <= b[j]) c[j]++;p[a[i]] = i;for(int j = 1; j <= k; j++)if(c[j] > j){int now = b[j] + 1;while(p[a[now]] > now) now++;b[j] = now;c[j]--;}for(int j = 1; j <= k; j++)dp[i] = min(dp[i], dp[b[j]] + j * j);}printf("%d\n", dp[n]);return 0;
}