結果

問題 No.1394 Changing Problems
ユーザー chineristACchineristAC
提出日時 2020-09-07 13:41:28
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,704 bytes
コンパイル時間 235 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 135,104 KB
最終ジャッジ日時 2024-07-04 19:23:54
合計ジャッジ時間 12,447 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 WA -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 AC 249 ms
106,368 KB
testcase_07 RE -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 WA -
testcase_14 RE -
testcase_15 WA -
testcase_16 RE -
testcase_17 RE -
testcase_18 WA -
testcase_19 WA -
testcase_20 RE -
testcase_21 WA -
testcase_22 RE -
testcase_23 RE -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 RE -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

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,heapq

input = sys.stdin.readline

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

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

    for i in range(N):
        a = A[i]
        q = (a+1) // (N-1)
        r = (a+1) % (N-1)
        init[r] += 1
        Qsum += q
        heapq.heappush(Max_que,(-a,i))

    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
            heapq.heappush(Max_que,(-x,i))

        else:
            while -Max_que[0][0] != A[Max_que[0][1]]:
                heapq.heappop(Max_que)

            lower = -Max_que[0][0] - (N-2)

            if lower<=0:
                print(0)
                continue

            lower_q = lower//(N-1)
            lower_r = lower%(N-1)

            t1_q,t1_r = LST.query(0,lower_r)
            if t1_r != -1 and  t1_q + Qsum  <= lower_q:
                start = -1
                end = lower_r-1
                while end-start>1:
                    test = (end + start) // 2
                    if LST.query(0,test+1)[0] + Qsum <= lower_q:
                        end = test
                    else:
                        start = test
                t1_q, t1_r = lower_q+1-Qsum, end

            t2_q,t2_r = LST.query(lower_r,N-1)
            if t2_r != -1 and  t2_q + Qsum  < lower_q:
                start = lower_r-1
                end = N-2
                while end-start>1:
                    test = (end + start) // 2
                    if LST.query(lower_r,test+1)[0] + Qsum < lower_q:
                        end = test
                    else:
                        start = test
                t2_q,t2_r = lower_q-Qsum,end

            res = min((t1_q + Qsum) * (N-1) + t1_r ,(t2_q + Qsum) * (N-1) +t2_r)
            assert(res>=lower)
            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