Çàäà÷à . Ðàñ÷åò àñèìïòîòèêè - 3

#include <bits/stdc++.h>
using namespace std;

int K;

struct query
{
    int l, r, ind;
};

bool cmp(query a, query b)
{
    if (a.l / K != b.l / K)
        return a.l / K < b.l / K;
    else
        return a.r < b.r;
}

int main()
{
    int n, q;
    cin >> n >> q;
    // äëÿ ïðîñòîòû, ñ÷èòàéòå, ÷òî q = n
    K = (int)sqrt(n);

    vector <int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector <query> ask(q);
    vector <int> ans(q);
    for (int i = 0; i < q; i++)
    {
        cin >> ask[i].l >> ask[i].r;
        ask[i].l--; ask[i].r--;
        ask[i].ind = i;
    }
    sort(ask.begin(), ask.end(), cmp);

    // Ïîñ÷èòàéòå àñèìïòîòèêó òîëüêî ÷àñòè êîäà, 
    // ðàñïîëîæåííîé íèæå ýòîãî êîììåíòàðèÿ

    int sum = 0, L = ask[0].l, R = ask[0].r;
    for (int i = ask[0].l; i <= ask[0].r; i++)
        sum += arr[i];
    ans[ask[0].ind] = sum;

    for (int i = 1; i < q; i++)
    {
        for (int j = L; j < ask[i].l; j++)
            sum -= arr[j];
        for (int j = L - 1; j >= ask[i].l; j--)
            sum += arr[j];
        for (int j = R + 1; j <= ask[i].r; j++)
            sum += arr[j];
        for (int j = R; j > ask[i].r; j--)
            sum -= arr[j];
        ans[ask[i].ind] = sum;
        L = ask[i].l; R = ask[i].r;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << endl;

    return 0;
}