Minimum Sum
/icons/hr.icon
問題
/icons/hr.icon
出典
AGC005 - B 1828 diff
/icons/hr.icon
問題概要
$ \sum_{l = 1}^{N} \sum_{r=l}^{N} \min(a_l, a_{l + 1}, ..., a_{r - 1}, a_r) を求めよ。
/icons/hr.icon
制約
$ 1 \leq N \leq 2 \times 10^5
/icons/hr.icon
考察・解説
愚直に解くだけだと $ O(N^2) で TLE するのでどうにか高速化を試みたい
$ O(N) や $ O(N \log N) といった所でしょうか
とりあえず愚直ではダメなので、 最小値が $ a_i となるような区間の個数は何個あるのか考えてみる
仮にそれが $ k_i 個であった場合、求める答えは $ \sum_{i = 1}^{N} k_i \times a_i で求めることが可能である
これは俗に言う 主客転倒 と呼ばれる数え上げのテクニックの一つである
ということで実際に考察してみる
$ a_1, a_2, ..., a_l, ..., a_i, a_{i+1}, ..., a_r, ..., a_n といった $ a_l \leq a_i \leq a_r を満たすような $ a_i を考える。
このような $ a_i が最小値になる区間は
左側が $ i - (l + 1) + 1 = i - l
右側が $ (r - 1) - i + 1 = r - i
したがって、$ (i - l) \times (r - i) 通りの組み合わせがある
これらは SortedSet を用いればやるだけになる。
自分で作ろうと思ったが地獄を見たので tatyam さんのものを拝借する...
/icons/hr.icon
コード
code:Python
'''
使用例
'''
from math import ceil, sqrt
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')
class SortedSet(GenericT): BUCKET_RATIO = 50
REBUILD_RATIO = 170
def _build(self, a=None) -> None:
"Evenly divide a into buckets."
if a is None:
a = list(self)
size = self.size = len(a)
bucket_size = int(ceil(sqrt(size / self.BUCKET_RATIO)))
def __init__(self, a: IterableT = []) -> None: "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
a = list(a)
if not all(ai < ai + 1 for i in range(len(a) - 1)): a = sorted(set(a))
self._build(a)
def __iter__(self) -> IteratorT: for i in self.a:
for j in i:
yield j
def __reversed__(self) -> IteratorT: for i in reversed(self.a):
for j in reversed(i):
yield j
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedSet" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
def _find_bucket(self, x: T) -> ListT: "Find the bucket which should contain x. self must not be empty."
for a in self.a:
return a
return a
def __contains__(self, x: T) -> bool:
if self.size == 0:
return False
a = self._find_bucket(x)
i = bisect_left(a, x)
return i != len(a) and ai == x def add(self, x: T) -> bool:
"Add an element and return True if added. / O(√N)"
if self.size == 0:
self.a = x
self.size = 1
return True
a = self._find_bucket(x)
i = bisect_left(a, x)
if i != len(a) and ai == x: return False
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.REBUILD_RATIO:
self._build()
return True
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0:
return False
a = self._find_bucket(x)
i = bisect_left(a, x)
if i == len(a) or ai != x: return False
a.pop(i)
self.size -= 1
if len(a) == 0:
self._build()
return True
def lt(self, x: T) -> UnionT, None: "Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
def le(self, x: T) -> UnionT, None: "Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
def gt(self, x: T) -> UnionT, None: "Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
def ge(self, x: T) -> UnionT, None: "Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
def __getitem__(self, x: int) -> T:
"Return the x-th element, or IndexError if it doesn't exist."
if x < 0:
x += self.size
if x < 0:
raise IndexError
for a in self.a:
if x < len(a):
x -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
return ans + bisect_right(a, x)
ans += len(a)
return ans
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in sorted(range(n), key=lambda i: ai): s.add(i)
k = s.index(i)
ans += (i - l) * (r - i) * ai print(ans)