PAST4L
from 第四回 アルゴリズム実技検定
PAST4L
L - マンションの改築
考えたこと
奇数、偶数、1点、のいずれかに加算をして、隣接する値の一致するものの数を毎回答える
クエリが10^5なので、クエリあたりは定数かlog
1点変更はまあいいとして奇数が問題
偶数番ひく奇数番の差分で持っておけば単なるRange Add
Range Addして全体のなかから0のものの個数を探す？？
Range Addしないで-xのものを探せばいい
頻度表を配列で持てるなら定数オーダー
10^9なので無理
ハッシュでいける？
点更新の時どうする？
逆算する
AC
code:python
def main():
N, Q = map(int, input().split())
HS = list(map(int, input().split()))
from collections import defaultdict
freq = defaultdict(int)
for i in range(N - 1):
d = HSi - HSi + 1 # odd - even
if i & 1:
d = -d
freqd += 1
odd_height = 0
for _q in range(Q):
q = list(map(int, input().split()))
if q0 == 1:
odd_height += q1
print(freq-odd_height)
elif q0 == 2:
odd_height -= q1
print(freq-odd_height)
else:
i = q1 - 1
add = q2
if i > 0:
d = HSi - HSi - 1
if i & 1:
d = -d
freqd -= 1
if i < N - 1:
d = HSi - HSi + 1
if i & 1:
d = -d
freqd -= 1
HSi += add
if i > 0:
d = HSi - HSi - 1
if i & 1:
d = -d
freqd += 1
if i < N - 1:
d = HSi - HSi + 1
if i & 1:
d = -d
freqd += 1
print(freq-odd_height)
PAST1Hと似てる