AtCoder Beginner Contest 292 G,Ex問題メモ

PyPyの再帰が遅いというのは、$10^4～10^5$ もの深い再帰が遅いのであって、 階層の浅い再帰の場合はそこまで恐れなくてもいいっぽい。

def dfs(l, r, k, d):
    if l == r:
        return 1

    if k == m:
        if l + 1 < r:
            return 0
        else:
            return 1

    if d >= 10:
        return 0

    if 0 <= sss[l][k] < d:
        return 0

    if memo[l][r][k][d] != -1:
        return memo[l][r][k][d]

    res = dfs(l, r, k, d + 1)

    for x in range(l + 1, r + 1):
        if sss[x - 1][k] != -1 and sss[x - 1][k] != d:
            break
        res += dfs(l, x, k + 1, 0) * dfs(x, r, k, d + 1) % MOD
        res %= MOD

    memo[l][r][k][d] = res
    return res


n, m = map(int, input().split())
sss = []
for _ in range(n):
    s = input()
    s_arr = []
    for c in s:
        if c == '?':
            s_arr.append(-1)
        else:
            s_arr.append(int(c))
    sss.append(s_arr)
MOD = 998244353
memo = [[[[-1] * 10 for _ in range(m)] for _ in range(n + 1)] for _ in range(n)]

ans = dfs(0, n, 0, 0)
print(ans)

from itertools import accumulate
from operator import add


class SegmentTreeInjectable:
    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:
            if i & 1:
                tree[i >> 1] = func(tree[i ^ 1], tree[i])
            else:
                tree[i >> 1] = func(tree[i], tree[i ^ 1])
            i >>= 1

    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 debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1

    def leftmost2(self, b):
        """ ABC292-Ex問題に特有の二分探索関数 """
        tree = self.tree
        l = 0
        r = self.offset
        i = 1
        left_sum = 0
        while l + 1 < r:
            m = (l + r) >> 1
            lch = i << 1
            rch = lch | 1

            if left_sum + tree[lch][1] >= 0:
                r = m
                i = lch
                continue

            if m < b:
                if left_sum + tree[lch][0] + tree[rch][1] >= 0:
                    l = m
                    i = rch
                    left_sum += tree[lch][0]
                    continue
            return -1
        return l


n, b, q = map(int, input().split())
aaa = list(map(int, input().split()))
INF = 1 << 60


def func(x, y):
    return (x[0] + y[0], max(x[1], x[0] + y[1]))


aaa_init = [(a - b, a - b) for a in aaa]
sgt = SegmentTreeInjectable.from_array(aaa_init, lambda: (0, -INF), func)

for _ in range(q):
    c, x = map(int, input().split())
    c -= 1
    x -= b
    sgt.update(c, (x, x))

    li = sgt.leftmost2(n)
    if li == -1:
        ans = sgt.get_all()[0] / n + b
    else:
        ans = sgt.get_range(0, li + 1)[0] / (li + 1) + b
    print(ans)