結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2020-09-21 01:19:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 787 ms / 2,000 ms |
コード長 | 2,192 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 156,452 KB |
最終ジャッジ日時 | 2024-06-24 11:18:26 |
合計ジャッジ時間 | 7,630 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
class BIT:def __init__(self, n):self.n = nself.bit = [0]*(self.n+1) # 1-indexeddef init(self, init_val):for i, v in enumerate(init_val):self.add(i, v)def add(self, i, x):# i: 0-indexedi += 1 # to 1-indexedwhile i <= self.n:self.bit[i] += xi += (i & -i)def sum(self, i, j):# return sum of [i, j)# i, j: 0-indexedreturn self._sum(j) - self._sum(i)def _sum(self, i):# return sum of [0, i)# i: 0-indexedres = 0while i > 0:res += self.bit[i]i -= i & (-i)return resclass RangeAddBIT:def __init__(self, n):self.n = nself.bit1 = BIT(n)self.bit2 = BIT(n)def init(self, init_val):self.bit2.init(init_val)def add(self, l, r, x):# add x to [l, r)# l, r: 0-indexedself.bit1.add(l, x)self.bit1.add(r, -x)self.bit2.add(l, -x*l)self.bit2.add(r, x*r)def sum(self, l, r):# return sum of [l, r)# l, r: 0-indexedreturn self._sum(r) - self._sum(l)def _sum(self, i):# return sum of [0, i)# i: 0-indexedreturn self.bit1._sum(i)*i + self.bit2._sum(i)import sysinput = sys.stdin.buffer.readlinen = int(input())A = list(map(int, input().split()))par = [-1]*nch = [[] for _ in range(n)]for i, a in enumerate(A):par[i+1] = ach[a].append(i+1)root = 0s = [root]eulerTour = []left = [0]*nright = [-1]*ndepth = [-1]*nnum = -1de = -1while s:q = s.pop()if q >= 0:num += 1eulerTour.append(q)left[q] = numright[q] = nums.append(~q)de += 1depth[q] = defor v in ch[q]:s.append(v)else:de -= 1if ~q != root:eulerTour.append(par[~q])num += 1right[par[~q]] = num#print(eulerTour)#print(left)#print(right)bit = RangeAddBIT(2*n+1)ans = 0for i in range(n):ans += bit.sum(left[i], left[i]+1)bit.add(left[i], right[i]+1, 1)print(ans)