結果

問題 No.3059 Range Tournament
ユーザー SPD_9X2
提出日時 2025-01-11 23:13:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,884 ms / 4,000 ms
コード長 12,708 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 152,656 KB
最終ジャッジ日時 2025-01-11 23:15:28
合計ジャッジ時間 81,074 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #

"""

速度チェック


https://yukicoder.me/problems/11172

小さいほうから考える?
1は勝つことは無いので0

2は、1と試合できる回数だけ

あるiについて、試合回数を考える
小さいのを x 大きいのをYとする

xx -> x
xY -> Y
YY -> Y

どれに負けるかを考えるのは難しいので、気合の高速化かもしれない



winner(l,r) = (l,r)の勝者を計算
とすると、純粋に区間maxである。

l,rの区間内部だけで対戦が終結する回数を数えたい
call(l,r) = l,rのトーナメントが終結する回数
上に当てはまらないものは、個別に計算?


2冪の区間トーナメントは行われる回数が非常に多い
ので、そこだけをまとめて集計すれば解けそう

call(l,2^k) = l左端で、2^k人の完全トーナメントを行う回数
で解けるかな


実装がむずい


-------

2冪はどうやって解くか?
call(l,2^k) = l左端で、2^k人の完全トーナメントを行う回数
とする?

トーナメントの上から伝播させていけばOK


一般の場合を考えると
    7
  7   6
 7 2 4 6
12 34 56 7

奇数の場合
最初2個,最後
それ以外でsolve?

    9
   6 9
  8 9 6
 9 2 4 6 8
12 34 56 78 9
違うな・・・

いい感じに分割できるのはわかるけど
分割法がよくわからない

最初の2コ、X、 最後
として、Xを再帰的に分割する?
   
   A B
  B 6 A
 B2 46 8A
12 34 56 78 9A B
-> B6が生まれてしまっている・・・

算数ができなさ過ぎて不可能です

--------------

シミュレーションして規則性を見るか?

1 [0]
2 [1, 1]
3 [1, 1, 2]
4 [3, 3, 3, 3]
5 [1, 1, 3, 3, 4]
6 [3, 3, 3, 3, 5, 5]
7 [1, 1, 5, 5, 5, 5, 6]
8 [7, 7, 7, 7, 7, 7, 7, 7]
9 [1, 1, 5, 5, 5, 5, 7, 7, 8]
10 [3, 3, 3, 3, 7, 7, 7, 7, 9, 9]
11 [1, 1, 5, 5, 5, 5, 9, 9, 9, 9, 10]
12 [7, 7, 7, 7, 7, 7, 7, 7, 11, 11, 11, 11]
13 [1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 11, 11, 12]
14 [3, 3, 3, 3, 11, 11, 11, 11, 11, 11, 11, 11, 13, 13]
15 [1, 1, 5, 5, 5, 5, 13, 13, 13, 13, 13, 13, 13, 13, 14]
16 [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15]
17 [1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 13, 13, 13, 13, 15, 15, 16]
18 [3, 3, 3, 3, 11, 11, 11, 11, 11, 11, 11, 11, 15, 15, 15, 15, 17, 17]
19 [1, 1, 5, 5, 5, 5, 13, 13, 13, 13, 13, 13, 13, 13, 17, 17, 17, 17, 18]
20 [7, 7, 7, 7, 7, 7, 7, 7, 15, 15, 15, 15, 15, 15, 15, 15, 19, 19, 19, 19]
21 [1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 17, 17, 17, 17, 17, 17, 17, 17, 19, 19, 20]
22 [3, 3, 3, 3, 11, 11, 11, 11, 11, 11, 11, 11, 19, 19, 19, 19, 19, 19, 19, 19, 21, 21]
23 [1, 1, 5, 5, 5, 5, 13, 13, 13, 13, 13, 13, 13, 13, 21, 21, 21, 21, 21, 21, 21, 21, 22]
24 [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 23, 23, 23, 23, 23, 23, 23, 23]
25 [1, 1, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 21, 21, 21, 21, 23, 23, 24]
26 [3, 3, 3, 3, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 23, 23, 23, 23, 25, 25]
27 [1, 1, 5, 5, 5, 5, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 25, 25, 25, 25, 26]
28 [7, 7, 7, 7, 7, 7, 7, 7, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 27, 27, 27, 27]
29 [1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 27, 27, 28]
30 [3, 3, 3, 3, 11, 11, 11, 11, 11, 11, 11, 11, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 29, 29]
31 [1, 1, 5, 5, 5, 5, 13, 13, 13, 13, 13, 13, 13, 13, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 30]
32 [31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31]

一応規則性は掴めたか
立っているbit分を左からまとめていけばいい
ただし、初手は右端

いや、なんか違うな 10は?
愚直にシミュレーションすればいい?
うーん


1 1 [0]
2 10 [0, 0]
3 11 [0, 0, 2]
4 100 [0, 0, 0, 0]
5 101 [0, 0, 2, 2, 4]
6 110 [0, 0, 0, 0, 4, 4]
7 111 [0, 0, 2, 2, 2, 2, 6]
8 1000 [0, 0, 0, 0, 0, 0, 0, 0]
9 1001 [0, 0, 2, 2, 2, 2, 6, 6, 8]
10 1010 [0, 0, 0, 0, 4, 4, 4, 4, 8, 8]
11 1011 [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 10]
12 1100 [0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8]
13 1101 [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 10, 10, 12]
14 1110 [0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 12, 12]
15 1111 [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 14]
16 10000 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
17 10001 [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 10, 10, 10, 10, 14, 14, 16]
18 10010 [0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 12, 12, 12, 12, 16, 16]
19 10011 [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 14, 14, 14, 14, 18]
20 10100 [0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16]
21 10101 [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 10, 10, 10, 10, 10, 10, 10, 10, 18, 18, 20]
22 10110 [0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 12, 12, 12, 12, 12, 12, 12, 12, 20, 20]
23 10111 [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 14, 14, 14, 14, 14, 14, 14, 14, 22]
24 11000 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 16, 16, 16, 16, 16, 16, 16]
25 11001 [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 18, 18, 18, 18, 22, 22, 24]
26 11010 [0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 20, 20, 20, 20, 24, 24]
27 11011 [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 22, 22, 22, 22, 26]
28 11100 [0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 24, 24, 24, 24]
29 11101 [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 26, 26, 28]
30 11110 [0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 28, 28]
31 11111 [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 30]
32 100000 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


生成過程に注目するのか…?
結論から逆操作ができればOK
とりあえずサイズの推移は計算できる

21 = 10101 でやってみよう。
21 -> 11 -> 6 -> 3 -> 2 -> 1 
   1      1    0    1   0

-> 11010 と変換できる
   
長さ表 [0,1,2,4,8,16,...] とする。
カーソルは、最初最後の要素の前にあるとする。
- 1の時 -> 長さ表のindexを1進める。カーソルの右から長さ分取る。
- 0の時 -> カーソルの左から現在の長さを取る。
が正解か? 21の場合は正しい

22 -> 11 -> 6 -> 3 -> 2 -> 1 
   0     1    0    1    0
正しくない


--------------------------------------------

逆操作をシミュレーションする?

21 -> 11010

A
AB
BC/A (B->BCと分離)
BbCc/Aa
bbbbCCccAAaa/B
bbbbbbCCCCccccAAAAaaaa/BBb

1
2
2,1
4,2
2,4,4,1
2,8,8,2,1
21 10101 [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 10, 10, 10, 10, 10, 10, 10, 10, 18, 18, 20]

これを行えばいいか

"""

import sys
from collections import deque

#0-indexed , 半開区間[a,b)
#calc変更で演算変更
class SegTree:

    def __init__(self,N,first):
        self.NO = 2**(N-1).bit_length()
        self.First = first
        self.data = [first] * (2*self.NO)

    def calc(self,l,r):
        return max(l,r)

    def update(self,ind,x):
        ind += self.NO - 1
        self.data[ind] = x
        while ind >= 0:
            ind = (ind - 1)//2
            self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2])

    def query(self,l,r):
        L = l + self.NO
        R = r + self.NO
        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s , self.data[R-1])
            if L & 1:
                s = self.calc(s , self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self , ind):
        ind += self.NO - 1
        return self.data[ind]

# 借りました
class SparseTable:
    def __init__(self, A, op):
        self.n = len(A)
        logn = (self.n - 1).bit_length()
        if self.n == 1:
            logn = 1
        self.op = op
        self.table = [None] * (self.n * logn)
        for i in range(self.n):
            self.table[i] = A[i]
        for i in range(1, logn):
            ma = self.n - (1 << i) + 1
            d = 1 << (i - 1)
            for j in range(ma):
                self.table[i * self.n + j] = op(self.table[(i - 1) * self.n + j], self.table[(i - 1) * self.n + j + d])

    def prod(self, l, r):
        d = r - l
        if d == 1:
            return self.table[l]
        logn = (d - 1).bit_length() - 1
        return self.op(self.table[logn * self.n + l], self.table[logn * self.n + r - (1 << logn)])


class DSU():

    def __init__(self, n:int):

        self.n = n
        self.p = [i for i in range(n)]
        self.rank = [i for i in range(n)]
        self.sizelis = [1] * n

    def leader(self,a):
        stk = []
        while self.p[a] != a:
            stk.append(a)
            a = self.p[a]
        for v in stk:
            self.p[v] = a
        return a

    def merge(self, a, b):
        ap = self.leader(a)
        bp = self.leader(b)
        if ap == bp:
            return ap

        if self.rank[ap] > self.rank[bp]:
            self.p[bp] = ap
            self.sizelis[ap] += self.sizelis[bp]
        elif self.rank[ap] < self.rank[bp]:
            self.p[ap] = bp
            self.sizelis[bp] += self.sizelis[ap]
        else:
            self.p[bp] = ap
            self.sizelis[ap] += self.sizelis[bp]
            self.rank[ap] += 1
        return self.p[ap]

    def same(self,a,b):
        return self.leader(a) == self.leader(b)

    def size(self,a):
        return self.sizelis[ self.leader(a) ]

    def groups(self):
        dic = {}
        for v in range(self.n):
            vp = self.leader(v)
            if vp not in dic:
                dic[vp] = [v]
            else:
                dic[vp].append(v)
        return list(dic.values())

def test(N):

    uf = DSU(N)
    
    lis = [i for i in range(N)]
    ans = [i for i in range(N)]

    base = 2

    while len(lis) >= 2:

        nlis = []
        for i in range(1,len(lis),2):
            nlis.append(min(lis[i-1],lis[i]))
            uf.merge(lis[i-1],lis[i])
        if len(lis) % 2 == 1:
            nlis = [lis[-1]] + nlis

        lis = nlis
    
        # print (lis)

        for fi in nlis:
            flag = True
            for j in range(fi,fi+base):
                if (not 0 <= j < N) or (not uf.same(fi,j)):
                    flag = False
                    break
            
            if flag:
                for j in range(fi,fi+base):
                    ans[j] = fi

        base *= 2
    
    return ans

def test2(N):
    is_rem = []
    x = N
    while x != 1:
        is_rem.append(x % 2)
        x = (x+1)//2
    
    lis = [1]
    for p in list(reversed(is_rem)):
        new_lis = []
        if p == 0:
            for y in lis:
                new_lis.append(y*2)
        else:
            fi_rem = (lis[0]-1)*2
            for j in range(30):
                if 2**j & fi_rem:
                    new_lis.append(2**j)
            for y in lis[1:]:
                new_lis.append(y*2)
            new_lis.append(1)
        lis = new_lis
    return lis

# for i in range(1,33):
#    print (i,format(i,"b"),test(i),test2(i))

N = int(input())
P = list(map(int,input().split()))

Q = int(input())
d = [[0] * N for i in range(20)]

ans = [0] * N

# seg = SegTree(N,0)
# for i in range(N):
#    seg.update(i,P[i]-1)

for i in range(N):
    P[i] -= 1
spt = SparseTable(P,max)

for i in range(Q):
    L,R = map(int,input().split())
    L -= 1
    R -= 1

    lis = test2((R-L)+1)
    
    idx = L
    for x in lis:
        d[x.bit_length()-1][idx] += 1
        idx += x
    
    # other
    other = []
    cm = []
    pos = L

    for x in lis:
        cm.append( (x,spt.prod(pos,pos+x)) ) 
        pos += x
    
    while True:
        # print (cm)
        ncm = []
        if cm[0][0] == 1:
            ans[ max(cm[0][1],cm[1][1]) ] += 1
            ncm.append( (1, max(cm[0][1],cm[1][1])) )
            cm = cm[2:]

        for i in range(len(cm)):
            if cm[i][0] != 1:
                ncm.append( ( cm[i][0]//2 , cm[i][1] ) )
            else:
                ncm = [ cm[i] ] + ncm
        
        cm = ncm

        s = 0
        for i in range(len(cm)):
            s += cm[i][0]
        if s == 1:
            break

for bit in range(19,0,-1):
    for v in range(N):
        if d[bit][v] > 0:
            nmax = spt.prod(v,v+2**bit)
            ans[nmax] += d[bit][v]
            d[bit-1][v] += d[bit][v]
            d[bit-1][v+2**(bit-1)] += d[bit][v]
print (*ans,sep="\n")
0