Add to all

2 secs 1024 MB

jmx3453

問題

提出

テストケース

解説

　クエリ $2$ を愚直に処理すると $O(N)$ となり，クエリ次第では計算量が $O(QN)$ となります．このままでは実行時間制限に間に合いません．

　そこで，変数 $X$ を定義し，クエリ $2$ の際は $X$ に $y_q$ を足すようにします．クエリ $3$ では $A_{x_q}+X$ を出力すれば良いです．

　よって，クエリ $1,2,3$ を全て $O(1)$ で処理することができ，本問題を $O(Q)$ で解くことができました．

実装例(python3)

N,Q = map(int,input().split())
A = list(map(int,input().split()))

#クエリ処理
X = 0
for i in range(Q):
  Query = list(map(int,input().split()))
  if Query[0] == 1:
    A[Query[1]-1] += Query[2]
  elif Query[0] == 2:
    X += Query[1]
  else:
    print(X + A[Query[1]-1])