[CF][尺取][减少重复计算] codeforces 1043D Mysterious Crime

emmm第一感觉好像后缀数组之类的结构，但是这个每个元素是个整数，而字符串处理中每个元素都是一个长度为1的字符，，，所以很难把他等同于字符串来处理。但是直接理解的话，要求的话一定是找到一个排列，然后考虑他的每个子段，然后再在其他所有的排列中去找有没有这个子段，直接裸暴力的话n^3*10，肯定不行，但是想一下如果仅仅是考虑所有的子段就一定是不小于n^2的了，所以起码要在这里进行优化。然后由字符串的性质就可以知道一个长度为i的串如果满足要求的话，那么他的所有子串也都是满足要求的这些子串可以不用再计算了，发现了这个之后怎么去实施这个想法？考虑以每个下标i为开始的最长子串，这里如果用暴力的方法每次从i开始递增， 然后在与其他串判断，则当然仍然是n^3的，但是可以发现与其他串判断这个过程其实有很多重复的判断，假如已经知道了i到i+k个存在的话，判断第i+k+1个时候只需要把这一个数字去和其他的串中对应的数字比较是否全部相等就可以了，这样的话把复杂度降到了n^2*10，但是仍然不够，再考虑之前说的，枚举字段中的重复假设已经知道以i开始的到i+k个数字满足要求，那么在算以i+1开始的子段的时候，可以直接从第i+1+k+1个数字开始，也就是说中间的那些都不用再考虑了，因为这些信息已经在算第i个的时候计算过了。所需要保存的只有每个序列中数字i出现的位置而已。

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5;
typedef long long LL;

int pos[12][maxn],ori[12][maxn];
int n,m;
LL ans[maxn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>ori[i][j],pos[i][ori[i][j]]=j;
    int v1,vm,lm,flag;
    for(int i=1;i<=n;i++)
    {
        ans[i]=max(ans[i-1]-1,1LL);
        while(1)
        {
            flag=0;
            if(i+ans[i]>n)
                break;
            v1=ori[1][i];
            for(int j=2; j<=m; j++)
            {
                lm=pos[j][v1];
                if(lm+ans[i]>n||ori[j][lm+ans[i]]!=ori[1][i+ans[i]])
                {
                    flag=1;break;
                }
            }
            if(flag)
                break;
            ans[i]++;
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++)
        res+=ans[i];
    cout<<res;
    return 0;
}