結果
| 問題 | No.1300 Sum of Inversions |
| コンテスト | |
| ユーザー |
 回転
|
| 提出日時 | 2026-05-22 18:06:36 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,044 bytes |
| 記録 | |
| コンパイル時間 | 516 ms |
| コンパイル使用メモリ | 85,120 KB |
| 実行使用メモリ | 211,096 KB |
| 最終ジャッジ日時 | 2026-05-22 18:07:39 |
| 合計ジャッジ時間 | 12,302 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 TLE * 9 |
ソースコード
class WaveletMatrix:
def __init__(self,V):
self.n=len(V)
self.lg=max(V).bit_length()
self.ranks=[]
self.accs=[]
self.original_V=V
V=list(V)
for bit in range(self.lg-1,-1,-1):
rank=[0]*(self.n+1)
for i,v in enumerate(V):
rank[i+1]=rank[i]+((v>>bit)&1)
swp=[0]*self.n
zero,one=0,self.n-rank[self.n]
for v in V:
if (v>>bit)&1:
swp[one]=v
one+=1
else:
swp[zero]=v
zero+=1
acc=[0]*(self.n+1)
for i,v in enumerate(swp):
acc[i+1]=acc[i]+v
V=swp
self.ranks.append(rank)
self.accs.append(acc)
self.accs.append([0])
for v in self.original_V:
self.accs[-1].append(self.accs[-1][-1]+v)
def access(self,i):
return self.original_V[i]
def rank(self,r,x):
if (x>>self.lg)&1:return 0
for i in range(self.lg-1,-1,-1):
bit=(x>>i)&1
rank=self.ranks[i]
if bit:
zeros=self.n-rank[r]
r=zeros+rank[r]
else:
r-=rank[r]
return r
def rank_range(self,l,r,x):
return self.rank(r,x)-self.rank(l,x)
def quantile(self,l,r,k):
res=0
for i in range(self.lg-1,-1,-1):
rank=self.ranks[self.lg-1-i]
ones=rank[r]-rank[l]
zeros=(r-l)-ones
if k<zeros:
l-=rank[l]
r-=rank[r]
else:
res|=1<<i
k-=zeros
zero_sum=self.n-rank[self.n]
l=zero_sum+rank[l]
r=zero_sum+rank[r]
return res
def _range_freq(self,l,r,x):
if x.bit_length() > self.lg:
return r - l
res=0
for i in range(self.lg-1,-1,-1):
bit=(x>>i)&1
rank=self.ranks[self.lg-1-i]
ones=rank[r]-rank[l]
zeros=(r-l)-ones
if bit:
res+=zeros
zero_sum=self.n-rank[self.n]
l=zero_sum+rank[l]
r=zero_sum+rank[r]
else:
l-=rank[l]
r-=rank[r]
return res
def range_freq(self,left,right,lower,upper):
return self._range_freq(left,right,upper)-self._range_freq(left,right,lower)
def prev_value(self,left,right,upper):
cnt=self._range_freq(left,right,upper)
return self.quantile(left,right,cnt-1) if cnt>0 else None
def next_value(self,left,right,lower):
cnt=self._range_freq(left,right,lower)
return self.quantile(left,right,cnt) if cnt<right-left else None
def _range_sum(self,l,r,x):
if self.lg<x.bit_length():return self.accs[-1][r]-self.accs[-1][l]
res=0
for i in range(self.lg-1,-1,-1):
bit=(x>>i)&1
rank=self.ranks[self.lg-1-i]
acc=self.accs[self.lg-1-i]
if bit:
zero_sum=self.n-rank[self.n]
l0=l-rank[l]
r0=r-rank[r]
res+=acc[r0]-acc[l0]
l=zero_sum+rank[l]
r=zero_sum+rank[r]
else:
l-=rank[l]
r-=rank[r]
return res
def range_sum(self,left,right,lower,upper):
return self._range_sum(left,right,upper)-self._range_sum(left,right,lower)
def _build_distinct_wm(self):
P = [0] * self.n
last_pos = {}
for i, v in enumerate(self.original_V):
P[i] = last_pos.get(v, -1) + 1
last_pos[v] = i
self._distinct_wm = WaveletMatrix(P)
def range_distinct(self, left, right):
"""
区間 [left, right) に含まれる要素の種類数を返す
初回呼び出し時にO(N log N)で補助構造を構築し、以降はO(log N)で応答する。
"""
if not hasattr(self, "_distinct_wm"):
self._build_distinct_wm()
return self._distinct_wm.range_freq(left, right, 0, left + 1)
def bottom_k_sum(self, l, r, k):
"""
区間 [l, r) の中で小さい方から k 個の要素の和を返す
計算量: O(log N)
"""
if k <= 0: return 0
if k >= r - l: return self.accs[-1][r] - self.accs[-1][l]
res = 0
val = 0
for i in range(self.lg - 1, -1, -1):
rank = self.ranks[self.lg - 1 - i]
acc = self.accs[self.lg - 1 - i]
ones = rank[r] - rank[l]
zeros = (r - l) - ones
l0 = l - rank[l]
r0 = r - rank[r]
if k <= zeros:
l = l0
r = r0
else:
res += acc[r0] - acc[l0]
k -= zeros
val |= (1 << i)
zero_sum = self.n - rank[self.n]
l = zero_sum + rank[l]
r = zero_sum + rank[r]
res += k * val
return res
def top_k_sum(self, l, r, k):
"""
区間 [l, r) の中で大きい方から k 個の要素の和を返す
計算量: O(log N)
"""
if k <= 0: return 0
length = r - l
if k >= length: return self.accs[-1][r] - self.accs[-1][l]
total_sum = self.accs[-1][r] - self.accs[-1][l]
return total_sum - self.bottom_k_sum(l, r, length - k)
MOD = 998244353
N = int(input())
A = list(map(int,input().split()))
MAX = max(A)
WM = WaveletMatrix(A)
ans = 0
for i in range(1,N-1):
ans += WM.range_sum(0,i,A[i]+1,MAX+1) * WM.range_freq(i+1,N,0,A[i])
ans += A[i] * WM.range_freq(0,i,A[i]+1,MAX+1) * WM.range_freq(i+1,N,0,A[i])
ans += WM.range_freq(0,i,A[i]+1,MAX+1) * WM.range_sum(i+1,N,0,A[i])
ans %= MOD
print(ans)