結果

問題 No.2809 Sort Query
ユーザー navel_tosnavel_tos
提出日時 2024-07-13 00:38:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,445 ms / 2,000 ms
コード長 3,464 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 274,136 KB
最終ジャッジ日時 2024-07-13 00:39:36
合計ジャッジ時間 78,993 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 71
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 2809 Sort Query

#Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, N): self._N, self.bit = N, [0] * (N + 1)
    def build(self, A):  #O(N)で構築
        C = [0] * (self._N + 1)
        for i in range(self._N): C[i + 1] = C[i] + A[i]
        for e in range( self._N.bit_length() ):
            d = 1 << e
            for L in range(0, self._N + 1 - d, d << 1): self.bit[L + d] = C[L + d] - C[L]
    def add(self, i, x):  #A[i] += x
        i += 1
        while i <= self._N: self.bit[i] += x; i += i & - i
    def sum(self, i):  #sum(A[0, 1, ･･･ , i])
        ans, i = 0, i + 1
        while i > 0: ans += self.bit[i]; i -= i & - i
        return ans
    def fold(self, Lt, Rt):  #半開区間A[Lt: Rt)の和
        ans = 0
        while Lt != Rt:
            if Lt > Rt: ans -= self.bit[Lt]; Lt -= Lt & - Lt
            else:       ans += self.bit[Rt]; Rt -= Rt & - Rt
        return ans
    #down: Falseなら単調増加、Trueなら単調減少を仮定する。
    #sum(i)の作用値がX以上/以下となる、最小のiを返す
    def bisect(self, X, down = False):
        b = (self._N + 1).bit_length() - 1; i, d = 1 << b, 1 << (b - 1); cnt = 0
        for b in range(b, -1, -1):
            if i > self._N: i -= d; d >>= 1
            elif not down and cnt + self.bit[i] >= X: i -= d; d >>= 1
            elif     down and cnt + self.bit[i] <= X: i -= d; d >>= 1
            elif b == 0: return i
            else: cnt += self.bit[i]; i += d; d >>= 1
        return i - 1


#入力受取  座標圧縮
N, Q = map(int, input().split())
A = list(map(int, input().split()))
D = A[:]
query = [None] * Q
for q in range(Q):
    t, *k = map(int, input().split())
    if t == 1:
        k, x = k
        query[q] = (t, k - 1, x)
        D.append(x)
    if t == 2:
        query[q] = (t, 0, 0)
    if t == 3:
        k = k[0]
        query[q] = (t, k - 1, 0)
D.sort()
nD = []
for d in D:
    if len(nD) == 0 or nD[-1] != d:
        nD.append(d)
D = nD
E = {j: i for i, j in enumerate(D)}
n = len(E)
A = [E[i] for i in A]
ans = []
R = [-1] * Q
for q, (t, k, x) in enumerate(query):
    if t == 1:
        query[q] = (t, k, E[x])
    if t == 3:
        ans.append(-1)
        R[q] = len(ans) - 1

#ソートの影響を受けないものと、ソートの影響を受ける場合は何回目のソートか調べる
B = A[:]
S = set(range(N))
X = []
for q, (t, k, x) in enumerate(query):
    if t == 1:
        B[k] = x
        S.add(k)
    if t == 2:
        S.clear()
        X.append([])
    if t == 3:
        if k in S:
            ans[R[q]] = B[k]
        else:
            X[-1].append((R[q], k))

#X[ソート回数]: (ansのindex, ソート順でk個目)
BIT = BinaryIndexedTree(n)
B = [0] * n
for Ai in A:
    B[Ai] += 1
BIT.build(B)
cnt = -1
diff = dict()
for q, (t, k, x) in enumerate(query):
    if t == 1:
        if cnt == -1:
            BIT.add(A[k], -1)
            A[k] = x
            BIT.add(A[k], +1)
        else:
            diff[k] = x  #変更フォルダに保存
    if t == 2:
        #1. 変更を保存
        if cnt >= 0:
            diff2 = dict()
            for k in diff:
                diff2[k] = BIT.bisect(k + 1)
            for k in diff:
                BIT.add(diff[k], +1)
                BIT.add(diff2[k], -1)
        cnt += 1
        diff = dict()

        #2. クエリに回答
        for q, k in X[cnt]:
            ans[q] = BIT.bisect(k + 1)

for i in ans: print(D[i])
0