結果

問題 No.3059 Range Tournament
ユーザー chineristAC
提出日時 2025-03-14 22:29:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,018 ms / 4,000 ms
コード長 4,689 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 260,256 KB
最終ジャッジ日時 2025-03-14 22:31:02
合計ジャッジ時間 67,209 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,time

from itertools import permutations
from heapq import heappop,heappush
from collections import deque
import random
import bisect
from math import ceil,floor

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.size = n
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1])

    def query(self, l, r):
        if r==self.size:
            r = self.num

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r-1])
            l >>= 1
            r >>= 1

        return res
    
class SparseTable():
    def __init__(self,A,merge_func,ide_ele):
        N = len(A)
 
        self.merge_func = merge_func
 
        self.lg = [0]*(N + 1)
        for i in range(2, N+1):
            self.lg[i] = self.lg[i >> 1] + 1
        self.pow_2 = [pow(2,i) for i in range(20)]
 
        self.table = [None]*(self.lg[N] + 1)
        st0 = self.table[0] = [a for a in A]
        b = 1
        for i in range(self.lg[N]):
            st0 = self.table[i+1] = [self.merge_func(u,v) for u, v in zip(st0, st0[b:])]
            b <<= 1
 
    def query(self,s,t):
        b = t-s+1
        m = self.lg[b]
        return self.merge_func(self.table[m][s],self.table[m][t-self.pow_2[m]+1])

def solve(N,P,Q,query):
    K = 20
    imos = [[0]*(N+1) for k in range(K)]

    res = [0] * N

    seg = SegmentTree(P,max,-1)

    ST = SparseTable(P,max,-1)

    for l,r in query:
        l,r,k = l,r,0
        amari = []

        imos[0][l] -= 1
        imos[0][r] += 1

        while True:
            imos[k][l] += 1
            imos[k][r] -= 1

            #print(l,r,k,amari)

            if not amari:
                n = (r-l)>>k
                if n == 1:
                    break

                if n & 1 == 0:
                    k += 1
                else:
                    res[ST.query(l,l+(2<<k)-1)] += 1
                    amari = [ST.query(l,l+(2<<k)-1), ST.query(r-(1<<k),r-1)]
                    l,r = l+(2<<k),r-(1<<k)
                    k += 1
            else:

                res[max(amari)] += 1


                n = ((r-l)>>k) + 1
                if n == 1:
                    break

                if n & 1 == 0:
                    amari.append(seg.query(r-(1<<k),r))
                    l,r = l,r-(1<<k)
                    k += 1
                else:
                    res[ST.query(l,l+(2<<k)-1)] += 1
                    amari.append(ST.query(l,l+(2<<k)-1))
                    l,r = l+(2<<k),r
                    k += 1
    
    
    for k in range(K):
        for i in range(N):
            if i+(1<<k) <= N:
                imos[k][i+(1<<k)] += imos[k][i]
        
        for i in range(N-(1<<k)+1):
            idx = ST.query(i,i+(1<<k)-1)
            res[idx] += imos[k][i]
    
    return res

def solve_brute(N,P,Q,query):
    res = [0] * N
    for l,r in query:
        A = deque(P[l:r])
        while len(A) > 1:
            a = A.popleft()
            b = A.popleft()
            res[max(a,b)] += 1
            A.append(max(a,b))
    
    return res

while False:
    #N = random.randint(2,20)
    N = 2 * 10**5
    P = [i for i in range(N)]
    random.shuffle(P)

    #Q = random.randint(2,20)
    Q = 2 * 10**5
    query = []
    for i in range(Q):
        l = random.randint(0,N-1)
        r = random.randint(l+1,N)
        query.append((l,r))
    
    #exp = solve_brute(N,P,Q,query)
    res = solve(N,P,Q,query)
    print(sum(res))
    continue

    if exp!=res:
        print("WA")
        print(N,Q)
        print(P)
        print(query)
        print(exp)
        print(res)
        break
    else:
        print("AC",N,Q,sum(exp))
    

        

N = int(input())
P = [int(p)-1 for p in input().split()]
Q = int(input())
query = []
for _ in range(Q):
    l,r = mi()
    query.append((l-1,r))

print(*solve(N,P,Q,query),sep="\n")
0