区間和（sweep line/line sweep）

sweep line/line sweep の概要

長さNの配列とある区間に一定の値を加算するQueryがk個与えられている場合に、その配列の終状態をO(n+k)で計算可能なアルゴリズム。例えばAという配列があって、[i, j]の区間にmを加算する[i, j, m]というQueryがk個ある場合、まず0で初期化した長さがAより1つ大きい配列Bを用意して、全てのQueryに対して、B[i]にmを加え、B[j+1]からmを引いた後、前から累積和をとって、最後の要素を省いたものが答え。要は累積和の亜種かな。多分Segment TreeとかBinary Index Treeとか使えればそっちで良さそう。

例

370. Range Addition

問題は上の概要そのまま。1109. Corporate Flight Bookingsもほぼ同じ問題。

def getModifiedArray(length, updates)
    ans = [0] * (length + 1)
    for i, j, k in updates:
        ans[i] += k
        ans[j+1] -= k
    for i in range(1, length):
        ans[i] += ans[i - 1]
    return ans[:-1]

"""

1094. Car Pooling

ある車のcapacityと、様々な区間ごとに乗車人数trips (<= 1000) が与えられていて（[k, i, j], k：乗車人数、i:pick upする場所、jがdrop offする場所）、実際にすべての乗車区間で乗車可能かどうか判定。

def carPooling(trips, capacity):
    nums = [0] * 1001 
    for n, i, j in trips:
        nums[i] += n
        nums[j] -= n
    for v in stops:    
        capacity -= v
        if 0 > capacity:
            return False
    return True

1589. Maximum Sum Obtained of Any Permutation

ある配列と区間を示すQueryが与えられていて、すべてのQueryの区間和の和が最大となるように配列が並べ可能なときに、その最大値を求める。
方針：どの位置/indexが高頻度かをline sweepで数え、高頻度な順に大きい数を配置していけば良い。

def maxSumRangeQuery(nums, requests):
    n = len(nums)
    cnt = [0] * (n + 1)
    for i, j in req:
        cnt[i] += 1
        cnt[j + 1] -= 1
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    ans = 0
    for val, num in zip(sorted(cnt[:-1]), sorted(nums)):
        ans += val * num
    return ans % (10**9 + 7)