""" 速度チェック 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")