結果

問題 No.1394 Changing Problems
コンテスト
ユーザー chineristAC
提出日時 2020-09-07 01:20:27
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,343 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 117,388 KB
最終ジャッジ日時 2024-07-04 19:22:36
合計ジャッジ時間 11,005 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 2
other WA * 18 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegmentTree():
    def __init__(self,n,init,merge=min,merge_unit=(10**18,-1),operate=lambda x,y:(x[0]+y,x[1]),operate_unit=0):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            add=self.lazy[v]
            self.lazy[v]=self.operate_unit
            self.data[2*v]=self.operate(self.data[2*v],add)
            self.data[2*v+1]=self.operate(self.data[2*v+1],add)
            self.lazy[2*v]=self.lazy[2*v] + add
            self.lazy[2*v+1]=self.lazy[2*v+1] + add


    def remerge_above(self,i):
        while i:
            i>>=1
            self.data[i]=self.operate(self.merge(self.data[2*i],self.data[2*i+1]),self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.lazy[l] + x
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.lazy[r-1] + x
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        while l<r:
            if l&1:
                res=self.merge(res,self.data[l])
                l+=1
            if r&1:
                res=self.merge(res,self.data[r-1])
            l>>=1
            r>>=1
        return res

import sys

input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))

def solve_not_one():
    init = [0]*(N-1)
    Qsum = 0

    for a in A:
        q = (a+1) // (N-1)
        r = (a+1) % (N-1)
        init[r] += 1
        Qsum += q

    for i in range(1,N-1):
        init[i] += init[i-1]

    init = [(i-init[i],i) for i in range(N-1)]
    LST = LazySegmentTree(N-1,init)

    Q = int(input())
    for _ in range(Q):
        query = tuple(map(int,input().split()))
        if query[0] == 1:
            gomi,i,x = query
            i -= 1

            Qsum -= (A[i]+1) // (N-1)
            Qsum += (x+1) // (N-1)

            pre_r = (A[i]+1) % (N-1)
            LST.update(pre_r,N-1,1)

            next_r = (x+1) % (N-1)
            LST.update(next_r,N-1,-1)

            A[i] = x

        else:
            q,r = LST.query(0,N-1)
            res = (N-1) * (Qsum + q) + r
            print(res)

def solve_one():
    Q = int(input())
    for _ in range(Q):
        query = tuple(map(int,input().split()))
        if query[0] == 1:
            A[0] = query[2]
        else:
            print(A[0]+1)

if N==1:
    solve_one()
else:
    solve_not_one()
0