レベルアップ問題集Python3 クエリメニュー

<ソートと検索(query)>
step1　指定の位置への要素の追加
# utf-8
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(N)]

A.insert(K, Q)

for a in A:
    print(a)
'''
配列を用意して A の各要素を受け取ったのち、要素を追加するメソッドを利用したり、新たに長さ N + 1 の配列 B を作成し、A の要素と次のように対応させることで問題を解くことができます。
B_i = A_i (1 ≦ i ≦ K)
B_i = Q (i = K + 1)
B_i = A_{i-1} (K + 2 ≦ i ≦ N + 1)

リストの insert メソッドを使って解いています。
'''

step2　指定要素の検索
# utf-8
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

exist = False
for a in A:
    if a == K:
        exist = True
        break

print("YES" if exist else "NO")
'''
配列を用いてデータを受け取り、繰り返しを用いて、各要素について K かどうかを条件文で判定すれば良いです。
判定の結果に応じて "YES" または "NO" を出力しましょう。
for 文を使ってリストの各要素が K に一致するか判定しています。
'''

step3　指定要素の検索(query)
# utf-8
N, Q = map(int, input().split())
A = {int(input()) for _ in range(N)}

for _ in range(Q):
    k = int(input())
    if k in A:
        print("YES")
    else:
        print("NO")
'''
配列を用いてデータを受け取り、繰り返しを用いて、K_1 ... K_Q の各要素について A に存在するかどうかを条件文で判定することでも判定をおこなうことはできます。
しかし、そうした場合 K の要素 1 つを探すために A の要素を全て探索する必要があり、プログラム全体で Q × N 回ループを回す必要があります。
この問題の条件に注目すると 1 ≦ N , Q ≦ 100,000 とあるので、 Q × N は最大で 10,000,000,000 になり得ます。
これでは実行時間内に答えを出すことはできません。
この問題を解決するためには、計算量を意識してプログラムを書く必要があります。言語間で備わっているデータ構造が異なっているので一概にこれを使えば良いというのはないので、各言語ごとの実装例にて計算量改善の方法を参照してください。
この問題を解くためのデータ構造として、代表的なものとしては順序付き集合が挙げられます。
これは、値を常にソートされた状態で保持するデータ構造です。
順序付き集合に A の値を追加したのち、その中から K_i の値を検索することで、この問題を O(Q log N) で解くことができます。

set を使って解いています。
set はハッシュ法を用いて値を管理しているため、in 演算子による値の探索が平均 O(1) で実行できます。
'''

step4　先頭の要素の削除
# utf-8
N = int(input())
A = [int(input()) for _ in range(N)]

del A[0]

for a in A:
    print(a)
'''
配列を用意して A の各要素を受け取ったのち、要素を削除するメソッドを利用したり、新たに長さ N - 1 の配列 B を作成し、A の要素と次のように対応させることで問題を解くことができます。
B_i = A_{i+1} (1 ≦ i ≦ N - 1)
del 文を del list[削除したい要素のインデックス] のように使うことでリストのインデックスを指定して要素を削除することができます。
del 文を list オブジェクトに用いたときの計算量は O(N) です。
'''

step5　先頭の要素の削除(query)
# utf-8
from collections import deque

N, K = map(int, input().split())
A = deque([int(input()) for _ in range(N)])

f = 0
for _ in range(K):
    s = input()
    if s == "pop":
        A.popleft()
        continue
    for a in A:
        print(a)
'''
配列を用いてデータを受け取り、問題の指示に従って要素を削除・出力することでも判定をおこなうことはできます。
しかし、そうした場合 A の要素を削除する度に全ての要素を移動させる必要があり、プログラム全体で N × K 回ループを回す必要があります。
この問題の条件に注目すると 1 ≦ K ≦ N ≦ 100,000 とあるので、 N × K は最大で 10,000,000,000 になり得ます。
これでは実行時間内に答えを出すことはできません。
この問題を解決するためには、計算量を意識してプログラムを書く必要があります。言語間で備わっているデータ構造が異なっているので一概にこれを使えば良いというのはないので、各言語ごとの実装例にて計算量改善の方法を参照してください。
この問題を解くためのデータ構造として、代表的なものとしては両端キューが挙げられます。
これは、末尾への要素の追加と先頭要素の削除を高速(O(1))に行うことができます。
このデータ構造を使うことで、この問題の計算量は O(N+K) となります。

両端キューは collections モジュールの deque クラスとして用意されています。
この deque オブジェクトの popleft メソッドの計算量は O(1) です。
'''

step6　連想配列
# utf-8
N, K = map(int, input().split())
roster = {(x, y) for x, y in [input().split() for _ in range(N)]}

