日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）E,G問題メモ

日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）

ヴァンターラヴァンターラ愛の国ヴァンターラ

E - Train Delay

問題文

Atcoder 国には $1$ から $N$ の番号がついた $N$ 個の街と、 $1$ から $M$ の番号がついた $M$ 本の電車が走っています。
電車 $i$ は街 $A_i$ を時刻 $S_i$ に発車し、街 $B_i$ に時刻 $T_i$ に到着します。
今、電車 $1$ の発車時刻が $X_1$ だけ遅れました。
「時刻表通りなら電車 $1$ からの乗り継ぎで乗車可能だった全ての電車」に、電車 $1$ が遅れた場合も乗車可能にするためには、各電車をそれぞれ最小で何分遅らせればよいか、求めてください。
すなわち、以下の条件を満たす $X_2,X_3,...,X_N$ を求めてください。
- $X_i \ge 0$
- $1 \leq i,j \leq M$ を満たす全ての組 $(i,j)$ について、「 $B_i=A_j$ かつ $T_i \leq S_j$ 」ならば「 $T_i+X_i \leq S_j+X_j$ 」
- 上記の条件を満たす中で、 $X_2+\ldots+X_M$ が最小のもの
なお、 $X_2+\ldots+X_M$ が最小になるような $X_2,\ldots,X_M$ の定め方は一意であることが証明できます。

制約

$2 \leq N \leq 2\times 10^5$
$2 \leq M \leq 2\times 10^5$
$1 \leq A_i,B_i \leq N$
$A_i \neq B_i$
$0 \leq S_i \lt T_i \leq 10^9$
$1 \leq X_1 \leq 10^9$

解法

問題設定がややこしい。
解法も「こうかな？」と思いついたものがWAやTLEになりやすく、グラフの複雑さから、上手くいかないケースも究明しづらい。

「 $X_2+\ldots+X_M$ が最小」という条件があるが、「ある電車 $i$ を余分に遅らせることで、他の $j$ が少ない遅延で発車できる」なんてことはないので、各電車について、時刻表通りではそいつに乗り継ぎ可能だった電車が全て到着し次第、すぐに発車してよい。
（または、遅延無しで発車可能なら時刻表通りとしてよい）

ある電車 $i$ の遅延時間 $X_i$ を計算したいとき、タイミングと、必要な情報を考える。

タイミング:
- 時刻表通りでは $i$ に乗り継ぎ可能だった全ての電車 $j$ の遅延時間の確定以降
情報:
- そのような電車の中での $T_j+X_j$ の最大値
  - その最大値を $M$ として、 $X_i=\max(0,M-S_i)$ として計算可能
- ただし、乗り継ぎできない電車の $T_j+X_j$ は最大値の計算に含めてはいけない

$S_i$ 以降に駅 $B_i$ に着く電車（ $T_j \gt S_i$ である $j$ ）がどれだけ遅延しようが、それは「もともと乗り継ぎ可能でない」電車なので $i$ の遅延時間には影響させなくてよい。
必要なのは、 $T_j \le S_i$ である電車のみの遅延時間である。

イベントソートで解ける。

$(S_i,1,i),(T_i,0,i)$ を、全てまとめてソートする。
0,1は、出発/到着の区別と、同率なら到着の方が先に処理されるようにするためのもの。

ソートされたイベントを順に処理する中で、処理中の時刻を $t$ として、以下の情報を管理する。

$\mathrm{Arrival[i]}=$ 駅 $i$ に（時刻表通りなら） $t$ までに到着する電車の中で、遅延を含めた到着が最も遅いものの時刻

出発イベント処理時:
- $X_i = \max(0, \mathrm{Arrival[A_i]}-S_i)$ とする
到着イベント処理時:
- $\mathrm{Arrival[B_i]} ← T_i+X_i$ とする（←はchmax）

これで、適切なタイミングを守って更新が実現できる。
出発イベントの時に到着点の $\mathrm{Arrival[B_i]}$ まで更新しようとしてしまうと、上手くいかない。

Python3

G - Add and Multiply Queries

問題文

長さ $N$ の正整数列 $A, B$ が与えられます。
以下の形式で与えられる $Q$ 個のクエリを、与えられた順番に処理してください。
クエリは次の $3$ 種類のいずれかです。
- タイプ $1$ : 1 i x の形式で与えられる。 $A_i$ を $x$ に置き換える。
- タイプ $2$ : 2 i x の形式で与えられる。 $B_i$ を $x$ に置き換える。
- タイプ $3$ : 3 l r の形式で与えられる。以下の問題を解き、答えを出力する。
  - はじめ $v = 0$ とする。 $i = l, l + 1, \dots ,r$ の順に、 $v$ を $v + A_i$ もしくは $v \times B_i$ で置き換える操作を行う。最終的な $v$ として実現できる最大値を求めよ。
