Submission #74668256

---

Source Code Expand

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAXN = 500005;
const int MAXS = 2 * MAXN;

int n, a[MAXN];
int pir[MAXN];
bool f[MAXN];
int st[MAXN];

int nxt[MAXS][10];
int lik[MAXS];
int len[MAXS];
int tot = 1;

int insert(int lst, int c)
{
    if (nxt[lst][c] && len[nxt[lst][c]] == len[lst] + 1)
        return nxt[lst][c];
    int cur = ++tot;
    len[cur] = len[lst] + 1;
    int p = lst;
    while (p && !nxt[p][c])
    {
        nxt[p][c] = cur;
        p = lik[p];
    }
    if (!p)
        lik[cur] = 1;
    else
    {
        int q = nxt[p][c];
        if (len[p] + 1 == len[q])
            lik[cur] = q;
        else
        {
            ++tot;
            len[tot] = len[p] + 1;
            memcpy(nxt[tot], nxt[q], sizeof(nxt[q]));
            lik[tot] = lik[q];
            while (p && nxt[p][c] == q)
            {
                nxt[p][c] = tot;
                p = lik[p];
            }
            lik[q] = lik[cur] = tot;
        }
    }
    return cur;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int j = a[i];
        if (i + j - 1 > n)
        {
            f[i] = false;
            continue;
        }
        bool flag = true;
        for (int k = 0; k < j; k++)
        {
            if (a[i + k] != j)
            {
                flag = false;
                break;
            }
        }
        f[i] = flag;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!f[i])
            continue;
        int nxti = i + a[i];
        if (nxti <= n && f[nxti] && a[i] != a[nxti])
            pir[i] = nxti;
        else
            pir[i] = 0;
    }
    lik[1] = 0;
    len[1] = 0;
    for (int i = n; i >= 1; i--)
    {
        if (!f[i])
            continue;
        int lst = (pir[i] == 0) ? 1 : st[pir[i]];
        st[i] = insert(lst, a[i] - 1);
    }
    long long ans = 0;
    for (int i = 2; i <= tot; i++)
        ans += len[i] - len[lik[i]];
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result