for _ in range(K):
    q = input()
    for num, ID in roster:
        if num == q:
            print(ID)
'''
全ての生徒の出席番号と ID をセットで保持し、出席番号が与えられたら、その出席番号と対応する ID を探して出力すれば良いです。
出席番号と ID をセットで保持するには、配列を 2 つ用意して、 1 人の出席番号と ID を同じ要素番号に入れるなどすれば良いです。
'''

step7　連想配列(query)
# utf-8
N, K = map(int, input().split())
roster = {x: y for x, y in [input().split() for _ in range(N)]}

for _ in range(K):
    s = input().split()
    if s[0] == "join":
        num, ID = s[1:]
        roster[num] = ID
    elif s[0] == "leave":
        num = s[1]
        del roster[num]
    else:
        num = s[1]
        print(roster[num])
'''
全ての生徒の出席番号と ID をセットで保持し、出席番号が与えられたら全ての出席番号の中から、その出席番号を探す方針のプログラムを組んだ場合、ループが最大で (100,000)^2 回回ってしまうため、実行時間制限に間に合いません。
また、生徒の追加や削除のごとに生徒に対応する要素番号が変化するため、情報の管理が大変になってしまいます。
これらの問題を解決するために連想配列というものを使うことにします。
連想配列とは、キーと呼ばれる値とそれに対応する値からなるデータ構造であり、N 個のキーとその値の組の中から、特定のキーに対応する値を取得する際にかかる時間が O(log N) でおこなうことができます。
また、連想配列ではキーと値の組の追加・削除も O(log N) でおこなうことができるため、今回の問題で与えられる全てのイベントの処理を O(log N) でおこなうことができるため、この問題を O(K log (N + K)) で解くことができるようになります。

辞書 (dict オブジェクト) を使って実装しています。
dict オブジェクトはキーと値の組をキーのハッシュ値で管理します。
>ハッシュ法を用いてキーと値の組を管理しているため、キーを用いた探索の計算量は平均 O(1) です。
dict オブジェクトの要素をキーを指定して削除する際は del 文を del dict[削除したい組のキー] のように使います。
削除の計算量は平均 O(1) です。
'''

step8　ソートと検索
# utf-8
N, X, P = map(int, input().split())
A = [int(input()) for _ in range(N)]

A.append(X)
A.append(P)
print(sorted(A).index(P) + 1)
'''
配列に全員の身長を格納したのち、昇順にソートをしたときに paiza 君の身長が前から何番目に現れるかを調べれば良いです。
sorted 関数の引数にリストを渡すと、ソート済みのリストを得ることができます。
また、リストの index メソッドを list.index(調べたい要素) のように使うとリストの中で一番左にある 調べたい要素 のインデックスを得ることができます。
このメソッドの計算量は O(N) です。
'''

final　ソートと検索(query)
# utf-8
N, K, P = map(int, input().split())
A = [int(input()) for _ in range(N)]

A.append(P)
ans = sorted(A).index(P) + 1

for _ in range(K):
    event = input()

    if event == "sorting":
        print(ans)
        continue

    x = int(event.split()[1])
    if x < P:
        ans += 1
'''
イベントが最大で 100,000 回起こるということは、実行時間を考えるとイベント 1 つあたりおおよそ 1,000 回程度のループで処理を行わなければいけません。
要素数 N の配列のソートには O(N log N) かかりますから、sorting が与えられるたびにソートをしていては間に合いません。
そこで、効率の良いデータの持ち方を考えてみましょう。転校生がやってくることで paiza 君が前から何番目に並ぶかが変化するのは、転校生の身長が paiza 君よりも小さいときのみです。
元からクラスにいる人の中で身長が paiza 君よりも小さい人の数を数えておき、転校生が来るたびに身長が paiza 君より小さいかどうかを判定し、小さい場合は答えを +1 することで、いちいちソートをせずにこの問題を解くことができます。
'''

<Vtuber>
step1　アイドルグループ
# utf-8
N, K = map(int, input().split())
names = {input() for _ in range(N)}

for _ in range(K):
    event = input()

    if event == "handshake":
        for name in sorted(names):
            print(name)
    else:
        event, name = event.split()
        if event == "join":
            names.add(name)
        else:
            names.remove(name)
