結果
| 問題 |
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 |
ソースコード
"""
速度チェック
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")