結果

問題 No.878 Range High-Element Query
ユーザー ああいいああいい
提出日時 2022-04-19 18:24:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 554 ms / 2,000 ms
コード長 5,672 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 87,236 KB
実行使用メモリ 186,656 KB
最終ジャッジ日時 2023-08-30 16:27:56
合計ジャッジ時間 6,216 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 67 ms
71,284 KB
testcase_01 AC 115 ms
77,540 KB
testcase_02 AC 121 ms
77,656 KB
testcase_03 AC 109 ms
77,132 KB
testcase_04 AC 109 ms
77,300 KB
testcase_05 AC 108 ms
77,464 KB
testcase_06 AC 95 ms
77,300 KB
testcase_07 AC 91 ms
76,624 KB
testcase_08 AC 109 ms
77,460 KB
testcase_09 AC 112 ms
77,452 KB
testcase_10 AC 86 ms
76,408 KB
testcase_11 AC 504 ms
159,636 KB
testcase_12 AC 454 ms
173,540 KB
testcase_13 AC 404 ms
138,124 KB
testcase_14 AC 343 ms
126,064 KB
testcase_15 AC 423 ms
160,360 KB
testcase_16 AC 523 ms
184,732 KB
testcase_17 AC 542 ms
183,892 KB
testcase_18 AC 554 ms
186,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


class SegTree:
    #単位元と結合演算はここ変える
    #いろんな種類のsegは作れないかも
    #→changeで変えれる
    
    unit = -1
    def f(self,x,y):
        return max(x,y)

    #頂点は1-index、一番下の段は0-index(bitは1-index)
    def __init__(self,N):
        self.N = N
        self.X = [self.unit] * (N + N)
    def build(self,seq):
        for i,x in enumerate(seq,self.N):
            self.X[i] = x
        for i in range(self.N-1,0,-1):
            self.X[i] = self.f(self.X[i << 1],self.X[i << 1 | 1])
    def set(self,i,x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.f(self.X[i << 1],self.X[i << 1 | 1])
    def fold(self,L,R):
        #区間[L,R)についてfold
        #0 <= L,R <= N にしなきゃダメ
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.f(vL,self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.X[R],vR)
            L >>= 1
            R >>= 1
        return self.f(vL,vR)
    def change(self,f,unit):
        self.f = f
        self.unit = unit



#WaveletMatrix

class BitVector():
    def __init__(self,A):
        self.n = len(A)
        SA = [0] * (self.n + 1)
        for i,a in enumerate(A):
            SA[i+1] = SA[i] + a
        self.SA = SA
    def rank1(self,r):
        return self.SA[r]
    def rank0(self,r):
        return r - self.SA[r]
    def select0(self,k):
        l,r = 0,len(self,SA)
        if not k < r - 1 - self.SA[r-1]:
            return -1
        while r - l > 1:
            m = l + r >> 1
            if m - self.SA[m] <= k:
                l = m
            else:
                r = m
        return l
    def select1(self,k):
        l,r = 0,len(self.SA)
        if not k < self.SA[r-1]:
            return -1
        while r - l > 1:
            m = l + r >> 1
            if self.SA[m] <= k:
                l = m
            else:
                r = m
        return l

class WaveletMatrix():

    # s: word size. Ai <= 10**6 なら 20
    #   Ai <= 10**9 なら　30 ぐらいで
    # (word size < 1 << s となるよう)
    def __init__(self,s,A):
        self.s = s
        self.A = A
        self.n = len(A)
        self.X = []
        B = A.copy()
        for i in reversed(range(s)):
            mask = 1 << i
            L = []
            R = []
            T = []
            for a in B:
                if a & mask:
                    T.append(1)
                    R.append(a)
                else:
                    T.append(0)
                    L.append(a)
            vb = BitVector(T)
            self.X.append((vb.rank0(self.n),vb))
            B = L + R
        self.X = self.X[::-1]
    def access(self,i):
        return self.A[i]
    # A[l,r)内のvalueの数を求める 
    def rank(self,l,r,value):
        if l >= r:return 0
        for i in reversed(range(self.s)):
            z,vb = self.X[i]
            if value >> i & 1:
                l = z + vb.rank1(l)
                r = z + vb.rank1(r)
            else:
                l = vb.rank0(l)
                r = vb.rank0(r)
        return r - l
    def select(self,value,k):
        #A内のk番目のvalueのindexを返す
        #value が k個なければ-1を返す
        if self.rank(0,self.n,value) <= k:return -1
        ind = 0
        for i in reversed(range(self.s)):
            z,v = self.X[i]
            if value >> 1 & 1:
                ind = z + vb.rank1(ind)
            else:
                ind = vb.rank0(int)
        ind += k
        for i in range(self.s):
            z,vb = self.X[i]
            if ind < z:
                ind = vb.select0(ind)
            else:
                ind = vb.select1(ind-z)
        return ind

    def freq_to(self,l,r,value):
        # 0 <= A[i] < value な　数を求める
        if not value:return 0
        if l >= r:return 0
        ret = 0
        for i in reversed(range(self.s)):
            z,vb = self.X[i]
            if value >> i & 1:
                ret += vb.rank0(r) - vb.rank0(l)
                l = z + vb.rank1(l)
                r = z + vb.rank1(r)
            else:
                l = vb.rank0(l)
                r = vb.rank0(r)
        return ret
    
    def freq(self,l,r,d,u):
        # d <= A[i] < u なる数を求める
        if d >= u:return 0
        return self.freq_to(l,r,u) - self.freq_to(l,r,d)

    def quantile(self,l,r,k):
        # [l,r) のk番目に小さい数の返す
        # k: 0-index k = 0で一番小さい数を返す
        if k >= r - l:return -1
        ret = 0
        for i in reversed(range(self.s)):
            z,vb = self.X[i]
            zeros = vb.rank0(r) - vb.rank0(l)
            if zeros > k:
                l = vb.rank0(l)
                r = vb.rank0(r)
            else:
                k -= zeros
                ret |= 1 << i
                l = z + vb.rank1(l)
                r = z + vb.rank1(r)
        return ret
    def quantile2(self,l,r,k):
        #[l,r)のk番目に大きい数を返す
        # k: 0-index
        return self.quantile(l,r,r-l-k-1)

import sys
rr = sys.stdin
N,Q = map(int,rr.readline().split())
a = list(map(int,rr.readline().split()))
seg = SegTree(N + 1)
l = [0] * N
for i in range(N):
    l[i] = seg.fold(a[i],N+1) + 1
    """
    if tmp != -1:
        l[i] = tmp + 1
    else:
        l[i] = 0
    """
    seg.set(a[i],i)
wm = WaveletMatrix(20,l)
for _ in range(Q):
    s,ll,r = map(int,rr.readline().split())
    ans = wm.freq_to(ll-1,r,ll)
    print(ans)
0