問題
要約
長さNの数列A = (A1, ..., AN)が与えられる。
その後、Q個のクエリに答える必要があります。各クエリは以下の形式で与えられる
-
整数L, R, Xが与えられる。
-
数列AのL番目からR番目までの要素（AL, ..., AR）の中で、値がXに等しい要素の個数を求める。
- N: 数列Aの長さ
- A: 与えられる数列 (A1, ..., AN)
- Q: クエリの数
- L: 各クエリでの範囲の開始位置
- R: 各クエリでの範囲の終了位置
- X: 各クエリで探す値
既存投稿一覧ページへのリンク
アプローチ
累積和と二分探索を組み合わせてクエリを処理する
解法手順
-
入力を受け取る：
- 数列の長さNを読み込む
- 数列Aの要素を読み込む
-
累積和の準備：
- 各値の出現位置を記録する配列acmを作成する
- 数列Aを走査し、各要素の出現位置をacmに記録する
-
クエリ処理：
- クエリの数Qを読み込む
- 各クエリに対して以下の処理を行う：
a. L, R, Xを読み込む
b. Xの出現位置リストlstを取得する
c. 二分探索を使用して、L以上の最小のインデックスlを求める
d. 二分探索を使用して、R以下の最大のインデックスrを求める
e. r - lを計算し、結果を出力する
-
全てのクエリに対して3の処理を繰り返す
ACコード
ac.py
from bisect import bisect_left, bisect # 二分探索のためのモジュールをインポート
def io_func():
# 入力を受け取る関数
N = int(input()) # 数列の長さを読み込む
A = list(map(int, input().split())) # 数列Aの要素を読み込む
Q = int(input()) # クエリの数を読み込む
queries = [list(map(int, input().split())) for _ in range(Q)] # クエリを読み込む
return N, A, queries
def solve(N, A, queries):
# メインの処理を行う関数
acm = [[] for _ in range(N+1)] # 各値の出現位置を記録する配列を初期化
# 数列Aを走査し、各要素の出現位置をacmに記録
for i, a in enumerate(A, 1):
acm[a].append(i)
# 各クエリに対して処理を行う
for L, R, X in queries:
lst = acm[X] # Xの出現位置リストを取得
l = bisect_left(lst, L) # L以上の最小のインデックスを二分探索で求める
r = bisect(lst, R) # R以下の最大のインデックスを二分探索で求める
print(r - l) # 結果を出力
if __name__=="__main__":
# メイン処理
N, A, queries = io_func() # 入力を受け取る
solve(N, A, queries) # 解を求める
###
# N: 数列の長さ
# A: 入力された数列
# queries: クエリのリスト
# acm: 各値の出現位置を記録する配列
# L, R, X: 各クエリの左端、右端、探索する値
# lst: 特定の値Xの出現位置リスト
# l, r: 二分探索で求めた範囲内のインデックス
# 1. 入力処理（io_func関数）:
# - 数列の長さ、数列の要素、クエリの数とその内容を読み込む
# 2. メイン処理（solve関数）:
# a. 累積和の準備:
# - 各値の出現位置を記録する配列acmを作成
# b. クエリ処理:
# - 各クエリに対して、指定された値Xの出現回数を二分探索で効率的に計算
# - 結果を出力
# 3. メイン処理の呼び出し:
# - io_func関数で入力を受け取り、solve関数で解を求める
トレース
入力例
N = 11
A = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
queries = [(3,7,1)]
trace.py
# メインの処理を行う関数
acm = [[] for _ in range(N+1)] # 各値の出現位置を記録する配列を初期化
# [[], [], [], [], [], [], [], [], [], [], [], []]
# 数列Aを走査し、各要素の出現位置をacmに記録
for i, a in enumerate(A, 1):
acm[a].append(i)
# [[], [2, 4], [7], [1, 10], [3], [5, 9, 11], [8], [], [], [6], [], []]
# 各クエリに対して処理を行う
for L, R, X in queries:
# L=3, R=7, X=1
lst = acm[X] # Xの出現位置リストを取得
# [2, 4]
l = bisect_left(lst, L) # L以上の最小のインデックスを二分探索で求める
# l = bisect_left([2, 4], 3) = 1
r = bisect(lst, R) # R以下の最大のインデックスを二分探索で求める
# r = bisect_left([2, 4], 7) = 2
print(r - l) # 結果を出力
# 1