結果
| 問題 |
No.1733 Sum of Sorted Subarrays
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2025-07-12 01:10:16 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,700 ms / 3,000 ms |
| コード長 | 5,506 bytes |
| コンパイル時間 | 449 ms |
| コンパイル使用メモリ | 82,192 KB |
| 実行使用メモリ | 143,356 KB |
| 最終ジャッジ日時 | 2025-07-12 01:11:01 |
| 合計ジャッジ時間 | 41,789 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
## https://yukicoder.me/problems/no/2730
MOD = 998244353
class BinaryIndexTree:
"""
フェニック木(BinaryIndexTree)の基本的な機能を実装したクラス
"""
def __init__(self, size):
self.size = size
self.array = [1] * (size + 1)
def add(self, x, a):
index = x
while index <= self.size:
self.array[index] *= a
self.array[index] %= MOD
index += index & (-index)
def sum(self, x):
index = x
ans = 1
while index > 0:
ans *= self.array[index]
ans %= MOD
index -= index & (-index)
return ans
def least_upper_bound(self, value):
if self.sum(self.size) < value:
return -1
elif value <= 0:
return 0
m = 1
while m < self.size:
m *= 2
k = 0
k_sum = 0
while m > 0:
k0 = k + m
if k0 < self.size:
if k_sum + self.array[k0] < value:
k_sum += self.array[k0]
k += m
m //= 2
if k < self.size:
return k + 1
else:
return -1
class LazySegmentTree:
"""
非再帰版遅延セグメント木。
更新は「加法」、取得は「最大値」のもの限定。
取得のところの都合で取得演算子は可換になっている必要がある。
"""
def __init__(self, init_array):
n = 1
while n < len(init_array):
n *= 2
self.size = n
self.array = [0] * (2 * self.size)
self.lazy_array = [1 for _ in range(2 * self.size)]
for i, a in enumerate(init_array):
self.array[self.size + i] = a
end_index = self.size
start_index = end_index // 2
while start_index >= 1:
for i in range(start_index, end_index):
self.array[i] = (self.array[2 * i] + self.array[2 * i + 1]) % MOD
end_index = start_index
start_index = end_index // 2
def _propagates(self, *ids):
for i in reversed(ids):
self._propagate(i)
def _propagate(self, i):
v = self.lazy_array[i]
if v == 1:
return
if i < self.size:
self.lazy_array[2 * i] *= v
self.lazy_array[2 * i] %= MOD
self.lazy_array[2 * i + 1] *= v
self.lazy_array[2 * i + 1] %= MOD
self.array[2 * i] *= v
self.array[2 * i] %= MOD
self.array[2 * i + 1] *= v
self.array[2 * i + 1] %= MOD
self.lazy_array[i] = 1
def _get_target_index(self, l, r):
L = l + self.size; R = r + self.size
lm = (L // (L & -L)) >> 1
rm = (R // (R & -R)) >> 1
while 0 < L and L < R:
if R <= rm:
yield R
if L <= lm:
yield L
L >>= 1; R >>= 1
while L > 0:
yield L
L >>= 1
def add(self, l, r, x):
# 2. 区間[l, r)のdata, lazyの値を更新
L = self.size + l; R = self.size + r
*ids, = self._get_target_index(l, r)
self._propagates(*ids)
while L < R:
if R & 1:
R -= 1
self.lazy_array[R] *= x
self.lazy_array[R] %= MOD
self.array[R] *= x
self.array[R] %= MOD
if L & 1:
self.lazy_array[L] *= x
self.lazy_array[L] %= MOD
self.array[L] *= x
self.array[L] %= MOD
L += 1
L >>= 1; R >>= 1
# 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
for i in ids:
if i < self.size:
self.array[i] = (self.array[2 * i] + self.array[2 * i + 1]) % MOD
def get_sum(self, l, r):
# 1. トップダウンにlazyの値を伝搬
self._propagates(*self._get_target_index(l, r))
L = self.size + l; R = self.size + r
# 2. 区間[l, r)の最大値を求める
s = 0
while L < R:
if R & 1:
R -= 1
s += self.array[R]
s %= MOD
if L & 1:
s += self.array[L]
s %= MOD
L += 1
L >>= 1; R >>= 1
return s
def main():
N = int(input())
A = list(map(int, input().split()))
a_list = [(i, a) for i, a in enumerate(A)]
a_list.sort(key=lambda x : x[1])
left_seg_tree = LazySegmentTree([1] * N)
left_bit = BinaryIndexTree(N)
right_seg_tree = LazySegmentTree([1] * N)
right_bit = BinaryIndexTree(N)
answer = 0
inv_2 = pow(2, MOD - 2, MOD)
for i in range(N):
index, a = a_list[i]
l = left_seg_tree.get_sum(0, index + 1)
l0 = left_bit.sum(index + 1)
r = right_seg_tree.get_sum(index, N)
r0 = right_bit.sum(N - 1 - index + 1)
lr1 = (l * r) % MOD
lr0 = (l0 * r0) % MOD
ans = (lr1 * lr0) % MOD
ans *= a
ans %= MOD
answer += ans
answer %= MOD
left_seg_tree.add(0, index + 1, 2)
left_bit.add(index + 1, inv_2)
right_seg_tree.add(index, N, 2)
right_bit.add(N - 1 - index + 1, inv_2)
print(answer)
if __name__ == "__main__":
main()