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.

Rezolvare

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()