貌似是第一套完整做完的省选题（太弱了）

T1：题意对于一列数，求对于每个1~i求有多少不同的子串。

容易想到可以用后缀数组求一个字符串有几个不同子串。

所以可以先将数组倒一下，然后求出sa，ht。

假设我们已求出i~n的答案，当我算i-1的时候，重复的子串显然就是（i-1)和i~n的中最大的LCP。

所以只要用树状数组维护rank，然后st表求LCP即可。

一开始 离散化写萎调了半天= =

#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 200010
#define ll long long
using namespace std;
int read(){
	int x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x;
}
int len,g[maxn],p[maxn];
void update1(int x)
{
	for (int i = x;i<=len;i += i&-i)
		g[i] = max(g[i],x);
}
void update2(int x)
{
	for (int i = x;i<=len;i += i&-i)
		p[i] = max(p[i],x);
}
int query1(int x)
{
	int y = 0;
	for (int i = x;i;i -= i&-i)
		y = max(y,g[i]);
	return y;
}
int query2(int x)
{
	int y = 0;
	for (int i = x;i;i -= i&-i)
		y = max(y,p[i]);
	return y;
}
int rk[maxn],ht[maxn],sa[maxn],c[maxn],s[maxn],gg[maxn],f[20][maxn],lg2[maxn],bin[20];
void getsa(int n,int m)
{
    int *x=rk,*y=ht;
	memset(c,0,sizeof(c));
	for (int i = 1;i <= n;i++) ++c[x[i]=s[i]];
	for (int i = 1;i <= m;i++) c[i] += c[i-1];
	for (int i = 1;i <= n;i++) sa[c[x[i]]--] = i;
    for (int k = 1;k < n;k<<=1)
	{
        int p=0;
    	for (int i = n-k+1;i <= n;i++) y[++p] = i;
    	for (int i = 1;i <= n;i++)
    		if (sa[i]>k) y[++p] = sa[i]-k;
    	memset(c,0,sizeof(c));
    	for (int i = 1;i <= n;i++) ++c[x[y[i]]];
    	for (int i = 1;i <= m;i++) c[i] += c[i-1];
    	for (int i = n;i >= 1;i--) sa[c[x[y[i]]]--] = y[i];
        swap(x,y);x[sa[1]]=p=1;
    	for (int i = 2;i <= n;i++)
	        x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
        if((m=p)>=n) break;
    }
}

void getht(int n)
{
    int p=0;
    for (int i = 1;i <= n;i++) rk[sa[i]] = i;
	for (int i = 1;i <= n;i++)
	{
        p?--p:0;
        if(rk[i]==1) continue;
        for(;(i+p<=n)&&(sa[rk[i]-1]+p<=n)&&(s[i+p]==s[sa[rk[i]-1]+p]);++p);
        ht[rk[i]]=p;
    }
}
int lcp(int x,int y){
	if (!x || x>len) return 0;
	if (x>y) swap(x,y); x++; int k=lg2[y-x+1];
	return min(f[k][x],f[k][y-bin[k]+1]);
}
int main()
{
	len=read();
	for (int i = len;i;i--)
		gg[i] = s[i] = read();
	sort(gg+1,gg+len+1);
	int cnt = unique(gg+1,gg+len+1)-gg-1;
	for (int i = 1;i <= len;i++)
		s[i] = lower_bound(gg+1,gg+cnt+1,s[i])-gg;
	getsa(len,cnt);getht(len);
	for (int i = 1;i <= len;i++)
		f[0][i] = ht[i];
	lg2[1]=0; bin[0]=1; bin[1]=2;
	for (int i=1; i<=16; i++)
	{
		bin[i+1]=(bin[i]<<1);
		for (int j=bin[i]; j<bin[i+1]; j++) lg2[j]=i;
		for (int j=1; j<=len; j++)
		{
			f[i][j]=f[i-1][j];
			if (j+bin[i-1]<=len) f[i][j]=min(f[i][j],f[i-1][j+bin[i-1]]);
		}
	}
	ll ans = 0;
	for (int i = len;i;i--)
	{
		ans += len-i+1;
		int l = query1(rk[i]-1),r = len-query2(len-rk[i])+1;
		ans -= max(lcp(l,rk[i]),lcp(r,rk[i])); 
		printf("%lld\n",ans);
		update1(rk[i]),update2(len-rk[i]+1);
	}
	return 0;
}

T2：这题只要会错排+逆元 谁都会做。

T3：求方差。

s=（Σxi^2）/m + E^2（E为平均数）

ms = (Σxi^2）+m*E^2

所以只要求(Σxi^2）最小就行。

f[i][j]表示第i天到j点的最小平方和。

f[i][j] = min(f[i-1][k]+(sum[j]-sum[k])^2);

这样是n^3的，题目要求n^2，显然就想到了斜率优化。

跟仓库建设没多大区别。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 1000000000
#define dy(x) (g[x]+sum[x]*sum[x]) 
#define dx(x) sum[x] 
using namespace std;

int f[3010],g[3010],sum[3010],a[3010],n,m,l,r,q[3010];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= n;i++)
		scanf("%d",&a[i]),sum[i] = sum[i-1]+a[i];
	for (int i = 1;i <= n;i++)
		g[i] = sum[i]*sum[i];
	for (int i = 2;i <= m;i++)
	{
		l = r = 1;
		for (int j = 1;j <= n;j++)
		{
			for (;l<r&&(dy(q[l+1])-dy(q[l]))<=2*sum[j]*(dx(q[l+1])-dx(q[l]));l++);
			f[j] = g[q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
			for (;l<r&&(dy(j)-dy(q[r]))*(dx(q[r])-dx(q[r-1]))<=(dy(q[r])-dy(q[r-1]))*(dx(j)-dx(q[r]));r--);
			q[++r] = j;
		}
		memcpy(g,f,sizeof(f));
	}
	printf("%d",f[n]*m-sum[n]*sum[n]);
	return 0;
}

这套题的难度还是有点低的，但zhl说他10分钟敲1道，还是得%一下的