結果

問題 No.1394 Changing Problems
ユーザー chineristACchineristAC
提出日時 2020-09-08 00:42:45
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,540 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 86,688 KB
実行使用メモリ 142,868 KB
最終ジャッジ日時 2023-09-18 02:39:19
合計ジャッジ時間 13,705 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 WA -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 AC 443 ms
116,568 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,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.num = 1<<self.n
        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(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        self.lazy[v]=self.operate_unit
        self.data[2*v]=self.operate(self.data[2*v],ope)
        self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
        self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
        self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

    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.merge_operate(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.merge_operate(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

    def bisect_l(self,l,r,x):
        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)
        Lmin = -1
        Rmin = -1
        while l<r:
            if l & 1:
                if self.data[l] <= x and Lmin==-1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.data[r-1] <=x:
                    Rmin = r-1
            l >>= 1
            r >>= 1

        if Lmin != -1:
            pos = Lmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            return pos-self.num
        elif Rmin != -1:
            pos = Rmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            return pos-self.num
        else:
            return -1


import sys,heapq
from operator import add

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,min,(10**18,-1),lambda x,y:(x[0]+y,x[1]),add,0)

    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:
                t1_q, t1_r = lower_q+1-Qsum, LST.bisect_l(0,lower_r,lower_q-Qsum)

            t2_q,t2_r = LST.query(lower_r,N-1)
            if t2_r != -1 and  t2_q + Qsum  < lower_q:
                t2_q,t2_r = lower_q-Qsum,LST.bisect_l(lower_r,N-1,lower_q-Qsum-1)

            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