'''
イベントが最大で 100,000 回与えられることを踏まえると、実行時間制限に間に合う目安の計算回数である 10^8 以下に全体の計算量を抑えるためには、
各イベントの処理「アイドルの加入」「アイドルの脱退」をO(log N) 程度の計算量で抑える必要があります。
これらを満たすデータ構造として順序付集合が挙げられます。これは N 要素の集合への要素の追加・削除を O(log N) でおこなうことができ、要素を常にソートされた状態で保持します。
入力に応じた順序付集合の処理を行うことでこの問題を解くことができます。set オブジェクトを使います。
set オブジェクトの要素は set.remove(削除したい要素) のように remove メソッドを使うことで削除できます。
set オブジェクトの remove メソッドの計算量は平均 O(1) です。
'''

step2　歴史を作る時間
# utf-8
N, K = map(int, input().split())
names = [input() for _ in range(N)]

histories = [None] * K
for i in range(K):
    year, charge = input().split()
    histories[i] = (int(year), charge)

for year, name in sorted(histories):
    print(name)
'''
入力が複数個与えられているのでこの問題も入力ごとに処理をおこなうクエリの問題に見えますが、結論から言うとこの問題はクエリの問題ではありません（ひっかけです、すみません）
よくよく問題文を見ると、この問題は「全ての歴史の出来事をソートしたのち、各出来事に対応した人の名前を順に出力する」ことで解くことができます。
処理を入力のたびにおこなうことも大切ですが、まとめて処理できるものはいったん全て入力を受け取ってから処理をするということも大切になります。
問題ごとに、どのタイミングで入力を受け取り、どのタイミングで処理するのかを意識することが大切です。
歴史の出来事と担当をペアとしてまとめて保持してそれらを年の順に並べたり、歴史の出来事と担当を関連付けてから、出来事をソートしたのち対応する担当を出力することでこの問題を解くことができます。
出来事が起こった年と担当者の名前を組で保持するためにタプル (tuple オブジェクト) を用います。
そしてその tuple オブジェクトをリストで管理し、sorted 関数を用いてソートすればよいです。
'''

step3　銀行
# utf-8
N, K = map(int, input().split())

data = {}
for _ in range(N):
    c, p, d = input().split()
    data[c] = (p, int(d))

for _ in range(K):
    g, m, w = input().split()

    pin, save = data[g]
    if pin != m:
        continue

    data[g] = (pin, save - int(w))

for name, d in data.items():
    print(name, d[1])
'''
会社による預金の引き出しは最大で 100,000 回行われるため、実行時間制限に間に合う目安の計算回数である 10^8 以下に全体の計算量を抑えるためには、預金の引き出し 1 回あたりの処理を O(log N) 程度でおこなう必要が出てきます。
初めに与えられる情報と、引き出し時に与えられる情報のうち共通しているものは会社名であり、暗証番号のチェックや預金残高の計算には時間はかからないことから、次のような処理が O(log N) 程度でできれば良いことがわかります。
  「会社名から、その会社の暗証番号を取得する」
  「会社名から、その会社の預金残高を取得する」
  
決まった値から関連した値を取り出したい時には連想配列を使うと便利です。
連想配列では、上の 2 つの処理と要素の追加をいずれも O(log N) でおこなうことができるので、連想配列を用いることでこの問題を解くことができます。
最後に、与えられた順で会社の残高を出力する必要があるので、与えられた順に会社の名前を保持しておく必要があることに注意しましょう。

辞書を使います。解答コードでは以下のようにオブジェクトを生成しています。
キー : 会社名
値 : 暗証番号と残高のタプル
以下でコードの計算量を確認します。
【 g not in data 】
目的 : 取引を行おうとした会社の社名が銀行に登録されているか確認する
計算量 : 平均 O(1)
【 pin != m 】
目的 : 暗証番号が合っているかを確認する
計算量 : O(1)
【 data[g] = (pin, save - int(w)) 】
目的 : 残高の更新をする
計算量 : O(1)
'''

step4　経理
# utf-8
N, K = map(int, input().split())
departments = {input(): [] for _ in range(N)}

for _ in range(K):
    a, p, m = input().split()

    departments[a].append((p, m))

for key, val in departments.items():
    print(key)
    for p, m in val:
        print(p, m)

    print("-----")
