AC 代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,a[200010],c[200010];
int p[447][200000],cnt[200010];
int f[200010];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        c[i]=a[i];
    }
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(c+1,c+n+1,a[i])-c;
    m=sqrt(n);
    for(int i=1;i<=m;i++)
    {
        int r=0,ncnt=0;
        for(int j=1;j<=n;j++)
        {
            if(j>1)
            {
                cnt[a[j-1]]--;
                if(!cnt[a[j-1]])ncnt--;
            }
            while(r<n&&(cnt[a[r+1]]>0||ncnt<i))
            {
                r++,cnt[a[r]]++;
                if(cnt[a[r]]==1)ncnt++;
            }
            p[i][j-1]=r;
        }
        cnt[a[n]]--;
    }
    for(int i=1;i<=n;i++)f[i]=1e9;
    f[0]=0;
    for(int i=0;i<n;i++)
        for(int j=1;j<=m;j++)
            if(f[i]+j*j<f[p[j][i]])f[p[j][i]]=f[i]+j*j;
    printf("%d\n",f[n]);
    return 0;
}

TLE 代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,a[200010],c[200010];
int p[200000][447],cnt[200010];
int f[200010];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        c[i]=a[i];
    }
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(c+1,c+n+1,a[i])-c;
    m=sqrt(n);
    for(int i=1;i<=m;i++)
    {
        int r=0,ncnt=0;
        for(int j=1;j<=n;j++)
        {
            if(j>1)
            {
                cnt[a[j-1]]--;
                if(!cnt[a[j-1]])ncnt--;
            }
            while(r<n&&(cnt[a[r+1]]>0||ncnt<i))
            {
                r++,cnt[a[r]]++;
                if(cnt[a[r]]==1)ncnt++;
            }
            p[j-1][i]=r;
        }
        cnt[a[n]]--;
    }
    for(int i=1;i<=n;i++)f[i]=1e9;
    f[0]=0;
    for(int i=0;i<n;i++)
        for(int j=1;j<=m;j++)
            if(f[i]+j*j<f[p[i][j]])f[p[i][j]]=f[i]+j*j;
    printf("%d\n",f[n]);
    return 0;
}

两份代码的区别只有 $p$ 数组的两个维度交换了。有没有大佬来解释这是为什么？