arc 008 D - タコヤキオイシクナール (python)

k = 0 から順番に (A[k*2],B[k*2]), (A[k*2+1],B[k*2+1]) を (A[k*2]+B[k*2])*A[k*2+1]+B[k*2+1]
と計算していく問題。
セグ木を使うと、(A[k*2]*A[k*2+1], B[k*2]*A[k*2+1]+B[k*2+1]) の結果を (A[k], B[k])に保存できるので、求める答えは sum(A[1]+B[1]) となる。(1-indexed なら）
また、m個のクエリごとに (a, b) を一点更新すれば順番に答えが更新できるのでほぼ問題は解決する。
あと考えることは n の制約は大きすぎるので、m 個のクエリに登場する p を昇順ソートして、その p に対して何番目かに大きいかを対応させて m 個ちょっとのセグ木で処理すことぐらい。座圧の基本。

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
chk = []
s = set()
for i in range(m):
  p,a,b = input().split()
  p = int(p); a = float(a); b = float(b)
  chk.append((p,a,b))
  s.add(p)
  
L = len(s)
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc
                
    def update(self, k, r): #一点更新
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k*2], self.seg[k*2 + 1])
            
S = segment_(L,(1,0),lambda a,b :(a[0]*b[0],a[1]*b[0]+b[1]))

t = {}
s = sorted(list(s))
for i,si in enumerate(s):
  t[si] = i #座圧
  
mi = ma = 1
for p,a,b in chk:
  S.update(t[p]+1,(a,b)) # +1 しなくてもいい。1-indexed に統一したかったからつけた。
  x = sum(S.seg[1]) #出てきたタコヤキの美味しさ
  if x > ma:
    ma = x
  if x < mi:
    mi = x
    
print(mi)
print(ma)