Editing 4115 - Investitie

== Enunt ==
După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive.

În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice i=1..N, unde valorile a[i] sunt date.

Numerele a[1], a[2], …, a[N] reprezintă o permutare a numerelor 1,2,...,N}.

În ziua a j-a el va investi în compania i o sumă de bani egală cu s[j][i] = s[j-1][a[i]], pentru orice zi j =2..M şi orice companie i = 1..N.
== Cerinţa ==
După finalizarea planului de investiţii, Dorel vrea să realizeze Q statistici referitoare la sumele investite. Fiind date Q seturi de valori zi, zf, cl, cr, el doreşte să afle ce sumă a investit în perioada cuprinsă între zilele zi și zf (inclusiv acestea), la companiile cu numere de ordine cuprinse între cl și cr (inclusiv acestea).
== Date de intrare ==
Pe prima linie a fişierului de intrare investitie.in se află numerele N şi M, separate prin spaţiu. Pe a doua linie se află valorile a[1], a[2], ..., a[N], separate prin spaţiu. Pe a treia linie se află valoarea lui Q. Pe următoarele Q linii se află câte patru valori, zi, zf, cl, cr, separate prin spaţiu.
== Date de ieșire ==
În fişierul de ieşire investitie.out se vor afişa, pe linii diferite, sumele investite corespunzătoare fiecăreia din cele Q statistici din fişierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ N, Q ≤ 100.000
* 1 ≤ M ≤ 1.000.000.000
* 1 ≤ zi ≤ zf ≤ M
* 1 ≤ cl ≤ cr ≤ N
* 0 ≤ cr -cl ≤ 100
* Pentru 10 puncte, M = 1
* Pentru 20 de puncte, 1 ≤  N, M ≤ 100, 1 ≤ Q ≤ 1000
* Pentru 12 puncte, 101 ≤ N , M ≤ 3000
* Pentru 24 de puncte, 1 ≤ N ≤ 50
* Pentru 34 de puncte fără alte restricţii
== Exemplul 1 ==
; investitie.in

  8 3
  3 1 7 2 6 4 5 8
  5
  1 1 3 7
  1 2 1 4
  1 3 2 8
  2 3 3 6
  3 3 3 3
; investitie.out

  24
  29
  93
  24
  6
== Explicație ==
Sumele investite în cele trei zile, în acţiuni ale celor opt companii, vor fi:

3 & 1 & 7 & 2 & 6 & 4 & 5 & 8
7 & 3 & 5 & 1 & 4 & 2 & 6 & 8
5 & 7 & 6 & 3 & 2 & 1 & 4 & 8


Prima statistică cere suma investită în prima zi în companiile cu numere de ordine de la 3 la 7. Suma este 7+2+6+4+5=24.
A doua statistică cere suma investită în primele două zile în companiile cu numerele de ordine de la 12 la 4. Suma este (3+1+7+2)+(7+3+5+1)=29.
Similar se calculează celelalte statistici.
<br>



== Rezolvare ==
<syntaxhighlight lang="python" line>
def investition(N, M, a, Q, queries):
    investments = [[0] * (N + 1) for _ in range(M + 1)]
    for i in range(1, N + 1):
        investments[1][i] = a[i - 1]
    for j in range(2, M + 1):
        for i in range(1, N + 1):
            investments[j][i] = investments[j - 1][a[i - 1]]
    
    cumulative_investments = [[0] * (N + 1) for _ in range(M + 1)]
    for j in range(1, M + 1):
        for i in range(1, N + 1):
            cumulative_investments[j][i] = cumulative_investments[j - 1][i] + investments[j][i]
    
    results = []
    for query in queries:
        zi, zf, cl, cr = query
        total_investment = 0
        for i in range(cl, cr + 1):
            total_investment += cumulative_investments[zf][i] - cumulative_investments[zi - 1][i]
        results.append(total_investment)
    return results

def main():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))
    Q = int(input())
    queries = [list(map(int, input().split())) for _ in range(Q)]

    results = investition(N, M, a, Q, queries)
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

</syntaxhighlight>