rt.

写的快吐了/fad

具体就是用线段树修改会 TLE，用 ST 表修改会 RE，而且之前把 这份代码 中的 ST 表板子粘过来提交还是 RE/fad

感觉可能是 $\mathit{rk}$ 数组写挂了？因为我在 query 函数中加了

++ L;
if (L > R) return 0;

就不是 RE 而是 WA 了

struct Sa {

    int sa[680000], rk[680000];
    int _rk[680000];

    int hgt[680000];
    int d[680000];

    int n, w;

    string s;
    int lg[680000];
    int f[680000][25];
    
    void Build () {
    	lg[0] = -1;
    	F(i, 1, n) lg[i] = lg[i >> 1] + 1;
    	F(i, 1, n) f[i][0] = hgt[i];
    	F(j, 1, 20) {
    		for (int i = 1; i + (1 << j) - 1 <= n; ++ i)
    			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    	}
    }
    
    int Query (int l, int r) {
    	int ln = lg[r - l + 1];
    	return min(f[l][ln], f[r - (1 << ln) + 1][ln]);
    }
    
    void SA() {

        F(i, 1, n << 1) sa[i] = 0, rk[i] = hgt[i] = _rk[i] = 0;
        F(i, 1, n << 3) d[i] = 0;
        F(i, 1, (n << 1)) s += ' ';

        F(i, 1, n) sa[i] = i, rk[i] = s[i] - 'a';

        for (w = 1; w < n; w <<= 1) {
            sort (sa + 1, sa + n + 1, [&] (int x, int y) {
                if (rk[x] == rk[y]) return rk[x + w] < rk[y + w];
                return rk[x] < rk[y];
            });

            F(i, 1, n) {
                _rk[i] = rk[i];
            }

            for (int i = 1, p = 0; i <= n; ++ i) {
                if (_rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w]) {
                    rk[sa[i]] = p;
                } else {
                    rk[sa[i]] = ++ p;
                }
            }

            // F(i,1,n)cout <<rk[i]<<' ';cout<<'\n';
            // F(i,1,n)cout<<sa[i]<<' ';cout<<'\n';
        }

        // F(i,1,n)cout<<sa[i]<<' ';cout<<'\n';

        for (int i = 1, k = 0; i <= n; ++ i) {
            if (rk[i] == 0) continue ;
            if (k) -- k;
            while (s[i + k] <= s[sa[rk[i] - 1] + k]) ++ k;
            hgt[rk[i]] = k;
            
        }
        // F(i,1,n)cout<<hgt[i]<<' ';cout<<'\n';
        Build();
    }

    int Q(int l, int r) {
        int L = rk[l], R = rk[r];
        if (L > R) swap(L, R);
        ++ L;
        if (L > R) return 0;
        return Query(L, R);
    }
}LCS, LCP;

int ans;

void Main() {
    ans = 0;
    cin >> n; LCS.n = LCP.n = n;
    LCS.s = LCP.s = " ";
    F(i, 1, n) {
        char c; cin >> c; LCP.s += c;
    }
    D(i, n, 1) {
        LCS.s += LCP.s[i];
    }
    LCP.SA();
    LCS.SA();

    F(L, 1, n) {
        for (int i = 1; i + L <= n; i += L) {
            ans = max(ans, (LCP.Q(i, i + L) + LCS.Q(n - i - L + 1, n - i + 1) + L - 1) / L);
        }
    }
    cout << ans << '\n';
}

部分代码，如果您需要完整代码我会贴的/bx