Language: C++

//#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <atcoder/all>
using namespace atcoder;
//using mint = modint998244353;
//using mint = modint1000000007;
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//using i128 = __int128_t;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
constexpr char ln = '\n';
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
inline int topbit(int x) {return x == 0 ? -1 : 31-__builtin_clz(x);}
inline int topbit(long long x) {return x == 0 ? -1 : 63-__builtin_clzll(x);}
inline int botbit(int x) {return x == 0 ? 32 : __builtin_ctz(x);}
inline int botbit(long long x) {return x == 0 ? 64 : __builtin_ctzll(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
inline int kthbit(long long x, int k) {return (x>>k)&1;}
inline void print() {cout << "\n";}
template<class T>
inline void print(const vector<T> &v) {
    for (auto itr = v.begin(); itr != v.end(); ++itr) cout << *itr << " ";
    print();
}
template<class T, class... Args>
inline void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
#ifdef MINATO_LOCAL
#define dump(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
inline void debug() {cerr << endl;}
template<class T>
inline void debug(const vector<T> &v) {
    for (auto itr = v.begin(); itr != v.end(); ++itr) cerr << *itr << " ";
    debug();
}
template<class T, class... Args>
inline void debug(const T &x, const Args &... args) {
    cerr << x << " ";
    debug(args...);
}
#else
#define dump(x) void(0)
inline void debug() {}
template<class T> inline void debug(const vector<T> &v) {}
template<class T, class... Args> inline void debug(const T &x, const Args &... args) {}
#endif
struct Fast_ios {Fast_ios() {cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);};} fast_ios;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


struct SuffixArray {
    string s;
    vector<int> sa,rev;

    SuffixArray() {}
    SuffixArray(const string &S) : s(S) {
        int N = s.size();
        s.push_back('$');
        sa.resize(N+1);
        iota(sa.begin(),sa.end(),0);
        sort(sa.begin(),sa.end(),[&](int a,int b) {
            if(s[a]==s[b]) return a > b;
            return s[a] < s[b];
        });
        vector<int> cs(N+1,0),rs(N+1),cnt(N+1);
        for(int i = 0; i <= N; ++i) rs[i] = s[i];
        for(int len = 1; len <= N; len <<= 1) {
            for(int i = 0; i <= N; ++i) {
                cs[sa[i]] = i;
                if(i > 0 &&
                rs[sa[i-1]] == rs[sa[i]] &&
                sa[i-1]+len <= N &&
                rs[sa[i-1]+len/2] == rs[sa[i]+len/2]) cs[sa[i]] = cs[sa[i-1]];
            }
            iota(cnt.begin(),cnt.end(),0);
            copy(sa.begin(),sa.end(),rs.begin());
            for (int i = 0; i <= N; ++i) {
                int s1 = rs[i]-len;
                if (s1 >= 0) sa[cnt[cs[s1]]++]=s1;
            }
            cs.swap(rs);
        }
        rev.resize(N+1);
        for(int i = 0; i <= N; ++i) rev[sa[i]] = i;
    }
    int operator[](int i) const {return sa[i];}

    bool lt_substr(string &t,int si,int ti) {
        int sn=s.size(),tn=t.size();
        while(si < sn && ti < tn) {
            if(s[si] < t[ti]) return 1;
            if(s[si] > t[ti]) return 0;
            si++; ti++;
        }
        return si==sn&&ti<tn;
    }

    int lower_bound(string& t) {
        int l=0,r=s.size();
        while(l+1<r) {
            int m = (l+r)>>1;
            if(lt_substr(t,sa[m],0)) l = m;
            else r = m;
        }
        return r;
    }

    int upper_bound(string& t) {
        t.back()++;
        int res=lower_bound(t);
        t.back()--;
        return res;
    }

    // O(|T|*log|S|)
    int count(string& T) {
        return upper_bound(T)-lower_bound(T);
    }
};

struct LongestCommonPrefix {
    SuffixArray sa;

    vector<int> ht;
    vector<vector<int>> dat;
    LongestCommonPrefix(string &s):sa(s){
        int N = s.size();
        vector<int> lcp(N,0);

        int t = 0;
        lcp[0] = 0;
        for(int i = 0; i < N; ++i) {
            int j = sa[sa.rev[i]-1];
            if(t > 0) t--;
            for(; j+t < N && i+t < N; ++t) {
                if(sa.s[j+t] != sa.s[i+t]) break;
            }
            lcp[sa.rev[i]-1] = t;
        }

        int h = 1;
        while((1<<h)<N) h++;
        dat.assign(h,vector<int>(N));
        ht.assign(N+1,0);
        for(int j = 2; j <= N; ++j) ht[j] = ht[j>>1]+1;

        for(int j = 0; j < N; ++j) dat[0][j] = lcp[j];
        for(int i = 1, p = 1; i < h; ++i, p <<= 1)
        for(int j = 0; j < N; ++j)
            dat[i][j] = min(dat[i-1][j],dat[i-1][min(j+p,N-1)]);
    }

    // a, b are indices for suffix array
    int query(int a,int b) {
        assert(a != b);
        if(a > b) swap(a,b);
        int l = b-a;
        return min(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
    }

    // a, b are indices for string
    int lcp(int a,int b) {
        return query(sa.rev[a],sa.rev[b]);
    }
};

int main() {
    string S; cin >> S;
    ll N = S.size();
    LongestCommonPrefix LCP(S);
    ll ans = N*(N+1)/2;
    for (int i = 1; i < N; i++) ans -= LCP.query(i,i+1);
    cout << ans << ln; 
}


Compiler output:
a.cc:4:10: fatal error: atcoder/all: No such file or directory
    4 | #include <atcoder/all>
      |          ^~~~~~~~~~~~~
compilation terminated.