#994712 (PyPy3) No.2809 Sort Query

• 問題: No.2809 Sort Query
• ユーザー: navel_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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#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])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX