結果

問題 No.2758 RDQ
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-12 16:16:12
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 355 ms / 2,000 ms
+ 104µs
コード長 2,698 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 231 ms
コンパイル使用メモリ 95,856 KB
実行使用メモリ 104,128 KB
最終ジャッジ日時 2026-07-12 16:16:21
合計ジャッジ時間 7,466 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2758

import math

def main():
    N, Q = map(int, input().split())
    A = list(map(int ,input().split()))
    lrk = []
    for _ in range(Q):
        l, r, k = map(int, input().split())
        lrk.append((l - 1, r - 1, k))
    
    # 平方分割を応用して解く
    max_a = max(A)
    sqrt_a = int(math.sqrt(max_a))
    
    sqrt_n = int(math.sqrt(N))
    bin_length = (N // sqrt_n) + (1 if N % sqrt_n > 0 else 0)
    small_k_bin_list = [{} for _ in range(bin_length)]
    for i in range(N):
        a = A[i]
        index = i // sqrt_n
        bin_map = small_k_bin_list[index]
        for k in range(1, sqrt_a + 1):
            if a % k == 0:
                if k not in bin_map:
                    bin_map[k] = 0
                bin_map[k] += 1

    queries = []
    for i in range(Q):
        l, r, k = lrk[i]
        l_index = l // sqrt_n
        queries.append((l_index, r, l, k, i))
    queries.sort(key=lambda x : x[0] * (2 * N) - x[1])

    large_k_bin_list= [0] * (max_a + 1)
    for a in A:
        large_k_bin_list[a] += 1

    def add(i):
        a = A[i]
        large_k_bin_list[a] += 1
    
    def delete(i):
        a = A[i]
        large_k_bin_list[a] -= 1

    left = 0
    right = N - 1
    answers = [0] * Q
    for l_index, r, l, k, index in queries:
        while left < l:
            delete(left)
            left += 1
        while l < left:
            left -= 1
            add(left)
        while r < right:
            delete(right)
            right -= 1
        while right < r:
            right += 1
            add(right)

        if k <= sqrt_a:
            r_index = r // sqrt_n
            answer = 0
            if l_index == r_index:
                for i in range(l, r + 1):
                    a = A[i]
                    if a % k == 0:    
                        answer += 1
            else:
                for i in range(l, sqrt_n * (1 + l_index)):
                    a = A[i]
                    if a % k == 0:    
                        answer += 1
                for i in range(r_index * sqrt_n, r + 1):
                    a = A[i]
                    if a % k == 0:    
                        answer += 1
                
                for i in range(l_index + 1, r_index):
                    if k in small_k_bin_list[i]:
                        answer += small_k_bin_list[i][k]
        else:
            x = k
            answer = 0
            while x <= max_a:
                answer += large_k_bin_list[x]
                x += k
        answers[index] = answer
    
    for i in range(Q):
        print(answers[i])
        




    

















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