日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）E,F,G問題メモ

def solve(h, w, aaa, ppp):
    def check(x):
        if aaa[0][0] + x < ppp[0]:
            return False
        dp = [[-1] * w for _ in range(h)]
        dp[0][0] = aaa[0][0] + x - ppp[0]
        # print(dp)
        for i in range(h):
            for j in range(w):
                if i == j == 0:
                    continue
                tmp = -1
                if i > 0 and dp[i - 1][j] >= 0:
                    tmp = max(tmp, dp[i - 1][j] + aaa[i][j] - ppp[i + j])
                if j > 0 and dp[i][j - 1] >= 0:
                    tmp = max(tmp, dp[i][j - 1] + aaa[i][j] - ppp[i + j])
                dp[i][j] = tmp
        return dp[-1][-1] != -1

    if h == w == 1:
        return max(0, ppp[0] - aaa[0][0])

    l = -1
    r = 1 << 58
    while l + 1 < r:
        mid = (l + r) // 2
        # print(f'{mid=}', check(mid))
        if check(mid):
            r = mid
        else:
            l = mid
    return r


h, w = map(int, input().split())
aaa = [list(map(int, input().split())) for _ in range(h)]
ppp = list(map(int, input().split()))
ans = solve(h, w, aaa, ppp)
print(ans)

import sys


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


def solve(n, q, s, queries):
    def merge(a, b):
        if a[2] == b[0]:
            l = a[3] + b[1]
            if a[5] == 1:
                if b[5] == 1:
                    return (a[2], l, b[0], l, l, 1)
                else:
                    return (a[2], l, b[2], b[3], max(l, b[4]), 0)
            if b[5] == 1:
                return (a[0], a[1], b[0], l, max(l, a[4]), 0)
            return (a[0], a[1], b[2], b[3], max(l, a[4], b[4]), 0)
        return (a[0], a[1], b[2], b[3], max(a[4], b[4]), 0)

    s = [c - 97 for c in s]
    init = [(x, 1, x, 1, 1, 1) for x in s]
    sgt = SegmentTreeInjectable.from_array(init, lambda: (-1, 0, -1, 0, 0, 0), merge)

    buf = []
    for query in queries:
        if query[0] == b'1':
            i = int(query[1]) - 1
            x = query[2][0] - 97
            sgt.update(i, (x, 1, x, 1, 1, 1))
        else:
            l = int(query[1]) - 1
            r = int(query[2])
            result = sgt.get_range(l, r)
            buf.append(result[4])
    return buf


input = sys.stdin.buffer.readline

n, q = map(int, input().split())
s = input()
queries = [input().split() for _ in range(q)]
ans = solve(n, q, s, queries)
print('\n'.join(map(str, ans)))

from collections import defaultdict


def solve(n, m, pairs):
    changes = defaultdict(int)
    for a, b in pairs:
        changes[a] = max(changes[a], b)
    best_change = max((b / (a - b), a, b) for a, b in changes.items())
    _, a, b = best_change
    k = max(0, n - 90300) // (a - b)
    ans = n + k * b
    n -= k * (a - b)
    knapsack = [0] * (n + 1)
    for a in sorted(changes):
        if a > n:
            break
        b = changes[a]
        d = a - b
        for j in range(b, n - d + 1):
            knapsack[j + d] = max(knapsack[j + d], knapsack[j] + b)
    ans += knapsack[n]
    return ans


n, m = map(int, input().split())
pairs = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, pairs)
print(ans)