#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int MAXN = 4e5+5;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N;
cin >> N;
int par[N+2], sub[N+2], big[N+2], rot[N+2], dep[N+2];
pli P[N+2];
vector <int> ch[N+2];
for (int i=0;i<=N+1;i++) {
par[i] = N+1;
big[i] = N+2;
rot[i] = -1;
sub[i] = 0;
}
P[0] = {0,0};
for (int i=1;i<=N;i++) {
cin >> P[i].fi;
P[i].fi += P[i-1].fi;
P[i].se = i;
}
sort(P,P+N+1);
for (int i=1;i<=N;i++) {
if (P[i].fi == P[i-1].fi) {
par[P[i-1].se] = P[i].se;
}
}
dep[N+1] = 0;
for (int i=N;i>=0;i--) {
par[i] = min(par[i],par[i+1]);
dep[i] = dep[par[i]]+1;
}
for (int i=0;i<=N;i++) {
sub[i]++;
sub[par[i]] += sub[i];
if (sub[i] > sub[big[par[i]]]) {
big[par[i]] = i;
}
}
for (int i=N+1;i>=0;i--) {
if (rot[i] != -1) continue;
int j = i;
while (j != N+2) {
rot[j] = i;
ch[i].push_back(j);
j = big[j];
}
reverse(ch[i].begin(),ch[i].end());
}
int Q;
cin >> Q;
while (Q--) {
int L, R;
cin >> L >> R;
L--;
int ans = dep[L];
while (par[rot[L]] <= R) {
L = par[rot[L]];
}
int x = upper_bound(ch[rot[L]].begin(),ch[rot[L]].end(),R) - ch[rot[L]].begin() - 1;
x = ch[rot[L]][x];
cout << ans - dep[x] << "\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... |