#include <bits/stdc++.h>
#define ll long long
#define INF 10000000
using namespace std;
#define LOG 10
#define MAX 400000
int up[MAX][LOG];
int main(){
int n, q, a, l, r, la;
ll pr = 0;
cin>>n;
vector<int> de(n + 1, 0);
map<ll, int> ma;
ma[0] = 0;
for (int i = 1; i <= n; i++){
cin>>a;
pr += a;
if (ma.find(pr) != ma.end()){
la = max(la, ma[pr]);
}
up[i][0] = la;
de[i] = de[la] + 1;
ma[pr] = i;
}
for (int i = 1; i < LOG; i++){
for (int j = 1; j <= n; j++){
up[j][i] = up[up[up[up[j][i - 1]][i - 1]][i - 1]][i - 1];
}
}
cin>>q;
while (q--){
cin>>l>>r;
int st = r;
l--;
for (int i = 19; i >= 0; i--){
int jmp = up[r][i / 2];
if (i % 2 == 1) jmp = up[jmp][i / 2];
if (jmp >= l){
r = jmp;
}
}
cout<<de[st] - de[r]<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |