investitie

#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

//Hurjui Alexandru-Mihai -- CN "Stefan cel Mare", 2022

ifstream fin ("investitie.in");
ofstream fout ("investitie.out");

int p[100001];
bool bc[100001];
pair <int, int> carp[100001];
vector <int> vc[100001];
vector <long long> s[100001];

long long calcs (int poz, int nr)
{
    int n, ind;
    long long rasp = 0;

    ind = carp[poz].first;
    poz = carp[poz].second;

    n = vc[ind].size()-1;
    rasp = s[ind].back() * (nr/n);
    nr = nr % n;

    if (nr > 0)
    {
        rasp = rasp + s[ind][min(poz+nr, n)] - s[ind][poz];
        nr = nr - (min (poz+nr, n) - poz);
    }
    if (nr > 0)
        rasp = rasp + s[ind][nr];

    return rasp;
}

int main()
{
    int n, m, i, j, q, zi, zf, pst, pdr;
    int nrc;
    long long valult, rasp;

    fin >> n >> m;
    for (i = 1; i<=n; i++)
        fin >> p[i];

    nrc = 0;
    for (i = 1; i<=n; i++)
        if (bc[i] == 0)
        {
            nrc++;
            vc[nrc].push_back (0);
            for (j = i; bc[j] == 0; j = p[j])
            {
                vc[nrc].push_back (j);
                carp[j] = {nrc, vc[nrc].size()-1};
                bc[j] = 1;
            }
        }
    for (i = 1; i<=nrc; i++)
    {
        s[i].push_back (0);
        for (j = 1; j<vc[i].size(); j++)
        {
            valult = s[i].back();
            s[i].push_back (valult + vc[i][j]);
        }
    }

    fin >> q;
    for (i = 1; i<=q; i++)
    {
        fin >> zi >> zf >> pst >> pdr;

        rasp = 0;
        for (j = pst; j<=pdr; j++)
            rasp = rasp + calcs (j, zf) - calcs (j, zi-1);
        fout << rasp << '\n';
    }
    return 0;
}