Корневая декомпозиция

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;
void cv(vector <int> v){
    for (auto x: v) cout<<x<<' ';
    cout<<'\n';
}

vector <int> a =  { 0,1,2,3,4,5,6,7,8,9 ,10};

int N = -1;

struct sct{
    int mn, mx, sum, zr;
};

void csc(sct x){
    cout<<x.mn<<'/'<<x.mx<<'/'<<x.sum<<'\n';
}
vector <sct> wrk(1);


int s = -2;
int inf = 2e9;

int mini_bug(int L, int R){
    cout<<"LR = "<<L<<"  "<<R<<'\n';
    int mn = inf;
    cout<<"ONE\n";
    while (L % s != 0 && L <= R){
        cout<<"L = "<<L<<'\n';
        cout<<"a[L] = "<<a[L]<<'\n';
        mn = min(mn, a[L]);
        cout<<"mn = "<<mn<<'\n';
        L++;
    }
    cout<<"TWO\n";
    while ((L + s - 1) <= R && L <= R){
        cout<<"L = "<<L<<'\n';
        cout<<"a[L] = "<<a[L]<<'\n';
        int id = L / s;
    cout<<"id = "<<id<<'\n';
    cout<<"wrk[id].mn = "<<wrk[id].mn<<'\n';
        mn = min(mn, wrk[id].mn);
        cout<<"mn = "<<mn<<'\n';
        L += s;
    }
    cout<<"THREE\n";
    while (L <= R){
        cout<<"L = "<<L<<'\n';
        cout<<"a[L] = "<<a[L]<<'\n';
        mn = min(mn, a[L]);
        cout<<"mn = "<<mn<<'\n';
        L++;
    }

    return mn;
}

int mini(int L, int R){
    int mn = inf;
    while (L % s != 0 && L <= R){
        mn = min(mn, a[L]);
        L++;
    }
    while ((L + s - 1) <= R && L <= R){
        int id = L / s;
        mn = min(mn, wrk[id].mn);
        L += s;
    }
    while (L <= R){
        mn = min(mn, a[L]);
        L++;
    }

    return mn;
}

int maxi(int L, int R){
    int mx = -inf;
    while (L % s != 0 && L <= R){
        mx = max(mx, a[L]);
        L++;
    }
    while ((L + s - 1) <= R && L <= R){
        int id = L / s;
        mx = max(mx, wrk[id].mx);
        L += s;
    }
    while (L <= R){
        mx = max(mx, a[L]);
        L++;
    }
    return mx;
}

int sumi(int L, int R){
    int sum = 0;
    while (L % s != 0 && L<=R){
        sum += a[L];
        L++;
    }
    while ((L + s - 1) <= R && L<=R){
        int id = L / s;
        sum += wrk[id].sum;
        L += s;
    }
    while (L <= R){
        sum += a[L];
        L++;
    }
    return sum;
}

int zeros(int L, int R){
    int zr = 0;
    while (L % s != 0 && L<=R){
        if (a[L] == 0) zr++;
        L++;
    }
    while ((L + s - 1) <= R && L<=R){
        int id = L / s;
        zr += wrk[id].zr;
        L += s;
    }
    while (L <= R){
        if (a[L] == 0) zr++;
        L++;
    }
    return zr;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    a.resize(N);
    for (int &x: a) cin>>x;
    /*for (int i =0;i<N;++i){
        a[i] = i;
    }*/
    int K;
    cin>>K;
    //reverse(a.begin(), a.end());
    s = sqrt(N);
    //cout<<s<<'\n';
    double Nd = N, sd = s;
    double q = Nd/sd;
    //cout<<q<<'\n';
    int sz = ceil(q);
    //cout<<sz<<'\n';
    wrk.resize(sz);
    int id = -9;
    for (int i = 0;i<sz;++i){
        sct sm = {inf, -inf, 0, 0};
        for (int j =0;j<s && i*s+j<N;++j){
            id = i*s+j;
            sm.mx = max(sm.mx, a[id]);
            sm.mn = min(sm.mn, a[id]);
            sm.sum += a[id];
            if (a[id] == 0) sm.zr++;
            //cout<<a[id]<<' ';
        }/*cout<<'\n';
        csc(sm);
        cout<<'\n';*/
        wrk[i] = sm;
        //cout<<'\n';
    }
    //for (auto x: wrk) csc(x);

    int l,r;
    vector <int> ans;
    for (int i=0; i<K; ++i){
        cin>>l>>r;
        l--;
        r--;
        //cout<<maxi(l,r)<<' ';
        //ans.push_back(maxi(l,r));
        cout<<zeros(l,r)<<' ';
    }
    //cv(ans);
}



/*
10 1
3 5 7 9 2 4 6 8 0 -1
3 5 7 9 2 4 6 0 0 -1

10 2
3 5 7 9 2 4 6 8 0 -1
*/