NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）F問題メモ

NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）

久々の7完。気持ち、中盤の問題に典型が多めだった？

F - Operations on a Matrix

問題

$N$ 行 $M$ 列の行列があり、はじめ、全ての成分が0
$Q$ 個のクエリを順に処理せよ
- 1 l r x: $l～r$ 列目（縦）の成分全てに $x$ を加算
- 2 i x: $i$ 行目（横）の成分全てを $x$ で置き換える
- 3 i j: $(i,j)$ 成分を出力する
$1 \le N,M,Q \le 2 \times 10^5$

解法

クエリ3が来たとき、「そのマスが最後にクエリ2で上書きされた時の $x$ に、それより後にクエリ1で加算された値を全て加えた値」を出さないといけない。

あるマスに対するクエリの履歴例（q1:加算、q2:上書き更新）

q1(1) q1(3) q2(5) q1(7) q2(9) q1(2) q1(4)  q3 この時の値は?
                        ~~~~~~~~~~~~~~~~~     →ここの合計

クエリ1は、まぁ範囲加算と1点取得なので、Fenwick木なんかで管理することになるだろう。
ただ、「 $j$ 列目に対する加算のうち、あるタイミングより後の加算のみを取り出す」ことを、クエリ3の時点でやろうとすると難しい。

クエリ2で上書きされた時に、その時点の列の累積加算値を記録しておけば、クエリ3が来た時点の累積加算値との差分で、クエリ1による加算値は求められる。

            q1(1) q1(3) q2(5) q1(7) q2(9) q1(2) q1(4)  q3
累積加算値     1     4          11          13    17
                                      ＊                    この時に現在の値 11 を記録
                                                       ＊   この時の現在の値 17 との差分 6 が、
                                                            最後のクエリ2以降に加算された値

だが、クエリ2が来るたびに全ての列に対して現在値を記録しておく訳にもいかないので、本当に必要な列、つまり「そのクエリ2で上書きされた値 $x$ を使うようなクエリ3の列」を先読みして、そこのみ記録しておく、といった処理をする必要がある。

まぁ実際にその通りやってもいいんだけど、クエリを逆順に考えると、多少は見通しが良くなる。

クエリ1は、Fenwick木やセグ木などで、各列ごとの累積加算値を管理する
クエリ3が来たら、 $(i,j)$ にコマを置き、コマにその時点の $j$ 列目の累積加算値をメモっておく
クエリ2が来たら、その行に置かれている全てのコマについて、以下を行う
- コマが $(i,j)$ にあったとする
- その時点の $j$ 列の累積加算値を $Y$ 、コマに書かれた累積加算値を $Z$ とする
- そのコマの答えは、 $x+Y-Z$ （ $x$ はクエリ2による上書き値）
- コマを取り除く

クエリ3で記録して、クエリ2で確定、となるので、どの列に対して記録しなければならないかがクエリ順的にわかりやすくなる。

Python3

        
          
          
              
              from operator import add
 
 
class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()
 
    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i
 
    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s
 
    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和
 
        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total
 
    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)
 
 
n, m, q = map(int, input().split())
 
queries = []
query3_count = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        query[1] -= 1
    elif query[0] == 2:
        query[1] -= 1
    else:
        query[1] -= 1
        query[2] -= 1
        query.append(query3_count)
        query3_count += 1
    queries.append(query)
 
rows_last_overwritten = [0] * n
rows_q3 = [set() for _ in range(n)]
cols = FenwickTreeInjectable(m + 1, int, add)
ans = [0] * query3_count
 
for query in reversed(queries):
    if query[0] == 1:
        l, r, x = query[1:]
        cols.add(l, x)
        cols.add(r, -x)
    elif query[0] == 2:
        i, x = query[1:]
        for j, qi in rows_q3[i]:
            ans[qi] += cols.sum(j) + x
        rows_q3[i].clear()
    else:
        i, j, qi = query[1:]
        rows_q3[i].add((j, qi))
        ans[qi] -= cols.sum(j)
 
for i in range(n):
    for j, qi in rows_q3[i]:
        ans[qi] += cols.sum(j)
 
print('\n'.join(map(str, ans)))

            

        
      