'''
領収書は最大で 100,000 枚あるので、実行時間制限に間に合う目安の計算回数である 10^8 以下に全体の計算量を抑えるためには、領収書 1 枚あたりの処理を O(log N) 程度でおこなう必要が出てきます。
注文番号と金額を各部署の会計表に追加する操作は、会計表を配列として扱うことで、配列への要素の追加と同じとみなすことができます。
よって、この問題を解くためには、「部署名から、その部署の会計表を取得する」操作が O(log N) 程度でおこなえれば良いことがわかります。
決まった値から関連した値を取り出したい時には連想配列を使うと便利です。
今回の問題では、「初めに与えられる情報」と「領収書に含まれる情報」のうち共通しているものは部署名であるので、キーを「部署名」・値を「注文番号と金額をペアで保持する配列」とすれば良いです。
連想配列では、「キーから値を取り出す操作」と「キーと値の追加」をいずれも O(log N) でおこなうことができるので、連想配列を用いることでこの問題を解くことができます。
最後に、与えられた順で部署の残高を出力する必要があるので、与えられた順に部署の名前を保持しておく必要があることに注意しましょう。

辞書を使います。解答コードでは以下のようにオブジェクトを生成しています。
キー : 部署名
値 : 注文番号と金額のタプルを 1 要素とするリスト
解答コードにおいて、今回の肝となるコードは departments[a].append((p, m)) ですが、この処理の計算量は平均 O(1) です。
これは、departments が dict オブジェクトであり、要素の取得が平均 O(1) で済むことと、list オブジェクトに要素を追加する append メソッドの計算量が O(1) であることから確認できます。

最初に、部署の数（N）と領収書の枚数（K）を読み込みます。
部署名をキーとし、空の領収書情報リストを値とする辞書を作成します。
領収書情報をK回繰り返し読み込み、部署ごとに情報を適切なリストに追加します。
各部署ごとに、部署名を出力し、その後に領収書情報（注文番号と金額）を出力します。
各部署の情報を出力した後、区切り線 "-----" を出力して、次の部署の情報に移ります。
'''

final Vtuber
# utf-8
N = int(input())

superchat = {}
member = set()
for _ in range(N):
    event = input().split()

    name = event[0]
    verb = event[1]
    if verb == "give":
        money = int(event[2])
        if name not in superchat:
            superchat[name] = (money, name)
        else:
            superchat[name] = (superchat[name][0] + money, name)
    else:
        member.add(name)

for name, money in sorted(superchat.items(), key=lambda x: x[1], reverse=True):
    print(name)
for name in sorted(member):
    print(name)
'''
N , K の制約より、各イベントについての処理を O(log N) 程度でおこなう必要があることがわかると思います。
スーパーチャットとメンバーシップの 2 つの処理が存在しますがこれらは互いに独立しているので分けて考えましょう。
それぞれのイベントを処理するために必要な操作をまとめてみましょう。

【スーパーチャット】
金額と名前を受け取り、その人が既にスーパーチャットをしている場合はその人のスーパーチャットの合計金額に受け取った金額を加算する。
初めてのスーパーチャットの場合は、その人のスーパーチャット合計金額を受け取った金額で初期化する。
最後にスーパーチャットの金額が高い順に名前を呼ぶ
これらの処理を言い換えると、主に次の 2 つの処理になります。
「名前から、その人のスーパーチャット総額を調べる」
「スーパーチャットの金額と名前のペアを金額が高い順に並び替える」
1 つ目の処理のような、決まった値から関連した値を取り出したい時には連想配列を使うと便利です。
連想配列の値には配列も指定することができるので、今回の問題では、キーを「名前」・値を「スーパーチャットの総額」とすれば良いです。
連想配列では、上の 2 つの処理と要素の追加をいずれも O(log N) でおこなうことができます。
2 つ目の処理をおこなうには、ペアを要素とする配列をソートしたり、名前と金額を関連づけてから金額でソートをおこなうなどすれば良いです。

【メンバーシップ】
メンバーシップに加入した人の名前を、加入者一覧に追加する
最後に、加入者の名前を辞書順で読み上げる
これは、加入者を配列などで管理したのち、ソートをおこなうことで処理することができます。
以上の 2 つの処理を入力に応じておこなうことでこの問題を解くことができます。

スーパーチャットをくれた人々とメンバーシップに加入してくれた人々で分けて、それぞれにオブジェクトを用意します。
解答コードでは、以下のように用意しています。
【 スーパーチャット 】
型 : dict
理由 : アカウント名と金額を組で考える必要があるため
【 メンバーシップ 】
型 : set
理由 : アカウント名だけ考えればよいから
解答コードにおいて、スーパーチャットの dict オブジェクトの値はスーパーチャットの総額とアカウント名をこの順でリストに格納する必要があります。
それは以下の 2 つの理由に依るものです。
ソートの都合
2 次元リストのソートは「各要素の 0 番目の要素を基準にソートして、0 番目の値が同等だった場合、1 番目の要素を基準にソートして、1 番目の値が同等だった場合、2 番目の要素を基準に ...」という法則でおこなわれます。
今回は金額を優先したいので、金額を 0 番目、アカウント名を 1 番目の要素に格納します。
値の更新の必要性
タプルは一回生成するとそのタプルの値を更新することはできません。
そのため、リストを用います。
逆順にソートするためにはソートする関数のパラメータで reverse=True とします。
'''

