結果

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

ソースコード

diff # 

import sys

# Standard library sort for suffixes is too slow for N=2e5.
# A proper SA-IS or O(N log N) suffix sorting algorithm would be needed in C++.
# For Python, this part will be very slow.
def get_suffix_array(s):
    n = len(s)
    suffixes = sorted([(s[i:], i) for i in range(n)])
    sa = [item[1] for item in suffixes]
    return sa

def get_lcp_array(s, sa):
    n = len(s)
    pos = [0] * n
    for i in range(n):
        pos[sa[i]] = i
    
    lcp = [0] * n  # lcp[k] = LCP of S[sa[k-1]:] and S[sa[k]:]
    k = 0 # current LCP length
    for i in range(n): # iterate through suffixes S[i:] in original order
        if pos[i] == n - 1: # S[i:] is the last suffix in sorted order
            k = 0
            continue
        
        # j is the starting index of the suffix following S[i:] in sorted order
        j = sa[pos[i] + 1] 
        
        while i + k < n and j + k < n and s[i+k] == s[j+k]:
            k += 1
        
        lcp[pos[i] + 1] = k # Store LCP for S[i:]'s rank
        
        if k > 0:
            k -= 1
    return lcp

class RMQ:
    def __init__(self, arr):
        self.n = len(arr)
        if self.n == 0: return

        self.log_table = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.log_table[i] = self.log_table[i // 2] + 1
        
        self.max_log = self.log_table[self.n]
        self.st = [[0] * self.n for _ in range(self.max_log + 1)]
        
        for i in range(self.n):
            self.st[0][i] = arr[i]
            
        for k in range(1, self.max_log + 1):
            for i in range(self.n - (1 << k) + 1):
                self.st[k][i] = min(self.st[k-1][i], self.st[k-1][i + (1 << (k-1))])

    def query(self, l, r): # Range [l, r] inclusive
        if l > r or self.n == 0:
            return float('inf') # Or an appropriate large value indicating no LCP
        
        length = r - l + 1
        k = self.log_table[length]
        return min(self.st[k][l], self.st[k][r - (1 << k) + 1])

def solve():
    N, Q = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().strip()

    sa = get_suffix_array(S)
    pos = [0] * N
    for i in range(N):
        pos[sa[i]] = i
    
    lcp_arr = get_lcp_array(S, sa) # lcp_arr[k] is LCP(sa[k-1], sa[k])
    
    # For LCP between S[idx1:] and S[idx2:], query min on lcp_arr
    # in range [min(pos[idx1],pos[idx2])+1, max(pos[idx1],pos[idx2])]
    rmq_lcp = RMQ(lcp_arr)

    def get_lcp_of_suffixes(idx1, idx2):
        if idx1 == idx2:
            return N - idx1
        
        rank1, rank2 = pos[idx1], pos[idx2]
        if rank1 > rank2:
            rank1, rank2 = rank2, rank1
        
        # Query lcp_arr from rank1+1 to rank2
        # rmq_lcp.query(0,0) would be lcp_arr[0], which is typically dummy (or lcp_arr[1])
        # If lcp_arr index matches rank: query [rank1+1, rank2]
        res = rmq_lcp.query(rank1 + 1, rank2)
        return N if res == float('inf') else res


    query_results = []
    for _ in range(Q):
        Lk, Rk = map(int, sys.stdin.readline().split())
        P_idx_orig = Lk - 1 # 0-indexed start of P in S
        P_len = Rk - Lk + 1

        current_total_smaller = 0
        for i in range(N): # Suffix S[i:]
            S_suf_len = N - i
            
            # LCP of S[i:] and P
            lcp_s_i_vs_s_P_idx = get_lcp_of_suffixes(i, P_idx_orig)
            lcp = min(lcp_s_i_vs_s_P_idx, P_len)
            # lcp is now LCP(S[i:], P)

            # Determine relationship S[i:] vs P
            cmp_res = 0 # 0: S[i:] == P, -1: S[i:] < P, 1: S[i:] > P
            
            is_S_i_prefix_of_P_or_eq = (lcp == S_suf_len)
            is_P_prefix_of_S_i_or_eq = (lcp == P_len)

            if is_S_i_prefix_of_P_or_eq and is_P_prefix_of_S_i_or_eq: # S[i:] == P
                cmp_res = 0
            elif is_S_i_prefix_of_P_or_eq: # S[i:] is proper prefix of P
                cmp_res = -1
            elif is_P_prefix_of_S_i_or_eq: # P is proper prefix of S[i:]
                cmp_res = 1
            else: # They differ at char lcp-th (0-indexed)
                  # S[i+lcp] vs S[P_idx_orig+lcp]
                if S[i+lcp] < S[P_idx_orig+lcp]:
                    cmp_res = -1
                else:
                    cmp_res = 1
            
            contribution = 0
            if cmp_res == 0: # S[i:] == P
                contribution = P_len - 1
            elif cmp_res == -1: # S[i:] < P
                contribution = S_suf_len
            else: # cmp_res == 1, S[i:] > P
                if is_P_prefix_of_S_i_or_eq : # P is proper prefix of S[i:]
                    contribution = P_len - 1
                else: # S[i...i+lcp-1] == P[0...lcp-1] and S[i+lcp] > P[P_idx_orig+lcp]
                      # prefixes of P of length up to lcp are smaller
                    contribution = lcp
            
            current_total_smaller += contribution
        query_results.append(current_total_smaller)

    sys.stdout.write('\n'.join(map(str, query_results)) + '\n')

solve()
0