#include <bits/stdc++.h>
#define ll long long
#define INF 10000000
using namespace std;
#define LOG 10
#define MAX 400002
int main(){
int n, q, l, r, la;
ll pr = 0, a;
cin>>n;
la = n + 1;
vector<int> de(n + 2, 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()){
if (la == n + 1) la = ma[pr];
la = max(la, ma[pr]);
}
de[i] = la;
ma[pr] = i;
}
int up[n + 2][LOG];
for (int i = 0; i < LOG; i++) up[0][i] = 0, up[n + 1][i] = n + 1;
for (int i = 1; i <= n; i++){
up[i][0] = de[i];
de[i] = de[up[i][0]] + 1;
}
for (int i = 1; i < LOG; i++){
up[n + 1][i] = n + 1;
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 && jmp != n + 1){
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... |