<平方分割>
step1　累積和
# utf-8
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

ans = [0] + A[:]
for i in range(1, N + 1):
    ans[i] += ans[i - 1]

for _ in range(K):
    q = int(input())
    print(ans[q])
'''
各 Q_i (1 ≦ i ≦ K) について A_1 ... A_{Q_i} の和をいちいち計算すると、最悪ケースのとき、プログラム全体でループが K × N 回回るため実行時間に間に合いません。
では実行時間に間に合わせるためにはどうしたら良いでしょうか。
A_1 から A_i までの和を sum[i] とすると、sum[i] = sum[i-1] + A[i] という関係が成り立つことを用いて、すべての i について sum[i] を計算しておくことで、この問題を実行時間内に解くことができます。
今回の問題で求めた区間の和 を 累積和 といい、計算量を落とす際にしばしば用いられます。
'''

step2　区間和
# utf-8
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

ans = [0] + A[:]
for i in range(1, N + 1):
    ans[i] += ans[i - 1]

for _ in range(K):
    left, right = map(int, input().split())

    print(ans[right] - ans[left - 1])
'''
素直に区間の始まりと終わりを全探索して実装すると、計算量が O(N^2) となってしまい実行時間制限に間に合いません。
そこで、累積和 S[i] = A[1] + ... + A[i] を用います。
A[l]+...+A[r] = (A[0]+...A[r]) - (A[0]+...A[l-1]) = S[r]-S[l-1]
の関係より、累積和 S を前もって計算しておけば、以上の関係から区間 l,r の和を O(1) で求めることができるので
全体の計算量を O(N) にできます。
'''

step3　二次元累積和
# utf-8
H, W, N = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]

ans = [[0] * (W + 1) for _ in range(H + 1)]

for i in range(1, H + 1):
    ans[i] = [0] + A[i - 1][:]
    for j in range(1, W + 1):
        ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1]

for _ in range(N):
    y, x = map(int, input().split())
    print(ans[y][x])
'''
クエリの問題では、与えられるクエリの数から 1 クエリあたりの計算量を概算するのも効果的です。
例えば、今回の問題では与えられるペアをクエリとみなすことができ、その数は最大で 100,000 であるから、 1 クエリあたりおおよそ 1000 回未満に抑えたいと気づくことができます。
これらを踏まえて問題をみてみましょう。各クエリの累積和を問題文で与えられた計算式の通り計算を行うと実行時間制限に間に合わないことがわかると思います。
では、どのように S(y,x) を計算すれば良いのでしょうか。
計算量を落とすためには、事前に値を計算しておいたり、既に計算した値を再利用したりすることが有効です。
A の要素を端から見ていくと同時に、注目している要素の S(y,x) も計算できないかを考えてみます。行番号が 1 のときの場合に限っては
S(1,1) = A[1][1]
S(1,i) = A[1][1] + ... + A[1][i]
といった具合に 1 次元配列の累積和と同様に扱うことができますが、2 行目以降については同じようには計算できません。
そこで図形の関係を考えます。
例として次のような A の S(3,3) を求めてみます。
S(3,3) は{黄緑の領域の値} + {水色の領域の値} - {ピンクの領域の値} + {黄色の領域の値}で求めることができます。
黄緑の領域の値 = S(2,3) = S(3-1,3)
水色の領域の値 = S(3,2) = S(3,3-1)
ピンクの領域の値 = S(2,2) = S(3-1,3-1)
黄色の領域の値 = A[3][3]
なので、S(i,j) は i と j を用いて次の計算式で求められます。 S(i,j) = S(i-1,j) + S(i,j-1) - S(i-1,j-1) + A[i][j]
しかし、この計算式は i ,j によっては存在しない S を計算に用いてしまうので、 i , j の値に応じて場合分けを行う必要があります。
i = 1 のときには S(i-1,j) , S(i-1,j-1) が、 j = 1 のときには S(i,j-1) , S(i-1,j-1) が存在しないため、その項を無視しましょう。このことは図形を書くことからも気づくことができます。
'''

step4　二次元区間和
# utf-8
H, W, N = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]

ans = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
    ans[i] = [0] + A[i - 1][:]
    for j in range(1, W + 1):
        ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1]

for _ in range(N):
    a, b, c, d = map(int, input().split())

    val = ans[c][d]
    if 0 < a and 0 < b:
        val += ans[a - 1][b - 1]
    if 0 < a:
        val -= ans[a - 1][d]
    if 0 < b:
        val -= ans[c][b - 1]

    print(val)
