結果

問題 No.2361 Many String Compare Queries
ユーザー lam6er
提出日時 2025-03-26 15:55:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 6,790 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 563,744 KB
最終ジャッジ日時 2025-03-26 15:56:08
合計ジャッジ時間 4,944 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 2 MLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    Q = int(data[idx+1])
    idx +=2
    S = data[idx]
    idx +=1
    queries = []
    for _ in range(Q):
        L = int(data[idx])-1  # 0-based
        R = int(data[idx+1])-1
        queries.append( (L, R) )
        idx +=2
    # Suffix Automaton implementation
    class State:
        def __init__(self):
            self.next = {}
            self.link = -1
            self.len = 0
            self.cnt = 0  # number of occurrences
            self.sum_i = 0  # sum of starting indices
    sa = [State()]
    last = 0
    for i, c in enumerate(S):
        p = last
        curr = len(sa)
        sa.append(State())
        sa[curr].len = sa[p].len +1
        sa[curr].cnt = 1
        sa[curr].sum_i = i
        while p >=0 and c not in sa[p].next:
            sa[p].next[c] = curr
            p = sa[p].link
        if p == -1:
            sa[curr].link = 0
        else:
            q = sa[p].next[c]
            if sa[p].len +1 == sa[q].len:
                sa[curr].link = q
            else:
                clone = len(sa)
                sa.append(State())
                sa[clone].len = sa[p].len +1
                sa[clone].next = sa[q].next.copy()
                sa[clone].link = sa[q].link
                while p >=0 and sa[p].next[c] == q:
                    sa[p].next[c] = clone
                    p = sa[p].link
                sa[q].link = clone
                sa[curr].link = clone
        last = curr
    # Reverse the links to compute cnt and sum_i using topological sort
    V = len(sa)
    size = [0]*V
    sum_i = [0]*V
    states = sorted(range(V), key=lambda x: -sa[x].len)
    for v in states:
        if sa[v].link >=0:
            sa[sa[v].link].cnt += sa[v].cnt
            sa[sa[v].link].sum_i += sa[v].sum_i
    for v in range(V):
        size[v] = sa[v].cnt
        sum_i[v] = sa[v].sum_i
    # Precompute for each state, transitions sorted and cumulative counts
    from collections import defaultdict
    trans = [defaultdict(int) for _ in range(V)]
    for v in range(V):
        for c, to in sa[v].next.items():
            trans[v][c] = to
    # For each state, precompute sorted list of transitions
    sorted_trans = [ [] for _ in range(V) ]
    for v in range(V):
        sorted_c = sorted(trans[v].keys())
        sorted_trans[v] = sorted_c
    # Precompute prefix sums for transitions
    prefix_sum = [{} for _ in range(V)]
    for v in range(V):
        sorted_c = sorted_trans[v]
        cnt = 0
        sum_cnt = 0
        sum_total = 0
        sum_sum_i = 0
        temp = []
        for c in sorted_c:
            to = trans[v][c]
            cnt += size[to]
            sum_cnt += size[to]
            sum_total += size[to]
            sum_sum_i += sum_i[to]
            temp.append( (c, sum_cnt, sum_total, sum_sum_i) )
        prefix_sum[v] = temp
    # Process each query
    for L, R in queries:
        len_U = R - L +1
        if len_U ==0:
            print(0)
            continue
        U = S[L:R+1]
        current = 0
        cnt_condition2 = 0
        cnt_condition1 = 0
        states_m = []
        max_m = 0
        valid = True
        for m in range(len_U):
            c = U[m]
            if c not in trans[current]:
                valid = False
                break
            next_state = trans[current][c]
            states_m.append( (m+1, current, next_state) )
            current = next_state
            max_m = m+1
        if valid:
            states_m.append( (max_m+1, current, None) )
        else:
            pass
        # Compute condition2: sum of min(m_i, len_U-1)
        # where m_i is the length of the longest prefix of U starting at i
        # We need to find for each i, the maximum m where S[i..i+m-1] == U[0..m-1]
        # This is equivalent to the length of the longest prefix of U that is a substring starting at i
        # But computing this for all i is expensive, so we use the suffix automaton to track the prefixes
        # Track the states for each prefix of U
        prefix_states = []
        current =0
        for m in range(len_U):
            if m >= len(U):
                break
            c = U[m]
            if c not in sa[current].next:
                break
            current = sa[current].next[c]
            prefix_states.append( (m+1, current) )
        sum_condition2 =0
        for m, s in prefix_states:
            if m >= len_U:
                continue
            sum_condition2 += size[s]
        # Now, compute condition1
        sum_condition1 =0
        current_len =0
        current_node =0
        for k in range(len_U):
            if k >0:
                c = U[k-1]
                if c not in sa[current_node].next:
                    break
                current_node = sa[current_node].next[c]
                current_len +=1
            if current_len != k:
                break
            if k >= len_U:
                break
            next_char = U[k] if k < len_U else None
            if k < len_U-1:
                pass
            else:
                pass
            target_c = U[k] if k < len(U) else None
            if k >= len_U:
                break
            if current_node ==0 and current_len !=k:
                break
            # Find all transitions from current_node with c < target_c
            # Use the precomputed sorted transitions and prefix sums
            if target_c is None:
                continue
            sorted_c_list = sorted_trans[current_node]
            low =0
            high = len(sorted_c_list)
            left =0
            while low < high:
                mid = (low+high)//2
                if sorted_c_list[mid] < target_c:
                    low = mid +1
                else:
                    high = mid
            count_less = low
            if count_less ==0:
                continue
            # Get the sum of cnt and sum_i for transitions with c < target_c
            if count_less > len(prefix_sum[current_node]):
                sum_cnt = prefix_sum[current_node][-1][1] if prefix_sum[current_node] else 0
                sum_sum_i = prefix_sum[current_node][-1][3] if prefix_sum[current_node] else 0
            else:
                if count_less ==0:
                    sum_cnt =0
                    sum_sum_i =0
                else:
                    sum_cnt = prefix_sum[current_node][count_less-1][1]
                    sum_sum_i = prefix_sum[current_node][count_less-1][3]
            m = k+1
            term = (N - m +1) * sum_cnt - sum_sum_i
            sum_condition1 += max(term, 0)
        total = sum_condition1 + sum_condition2
        print(total)
if __name__ == '__main__':
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0