CSP-S T2：考场的奇怪思路该如何优化?

（考场上压根没想到回文串这回事qwq

思路：为所有最近的相同字符之间连线，如果连线交叉，说明无法消除。

例:abab，1-3连线与2-4连线交叉，无法消除

做法:

先预处理出每一个字符的前一个同类las[]和后一个同类nex[]的下标，若没有则分别为-1和n

然后枚举每一个字串(a,b)：

1.找las和nex都在(a,b)外的字符，找到则返回假，计算每种字符的数量，为奇数则返回假

2.遍历(a,b)中vis[i]==0的i

a.遍历(a,i-1)，如果las[j]<a && i<nex[j]<nex[i]

说明i-nex[i]的连线被一条i前的点与i,nex[i]中间的点的连线交叉，无法消除，返回假

b.遍历(i+1,nex[i]-1)，如果las[j]<i && nex[j]>nex[i]

说明i-nex[i]的连线被中间一个点往外的连线交叉，无法消除，返回假

注：只需考虑nex[i]前面的点

c.vis[i]=vis[nex[i]]=1

3.结束，返回真

最后把每一个字串的返回值累加输出

这样做可以过考场给的3个样例，但时间复杂度爆表连800的样例都过不去

因此求助各位大佬优化思路,感谢)orz