'''
クエリの問題では、与えられるクエリの数から 1 クエリあたりの計算量を概算するのも効果的です。
例えば、今回の問題では与えられるペアをクエリとみなすことができ、その数は最大で 100,000 であるから、 1 クエリあたりおおよそ 1000 回未満に抑えたいと気づくことができます。
これらを踏まえて問題をみてみましょう。各クエリの累積和を問題文で与えられた計算式の通り計算をおこなうと実行時間制限に間に合わないことがわかると思います。
では、どのように S({a,b},{c,d}) を計算すれば良いのでしょうか。
計算量を落とすためには、事前に値を計算しておいたり、既に計算した値を再利用したりすることが有効です。
まず用意として、前問の二次元累積和 S(i,j) を全てのマスについて求めておきます。 この値を用いて S({a,b},{c,d}) も計算できないかを考えてみます。a = c の場合に限っては
S({a,b},{c,d}) = S(a,d) - S(a,b) といった具合に 1 次元配列の累積和と同様に扱うことができますが、それ以外の場合については同じようには計算できません。
そこで図形の関係を考えます。
例として次のような A の S({2,2},{3,3}) を求めてみます。S(3,3) は{黄緑の領域の値} - {水色の領域の値} - {ピンクの領域の値} + {黄色の領域の値}で求めることができます。
黄緑の領域の値 = S(3,3) = S(c,d)
水色の領域の値 = S(1,3) = S(a-1,d)
ピンクの領域の値 = S(3,1) = S(c,b-1)
黄色の領域の値 = S(1,1) = S(a-1,b-1)
なので、S({a,b},{c,d}) は a , b , c , d を用いて次の計算式で求められます。
S({a,b},{c,d}) = S(c,d) - S(a-1,d) - S(c,b-1) + S(a-1,b-1)
しかし、この計算式は a ,b によっては存在しない S を計算に用いてしまうので、 i , j の値に応じて場合分けをする必要があります。
a = 1 のときには S(a-1,d) , S(a-1,b-1) が、 b = 1 のときには S(a,b-1) , S(a-1,b-1) が存在しないため、その項を無視しましょう。このことは図形を書くことからも気づくことができます。
'''

step5　平方分割のパケット
# utf-8
A = [int(input()) for _ in range(10000)]

ans = [-1] * 100
for i in range(100):
    start, end = 100 * i, 100 * (i + 1)

    ans[i] = max(A[start:end])

for val in ans:
    print(val)
'''
問題の指示通りの処理を行いましょう。 100 要素ごとに、その区間の最大の要素を出力しても良いですし、配列などに最大値を格納して最後にまとめて出力しても良いです。
max 関数は引数に list オブジェクトを渡すと、list オブジェクトに含まれる要素の最大値を返します。この際、計算量は O(N) です。
'''

final　平方分割
# utf-8
N, K = 10000, int(input())
A = [int(input()) for _ in range(N)]

sqrt = int(pow(N, 0.5))
if sqrt ** 2 < N:
    sqrt += 1

range_max = [-1] * sqrt
for i in range(sqrt):
    start, end = sqrt * i, sqrt * (i + 1)
    range_max[i] = max(A[start:end])