ただし、入力で与えられるタイプ $3$ のクエリの答えは $10^{18}$ 以下であることが保証されています。

制約

$1 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq B_i \leq 10^9$
$1 \leq Q \leq 10^5$
タイプ $1$ , $2$ のクエリにおいて、 $1 \leq i \leq N$
タイプ $1$ , $2$ のクエリにおいて、 $1 \leq x \leq 10^9$
タイプ $3$ のクエリにおいて、 $1 \leq l \leq r \leq N$
タイプ $3$ のクエリにおいて、出力すべき値は $10^{18}$ 以下である

解法

ありがちな解法で考えると、セグメント木に $(A_i,B_i)$ なんかを乗せ、集約値の区間最大値を取得！としたいところだが、それまでの $v$ の値によって最適な選択が異なってくる。

Ai = 10,  Bi = 3

v=3 のとき v+10 = 13 > v*3 =  9    Aiの加算をした方がよい
v=9 のとき v+10 = 19 < v*3 = 30    Biの乗算をした方がよい

よって、セグメント木として「区間の集約値を前計算しておく」ができず、この方法は使えない。

※完全に使えないわけではなく、選択が変わる

$v$ の境界毎にいくつかの一次式を保持しておき、適切にマージすることで可能は可能。実装は重め。

解説 - 日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）

問題文最後の以下の条件を使用する。

タイプ $3$ のクエリの答えは $10^{18}$ 以下であることが保証されています。

出力すべき値が $10^{18}$ 以下ということは、区間に含まれる $B_i$ のうち $2$ 以上のものは60個以下ということになる。
$2^{60} \ge 10^{18}$ で2以上の数を60回かけると超えてしまうし、 $A_i$ の加算によっても $v$ は減らないので。

つまり、区間が長いクエリの時でも、区間内の $B_i$ の大半は $1$ が敷き詰められているということになる。

「1を乗算」は意味が無いので、 $B_i=1$ の時には必ず「 $A_i$ を加算」を選んでよい。そのような $i$ が連続していれば、 $A_i$ の区間和としてセグメント木でまとめて求められる。

結局、 $v=0$ から以下を繰り返せば良い。

$[l,r)$ の中で、最も左の $B_i \ge 2$ である位置 $i$ を取得
- 存在しない場合、 $A[l:r)$ の総和を $v$ に加算して終了
$[l,i)$ の範囲は、 $A_i$ を加算する方を選択する。 $A[l:i)$ の総和を $v$ に加算
$i$ は素直に比較して更新する。 $v←\max(v+A_i,v \times B_i)$
$l←i+1$ として最初に戻る

$A_i$ に対しては1点更新・区間和を求められるFenwickTreeやセグメント木などで管理。
$B_i$ に対しては、 $B_i \ge 2$ のindexのみを管理するSortedSetや、1点更新・区間maxのセグメント木などで管理し二分探索すればよい。

最大60回の繰り返しで、答えが求まる。計算量は $O(N \log{N} \log{(答えの制約上限)})$

なんか、感覚的に “クエリ” は “問い合わせ”、つまり「答えを知らないので教えて」という質問であることを想像するので、こういう風な「実は問う側が答えを分かってることを前提とした解法」は、ちょっと発想の外から殴られたような衝撃を感じる。

まぁ、「計算途中で $10^{18}$ を超えたら“overflow”を出力して」という仕様だったら別に問う側が知ってなくても成り立つし、そこから競技プログラミングの問題上、煩雑な部分を省略しただけとも捉えられるので、勝手な感覚ではあるんだけど。

Python3

        
          
          
              
              from operator import le, add
 
 
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
 
 
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
sgt_a = SegmentTreeInjectable.from_array(aaa, int, add)
sgt_b = SegmentTreeInjectable.from_array(bbb, int, max)
q = int(input())
buf = []
for _ in range(q):
    op, i, x = map(int, input().split())
    if op == 1:
        i -= 1
        sgt_a.update(i, x)
    elif op == 2:
        i -= 1
        sgt_b.update(i, x)
    else:
        v = 0
        i -= 1
        l, r = i, x
        while l < r:
            m = sgt_b.leftmost(l, r, 2, le)
            if m == -1:
                v += sgt_a.get_range(l, r)
                break
            if l < m:
                v += sgt_a.get_range(l, m)
            a = sgt_a.get_point(m)
            b = sgt_b.get_point(m)
            v = max(v + a, v * b)
            l = m + 1
        buf.append(v)
 
print('\n'.join(map(str, buf)))

            

        
      