結果

問題 No.2361 Many String Compare Queries
ユーザー qwewe
提出日時 2025-04-24 12:29:34
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,647 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 848,912 KB
最終ジャッジ日時 2025-04-24 12:31:09
合計ジャッジ時間 2,784 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import log2, floor

def main():
    sys.setrecursionlimit(1 << 25)
    N, Q = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().strip()
    queries = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

    # Suffix Array Construction
    sa = list(range(N))
    sa.sort(key=lambda i: S[i:])
    rank = [0] * N
    for i in range(N):
        rank[sa[i]] = i
    k = 1
    tmp = [0] * N
    while k <= N:
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < N else -1))
        tmp[sa[0]] = 0
        for i in range(1, N):
            tmp[sa[i]] = tmp[sa[i-1]]
            if (rank[sa[i]] != rank[sa[i-1]] or
                (sa[i]+k < N and sa[i-1]+k < N and rank[sa[i]+k] != rank[sa[i-1]+k]) or
                (sa[i]+k >= N and sa[i-1]+k < N) or (sa[i]+k < N and sa[i-1]+k >= N)):
                tmp[sa[i]] += 1
        rank, tmp = tmp, rank
        k <<= 1

    # LCP Array Construction using Kasai's algorithm
    lcp = [0] * N
    h = 0
    for i in range(N):
        if rank[i] == 0:
            continue
        j = sa[rank[i] - 1]
        while j + h < N and i + h < N and S[j+h] == S[i+h]:
            h += 1
        lcp[rank[i]] = h
        if h > 0:
            h -= 1

    # Sparse Table for LCP array
    LOG = floor(log2(N)) + 1 if N > 0 else 0
    st = [[0] * N for _ in range(LOG)]
    st[0] = lcp[:]
    for k in range(1, LOG):
        for i in range(N - (1 << k) + 1):
            st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))])

    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1

    def get_lcp(l, r):
        if l == r:
            return N - sa[l]
        if l > r:
            l, r = r, l
        k = log_table[r - l]
        return min(st[k][l+1], st[k][r - (1 << k) + 1])

    def compute_lcp(i, j):
        if i == j:
            return N - i
        ri = rank[i]
        rj = rank[j]
        return get_lcp(ri, rj)

    for L, R in queries:
        L -= 1
        R -= 1
        len_T = R - L + 1
        K = len_T - 1
        total = 0

        # Part B: sum of min(lcp(i, L), K)
        # Part A: sum of (N - i - l + 1) where l = lcp(i, L) < len_T and S[i + l] < S[L + l]
        partB = 0
        partA = 0

        # Precompute all lcp(i, L)
        lcp_i_list = []
        for i in range(N):
            l = compute_lcp(i, L)
            lcp_i = min(l, K)
            partB += lcp_i
            if l < len_T and i + l < N and L + l <= R and S[i + l] < S[L + l]:
                partA += (N - (i + l))
        total = partB + partA
        print(total)

if __name__ == "__main__":
    main()
0