#876178 (PyPy3) No.2333 Slime Structure

提出ソース
結果

問題	No.2333 Slime Structure
コンテスト
ユーザー	navel_tos
提出日時	2023-05-31 01:03:14
言語	PyPy3 (7.3.15)
結果	MLE (最新) AC (最初)
実行時間	-
コード長	6,980 bytes
コンパイル時間	1,045 ms
コンパイル使用メモリ	82,176 KB
実行使用メモリ	555,380 KB
最終ジャッジ日時	2024-12-28 13:29:08
合計ジャッジ時間	70,041 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 30 MLE * 1
権限があれば一括ダウンロードができます
ソースコード

raw source code
#MMA Contest 015 L Slime Structure

'''
残り2問。Kは難しそうなのでLから(?)

■ABC303D　Shift vs. CapsLock
aとAだけで構成された文字列Sがある。a,Shift+a,CapsLockだけで、最短で文字列Sを完成させろ。
Reference: https://atcoder.jp/contests/abc303/tasks/abc303_d

┏━━━━━━━┓┏━━━━┓  これの想定解はDPで、DP[i][j]: i文字目をCaps状態jで入力する
┃Shift         ┃┃Caps    ┃  最短の時間 としてDPを回せばよいのだが、どうやらこの問題は
┃  ┏━━━┓  ┃┃Lock    ┃  SegTreeに乗せることで、区間クエリ[L,R]あたりO(logN)で回答
┃  ┃  a   ┃  ┃┃        ┃  することができるらしい。
┃  ┗━━━┛  ┃┃        ┃  本問も同様の手法で解けるのではないだろうか。
┗━━━━━━━┛┗━━━━┛
Reference: https://twitter.com/simasimasukiyo/status/1662630417193930754?s=20


■考察
区間分割しないときつそうではある。
区間全幅を使うか、区間の左端だけを使うか、区間の右端だけを使うか、
みたいな感じでのり付けしていくのがベターかな。
区間を√Nで分割するとして、1回あたりの計算量はO(√N)くらいで収まりそう 多分

問題はクエリ1、一生更新するな
O(√N)で更新可能、それはそう。

連長圧縮されたスライムを、クエリ1で変更されるスライムで切断しておけばいいか。
とりあえずO(Q√N)には収まる、が、制約がN<10^5でありスライム切断クエリで実質的に
Nが増加することを考えるとかなり怪しい。
できればセグ木に乗せておきたい。

クエリ1で切断するぶんで区切っておき、セグ木には
1. 区間左端からの最大部分配列
2. 区間右端からの最大部分配列
3. 区間全域内での最大部分配列
4. 区間総和
を格納しておく必要がありそうだ。

そもそもこれ区間合成可能なの？
1. これらはたぶん大丈夫。採用区間左端/右端の最大部分配列を使うか、
2. それに隣の区間総和を足したものを比較すればよい。
   違うな、区間全域と隣の左端、あるいは区間右端と隣の全域、のどちらかだ。
   じゃあ区間全域を保持しないとだめか。
3. 区間またぎの有無で分ければいいか。
   区間内最大か、区間右端と隣の左端の合成値のどちらかだろう。
4. わろす

ただ今回の制約だとどれも値が爆発するので、
Python的には残念だが、これらはすべてtuple型で保持しないとだめそうだ。
苦しい。

クエリ2を手動で解いてもいいが、それするくらいなら全てSegTreeに乗せてしまえ。
'''
#Segment Tree: O(logN)
class SegmentTree:                                    # Segment Tree
    def __init__(self,n,identity_e,combine_f):        # 適応条件: 単位元eがある、互換可能
        self._n=n; self._size=1                       # モノイド(単位元)の例:
        while self._size<self._n:self._size<<=1       #  足し算 0, かけ算 1, 最小 INF,
        self._identity_e=identity_e                   #  最大 -INF, LCM(最小公倍数) 1
        self._combine_f=combine_f                     #
        self._node=[self._identity_e]*2*self._size    # combine_f には関数を指定する
                                                      # def文で関数を自作してもいいし、
    def build(self,array):                            #  from operator import xor
        assert len(array)==self._n,'array too large'  # のようにimportしてもよい
        for i,v in enumerate(array,start=self._size): #
            self._node[i]=v                           # build: セグ木を建てる
        for i in range(self._size-1,0,-1):            # 異常時はassert関数でエラーを報告
            self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
                                                      #
    def update(self,index,value):                     # update: 一点更新 O(logN)
        i=self._size+index; self._node[i]=value       # 地点i(0-indexed)を更新する
        while i-1:                                    # 同時に上位のセグメントも更新する
            i>>=1                                     #
            self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
                                                      #
    def fold(self,L,R):                               # fold: 区間取得 O(logN)
        L+=self._size; R+=self._size                  # 区間 [L,R) の特定値を取得する
        vL,vR=[self._identity_e]*2                    #
        while L<R:                                    # nodeの遷移の考え方
            if L&1:                                   #  ---1---  L: 自身より右の最小
                vL=self._combine_f(vL,self._node[L])  #  -2- -3-  R: 自身-1より左の最小
                L+=1                                  #  4 5 6 7  Rは計算より先に-1の
            if R&1:                                   #           処理をする点に注意
                R-=1                                  # R---1---L
                vR=self._combine_f(self._node[R],vR)  # R-2- LLL. 例: L=6, R=5
            L>>=1; R>>=1                              # .R.5 L 7      Rの移動が変則的
        return self._combine_f(vL,vR)                 #  ←R L→


#SegTree用の関数を定義  node: (区間左端,右端,区間内 の最大スコア, 区間総長)を格納
f_n=lambda n,m:(max(n[0],n[3]+m[0]),max(m[1],n[1]+m[3]),max(n[2],m[2],n[1]+m[0]),n[3]+m[3])

import heapq as hq
f=lambda:list(map(int,input().split()))

#入力受取
N=int(input()); Slime=[f() for _ in range(N)]; Len=[]; total=0; INF=10**18
Q=int(input()); Tasks=[f() for _ in range(Q)]; Cut=[INF]

#スライムの分割箇所を決定
for t,L,R in Tasks:
    if t==1: hq.heappush(Cut,L-1); hq.heappush(Cut,L)
    if t==2: hq.heappush(Cut,L-1); hq.heappush(Cut,R)

#実際にスライムを分割
for attack,num in Slime:
    while num and Cut[0]<=total+num:
        if Cut[0]<=total: hq.heappop(Cut); continue
        X=Cut[0]-total; Len.append((attack,X)); num-=X; total+=X; hq.heappop(Cut)
    if num: Len.append((attack,num)); total+=num
    
#セグ木に乗せる準備 ノード作成と連想配列を用意
D=dict(); Unit=[(0,0,0,0)]; total=0; D[0]=0
for index,(attack,num) in enumerate(Len,start=1):
    if attack>=0: Unit.append(tuple(attack*num for _ in range(4)))
    else: Unit.append((attack,attack,attack,attack*num))
    total+=num; D[total]=index
ST=SegmentTree(len(Unit),(-INF,-INF,-INF,0),f_n); ST.build(Unit)

#クエリを処理
for t,L,R in Tasks:
    if t==1: ST.update(D[L],(R,R,R,R))
    if t==2: print(ST.fold(D[L-1]+1,D[R]+1)[2])
yukicoder

結果

ソースコード
