# 累積和の前提
累積和をあらかじめ計算しておくと配列の特定の範囲の合計をすぐに求められるようになる
→値を途中で変更する場合などは累積和を計算し直す必要が出てきて逆に遅い
(BITなどで処理するらしい)
> 参考　https://algo-logic.info/binary-indexed-tree/

cf)
上記のような問題で質問の間でデータに集計漏れがあってi日目にはAi+A'i人が実は来場してました...みたいな時は累積和いちいち出してたら遅い

# 2.4 二次元累積和(２)

前回学習した(2.2節)いもす法の二次元ver
> 鉄則本輪読会第三回：　https://hackmd.io/@ZuzmC9jbTWexkh9-DVYybQ/HyxQDiHuh

マス(2,2)を左上としてマス(4,4)を右下とする長方形領域の積雪を1cm増やすことを考えると
マス(2,2)及びマス(5,5)の値を+1し、マス(2,5)及びます(5,2)の値を-1し、縦横累積和を取ると求まる。
分かりづらく感じた人は下のサイトで試してみて
> 二次元いもす法が視覚的にわかる　https://siv3d.jp/web/sample/2d-imos/2d-imos.html

# 入力
H, W, N = map(int, input().split())
A = [ None ] * N
B = [ None ] * N
C = [ None ] * N
D = [ None ] * N
X = [ None ] * (W)
for t in range(N):
	A[t], B[t], C[t], D[t] = map(int, input().split())
    
# 各日について加算
X = [ [ 0 ] * (W + 2) for i in range(H + 2) ]
Z = [ [ 0 ] * (W + 2) for i in range(H + 2) ]
for t in range(N):
    X[A[t]][B[t]] += 1
    X[A[t]][D[t]+1] -= 1
    X[C[t]+1][B[t]] -= 1
    X[C[t]+1][D[t]+1] += 1   

先の例においてマス(2,2)を左上としてマス(4,4)を右下とする長方形領域の積雪を1cm増やすことを考えた時、(5,5)を+1したように本来の求める領域より大きい枠（xにおいて配列の大きさが(w+2) * (H+2)になっている）を用意してあげる

脱線）inputとinput = sys.stdin.readline
ただ単に
`N = int(input())`
とするより

import sys
input = sys.stdin.readline

N = int(input())

とするほうが10の6乗回inputするとき0.3秒ほど早くなるらしい
> 参考:https://www.kumilog.net/entry/python-speed-comp#%E6%A8%99%E6%BA%96%E5%85%A5%E5%8A%9B

# 2.5 チャレンジ問題
N個の部屋をd日で全探索すると計算量がO(ND)となり間に合わない
L号室からR号室を除いた部屋が使える時最も大きい部屋は
max{1から(L-1)号室の最大人数,(R+1)からN号室の最大人数}でもとまる