AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の64問目である「Uplift（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【064 – Uplift（★3）】
考察
今回、N,Q < 105なので、単純に毎回計算していたら、O(NQ)でTLEしてしまいます。
そこでQ回地殻変動に対し、O(1)で結果を出力する必要があります。
考えた内容の概要
- 不便さが変化するのは、L-1~L, R~R+1間のみ
- 事前に各地点での不便さを計算しておき、全体の不便さを計算しておく。
- L~R間で地殻変動が起こった場合、特定の手順で不便さを更新する。
考えたことの内容
- 事前計算: 各地点間の不便さを計算しておく。具体的には、隣接する地点間の標高の差を計算し、その絶対値を不便さとして格納する。
- 地殻変動の影響: 地殻変動が起こると、その影響を受ける区画の不便さだけが変わる。具体的には、L-1~L, R~R+1間の不便さが変わる。
- 不便さの更新: 地殻変動が起こった場合、まず地殻変動前の不便さを全体の不便さから引き、次に新しい不便さを計算して全体の不便さに足す。
実装した内容
- 入力を受け取る。
- 初期の不便さを計算する。
- 各地殻変動のクエリに対して、不便さの変化を計算する。
- 更新後の全体の不便さを出力する。
典型解法：事前に計算
コード
N, Q = map(int, input().split())
A = list(map(int, input().split()))
if N == 1:
for _ in range(Q): # Q回のクエリに対応するための出力が必要
print(0)
exit()
inconvenience = [0] * N#各地点での不便さを格納
for i in range(N - 1):
inconvenience[i] = A[i + 1] - A[i]
result = sum(map(abs, inconvenience))
for q in range(Q):
L, R, V = map(int, input().split())
L -= 1 # 0-based indexに調整
R -= 1
if L != 0:
result -= abs(inconvenience[L - 1])#地殻変動が起きたら、L-1~Lの不便さを引き、
inconvenience[L - 1] += V#新しい不便さに更新し
result += abs(inconvenience[L - 1])#それを合計の不便さに足す
if R < N - 1:
result -= abs(inconvenience[R])
inconvenience[R] -= V
result += abs(inconvenience[R])
print(result)
コメント