Editing 1901 - Median Heaps

= Cerința =
Se dă un vector de <code>N</code> numere naturale nenule, indexat de la <code>1</code>.

Se cere să se raspundă la <code>Q</code> interogări de tipul:

* pentru un interval <code>[l, r]</code> din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.

Într-un interval <code>[l, r]</code>, puteți crește sau micșora fiecare element cu costul <code>x</code> unde <code>x</code> este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri.

= Date de intrare =

* pe prima linie numărul <code>N</code>.
* pe a doua linie <code>N</code> numere naturale nenule : , , … .
* pe a treia linie numărul <code>Q</code>.
* pe următoarele <code>Q</code> linii <code>2</code> numere: <code>l, r</code>.

= Date de ieșire =
Se vor afișa <code>Q</code> numere pe fiecare linie, reprezentând constul total minim, al fiecărui interval <code>l r</code>.

= Restricții și precizări =

* <code>1 ≤ N, Q ≤ 100.000</code>
* <code>1 ≤ l ≤ r ≤ 100.000</code>
* <code>1 ≤</code>  <code>≤ 1.000.000.000</code>

= Exemplu: =
Intrare
 9
 3 2 16 15 12 6 20 4 5
 3
 2 7
 2 2
 3 8
Ieșire
 31
 0
 29

= Explicație =
Pentru intervalul <code>[2, 7]</code>, costul total minim este <code>31</code>, deoarece egalizăm fiecare număr din interval cu <code>12</code>.

Pentru intervalul <code>[2, 2]</code>, costul total minim este <code>0</code>, deoarece avem un singur element în interval.

Pentru intervalul <code>[3, 8]</code>, costul total minim este <code>29</code>, deoarece egalizăm fiecare număr din interval cu <code>12</code>

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
import math

Nmax = 100001

class Query:
    def __init__(self, st, dr, pos):
        self.st = st
        self.dr = dr
        self.pos = pos

def update(aib, aibs, pos, val1, val2):
    while pos < Nmax:
        aib[pos] += val1
        aibs[pos] += val2
        pos += pos & -pos

def query(aib, aibs, pos, c):
    sum_val = 0
    s = 0
    while pos > 0:
        sum_val += aib[pos]
        if aibs is not None:
            s += aibs[pos]
        pos -= pos & -pos
    return sum_val if c == 1 else s

def add(k, N, V, S, aib, aibs):
    update(aib, aibs, N[k], 1, V[S[N[k]]])

def delete(k, N, V, S, aib, aibs):
    update(aib, aibs, N[k], -1, -V[S[N[k]]])

def binary_search(pos, n, aib):
    st, dr = 1, n
    ans = -1
    while st <= dr:
        mid = (st + dr) // 2
        q = query(aib, None, mid, 1)
        if q >= pos:
            dr = mid - 1
            ans = mid
        else:
            st = mid + 1
    return ans

def verify_restrictions(n, q, ranges):
    if not (1 <= n <= 100000 and 1 <= q <= 100000):
        return False
    for l, r in ranges:
        if not (1 <= l <= r <= 100000):
            return False
    return True

def main():
    n = int(input())
    V = [0] * (n + 1)
    
    values = list(map(int, input().split()))
    for i in range(1, n + 1):
        V[i] = values[i-1]
    
    q = int(input())
    ranges = []
    Q = []
    for i in range(1, q + 1):
        st, dr = map(int, input().split())
        ranges.append((st, dr))
        Q.append(Query(st, dr, i))

    if not verify_restrictions(n, q, ranges):
        print("Datele nu corespund restrictiilor impuse")
        return

    block = int(math.sqrt(n))
    S = list(range(n + 1))
    S[1:] = sorted(S[1:], key=lambda x: V[x])
    N = [0] * (n + 1)
    for i in range(1, n + 1):
        N[S[i]] = i

    Q.sort(key=lambda x: (x.dr // block, x.st if x.dr // block % 2 == 0 else -x.st))
    aib = [0] * Nmax
    aibs = [0] * Nmax
    Rez = [0] * (q + 1)
    
    st, dr = 1, 0
    for i in range(1, q + 1):
        s, d = Q[i-1].st, Q[i-1].dr
        while st < s:
            delete(st, N, V, S, aib, aibs)
            st += 1
        while st > s:
            st -= 1
            add(st, N, V, S, aib, aibs)
        while dr < d:
            dr += 1
            add(dr, N, V, S, aib, aibs)
        while dr > d:
            delete(dr, N, V, S, aib, aibs)
            dr -= 1

        poss = (d - s + 2) // 2
        ans = binary_search(poss, n, aib)
        s1 = query(aib, aibs, n, 2)
        h1 = query(aib, None, n, 1)
        s2 = query(aib, aibs, ans, 2)
        h2 = query(aib, None, ans, 1)
        s1 -= s2
        h1 -= h2

        Rez[Q[i-1].pos] = s1 - h1 * V[S[ans]] + (-s2 + h2 * V[S[ans]])

    for i in range(1, q + 1):
        print(Rez[i])

if __name__ == "__main__":
    main()

</syntaxhighlight>