累積minの一般化 - 競プロPythonのスニペット置き場

累積min(モノイドの端からの区間取得)

長さ $N$ の数列 $A$ 、集合 $G$ 、二項演算子 $*$ ( $(G,*)$ はモノイド)に対して、以下のことができる。

$O(N)$ 　前処理
$O(1)$ 　端からの区間取得

　　　　 $A_1\cdot A_2 \cdot \dots \cdot A_i~~(1\leq i\leq N)$
　　　　 $A_i \cdot A_{i+1} \cdot \dots \cdot A_N~~(1\leq i\leq N)$

モノイドは結合律・単位律を満たす。

ソースコード(二項演算子がminの場合)

from itertools import accumulate
class Acc:
    def __init__(self,l,f,unit):
        self.n,self.f,self.unit=len(l),f,unit
        self.lacc=list(accumulate(l,func=f))
        self.racc=list(accumulate(reversed(l),func=f))[::-1]
    def query(self,l,r):
        if r==None:
            if l==None:
                return self.lacc[-1]
            return self.racc[max(l,0)] if l<self.n else self.unit
        return self.lacc[min(r-1,self.n)] if 0<r else self.unit
    def __getitem__(self,i):    #[:r],[l:]
        return self.query(i.start,i.stop)
    def __str__(self):
        return str(self.lacc)+'\n'+str(self.racc)

###### Settings ######
_f=min              #二項演算子
_unit=float('inf')  #単位元
######################

a=[3,2,5,1,4]
acc=Acc(a,_f,_unit)

print(acc)      #累積minの状態の確認    左から >>[3, 2, 2, 1, 1]
                #                    右から >>[1, 1, 1, 1, 4]

print(acc[:3])  #a_0•a_1•a_2を取得           >>2
print(acc[2:])  #a_2*a_3*a_4を取得           >>1
print(acc[:])   #a_0*a_1*a_2*a_3*a_4を取得   >>1

print(acc[:9])  #jがはみ出る時j=len(a)に補正   >>1
print(acc[-1:]) #iがはみ出る時i=0に補正        >>1

min以外の例
####で囲まれた部分を変更すると使える。

###### Settings ######
_f=max              #二項演算子
_unit=-float('inf') #単位元
######################

###### Settings ######
from math import gcd
_f=gcd              #二項演算子
_unit=0             #単位元
######################

例題
ABC125C 累積gcd

ABC134C 累積max

参考記事
群の場合、端からでなくても累積値を $O(1)$ で取得できる。
k-penciler.hatenablog.com