for _ in range(K):
    left, right = map(lambda x: int(x) - 1, input().split())

    ans = A[left]
    now = left
    while now <= right:
        if now % sqrt == 0 and now + sqrt - 1 <= right:
            ans = max(ans, range_max[now // sqrt])
            now += sqrt
        else:
            ans = max(ans, A[now])
            now += 1

    print(ans)
'''
「長さ N の配列が与えられたとき、N の平方根を x を求め、配列を長さ x の配列に分割し、それぞれの配列について目的の値を調べておく」ためには、まず 10,000 の平方根 x を求めた後、長さが x の分割後の各区間の配列を用意して、そこに各区間の最大値を格納しましょう。
「調べたい区間に完全に含まれている配列についての 1. で求めた値と、その配列以外の部分の値を全て調べて、目的の値を求める」ためには、「調べたい区間の先頭から順に調べていき、1. で作成した各区間の始まりになったらその区間を完全に含むかどうかを判定する」処理をすれば良いです。
例として要素数 N = 9 のA = {3,5,7,4,3,5,8,5,7}の 2 要素目から 8 要素目のうち最大値を求める時を考えると、探索は次のような手順になります。
{手順 1 }
まず、A を長さ 3 の 3 つの配列に分け、それらの中での最大値を求める。
すると最大値はそれぞれ 7,5,8 となる。
{手順 2 }
2 要素目を見る。現状の最大値は 5
3 要素目を見る。現状の最大値は 7
4 要素目を見る。これは事前に作成した長さ 3 の 2 つ目の配列の初めの要素であるから、2 つ目の配列が調べたい区間に完全に含まれているかどうかを調べる。
配列の長さは 3 であるから 4 + 2 ≦ 8 より 2 つ目の配列は完全に含まれているので、4 要素目 〜 6 要素目を見る代わりに 2 つ目の配列の最大値 5 を見る。現状の最大値は 7
7 要素目を見る。これは事前に作成した長さ 3 の 3 つ目の配列の初めの要素であるから、3 つ目の配列が調べたい区間に完全に含まれているかどうかを調べる。
配列の長さは 3 であるから 7 + 2 > 8 より 3 つ目の配列は完全に含まれていないため、2 , 3 要素目と同様に見る。現状の最大値は 8
8 要素目を見る。答えとなる最大値は 8
'''

<点の幅>
step1　'I'の数
# utf-8
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

ans = [0] + A[:]
for i in range(1, N + 1):
    ans[i] += ans[i - 1]

for _ in range(K):
    a_left, a_right, b_left, b_right = map(int, input().split())

    a = ans[a_right] - ans[a_left - 1]
    b = ans[b_right] - ans[b_left - 1]

    if a_right - a_left + 1 >= N / 3:
        a = -1
    if b_right - b_left + 1 >= N / 3:
        b = -1

    if a == b:
        print("DRAW")
    elif a > b:
        print("A")
    else:
        print("B")
'''
教科書の i ページ目までの I の数の和 sum[i] = A[1] + ... + A[i] (ただし sum[0] = 0) を利用すると、l ≦ r である l, r について l ページ目から r ページ目までの I の数の和は sum[r] - sum[l-1] で求めることができます。
この sum[i] は累積和と呼ばれ、sum[i] = sum[i-1] + A[i] の関係を用いると高速に計算できるので、これを事前に計算しておくことで各試合の勝敗の判定を O(1) でおこなうことができます。
よって問題全体として、O(N + K)となるので実行時間制限以内で解くことができます。
l ページ目から r ページ目を掴んだときの掴んだページ数は r - l + 1 になることに気をつけましょう。
ルール違反した人のスコアを -1 にすると、勝敗の判定が単純な条件分岐でできるようになります。
'''

step2　ドーナツ
# utf-8
def calc_interval_sum(X, a, b, c, d):
    rst = X[c][d]
    if 0 < a and 0 < b:
        rst += X[a - 1][b - 1]
    if 0 < a:
        rst -= X[a - 1][d]
    if 0 < b:
        rst -= X[c][b - 1]

    return rst


H, W, N = map(int, input().split())
C = [[int(x) for x in input().split()] for _ in range(H)]

ans = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
    ans[i] = [0] + C[i - 1][:]
    for j in range(1, W + 1):
        ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1]

for _ in range(N):
    y, x, b, s = map(int, input().split())

    bm, sm = b // 2, s // 2

    outer = calc_interval_sum(ans, y - bm, x - bm, y + bm, x + bm)
    inner = calc_interval_sum(ans, y - sm, x - sm, y + sm, x + sm)
    print(outer - inner)
'''
ドーナツを作ることをクエリとすると、この問題では最大で 100,000 個のクエリが与えられることになります。
プログラムの実行時間を踏まえると、ドーナツ 1 つあたり 1000 回 程度の計算でドーナツ上のチョコの数を求める必要があります。
ドーナツ上のチョコの数を求めるために、ドーナツである領域のマスのチョコを全て数えていては計算量が大きくなり過ぎてしまいます。
これを解消するためにまず、ドーナツの穴をくり抜く前の生地のチョコの個数を数え、そこからくり抜いた穴の部分にあったチョコの数を引くという方針をとってみましょう。
H 行 W 列の二次元配列の全ての長方形の領域の総和は、事前に O(HW) で二次元累積和を計算しておくことで O(1)で求めることができます。
※二次元累積和・二次元区間和を参照してください。
二次元配列の二次元区間和 SUM({a,b},{c,d}) を求めることができるとすると、中心 (y,x) , 外側の一辺の長さ B , 穴の一辺の長さ S であるドーナツに乗っているチョコの個数は
SUM({y-floor(B/2),x-floor(B/2)},{y+floor(B/2),x+floor(B/2)}) - SUM({y-floor(S/2),x-floor(S/2)},{y+floor(S/2),x+floor(S/2)})
で求めることができます。二次元累積和が存在するかどうかに気をつけながらこの値を求めることでこの問題を解くことができます。
'''

final　点の幅
# utf-8
def calc_min_and_max_in_divisioned_area(X, range_min, range_max, sqrt, left, right):
    rst_min, rst_max = X[left], X[left]
    now = left
    while now <= right:
        if now % sqrt == 0 and now + sqrt <= right:
            rst_min = min(rst_min, range_min[now // sqrt])
            rst_max = max(rst_max, range_max[now // sqrt])
            now += sqrt
        else:
            rst_min = min(rst_min, X[now])
            rst_max = max(rst_max, X[now])
            now += 1

    return rst_min, rst_max


N, K = map(int, input().split())
S = [int(input()) for _ in range(N)]

sqrt = int(pow(N, 0.5))
if sqrt ** 2 < N:
    sqrt += 1

range_max = [-1] * N
range_min = [-1] * N
for i in range(sqrt):
    start, end = sqrt * i, sqrt * (i + 1)
    range_max[i] = max(S[start:end])
    range_min[i] = min(S[start:end])

for _ in range(K):
    a_left, a_right, b_left, b_right = map(lambda x: int(x) - 1, input().split())

    a_rg = a_right - a_left + 1
    b_rg = b_right - b_left + 1

    a_rg_min, a_rg_max = calc_min_and_max_in_divisioned_area(
        S, range_min, range_max, sqrt, a_left, a_right
    )
    b_rg_min, b_rg_max = calc_min_and_max_in_divisioned_area(
        S, range_min, range_max, sqrt, b_left, b_right
    )

    a_score = a_rg_max - a_rg_min
    b_score = b_rg_max - b_rg_min

    if a_score == b_score:
        print("DRAW")
    elif a_score > b_score:
        print("A")
    else:
        print("B")
'''
各試合の判定について A , B が選んだ生徒全員の点数を調べ(最高点 - 最低点)の値を求めた場合、1 試合あたり最大で N 人の生徒の点数を調べる必要があり、試合数は K なので全体として O(N*K) となります。この場合、最大 1,000,000,000 回処理を行う必要があり、これでは実行時間に間に合いません。
まずはこのように何回ループが回るかの検討を立て、実行時間に間に合うような実装を考えることがクエリの問題では大切になってきます。
では、実行時間に間に合うようにするにはどのような実装をすれば良いでしょうか？
試合数は最大で 100,000 なので、1 試合のあたりのループ回数を 1000 回未満に抑えたいところです。
そこで活躍するテクニックとして平方分割というアルゴリズムがあります。
これは、決まった区間の最大値や最小値などを求めたいことがわかっているときに元のデータをルート N の区間ごとに分け、その区間内での最大値・最小値を求めておくことで、ある区間の最大値・最小値を求める際に必要なループ回数を最大でルート N 回程度に抑えることができるというアルゴリズムです。
言葉ではわかりにくいので、図を使って説明します。
例えば、長さ 9 の次の数列 A のある区間の要素の最大値を求めたいとします。
A = {6,4,7,3,9,4,3,8,7} ルート 9 は 3 なので、3 つずつの区間 A_1 = {6,4,7}, A_2 = {3,9,4}, A_3 = {3,8,7} に分割します。
この各区間の中での最大値はそれぞれ 7 , 9 , 8 です。ここまでが前処理になります。
次に、最大値を求めたい区間の最大値を求めます。この値を求めるために区間の左端の A の要素からみていくのは普通の探索と変わりませんが、次のような工夫をします。
探索途中に事前に分割した区間を完全に含む場合、その区間内の各要素を調べる代わりにその区間の代表値（ここでは最大値）を調べる。
例として、A の 2 要素目から 7 要素目までの要素の最大値を求めたい場合、次の通り探索が進んでいきます。
2 要素目を見る。値は 4 であるから、現在の最大値は 4
3 要素目を見る。値は 7 であるから、現在の最大値は更新されて 7
4 要素目から 6 要素目までを調べる代わりに A_2 の最大値を調べる。現在の最大値は更新されて 9
7 要素目を見る。値は 3 であるから、答えは 9
よって探索回数は 6 回から 4 回に減らすことができました。
A の要素数 N が増えれば増えるほどこのアルゴリズムは効果を発揮します。具体的には以上のような探索を O(ルート N) でおこなうことができます。
このアルゴリズムを使って各試合の値（最大値ー最小値）を計算すれば、全体の最大のループ回数を 10,000,000 程度に抑えることができ、この問題を解くことができます。

min 関数に list オブジェクトを渡すと、その list オブジェクトに含まれる要素の最小値を返します。min 関数の計算量は O(N) です。
また、平方分割を用いて最小値、最大値を求める処理を関数として抽出すると、簡潔なコードになります。
'''