#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
const int N = 5e5 + 5;
int nxt[N];
int depth[N];
int n, q;
int a[N];
ll p[N];
int jump[N];
map<ll, int> mp;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
cin >> q;
nxt[n + 1] = n + 2;
nxt[n + 2] = n + 2;
for (int i = n; i >= 1; i--) {
mp[p[i]] = i;
if (mp.count(p[i - 1])) nxt[i] = min(nxt[i + 1], mp[p[i - 1]] + 1);
else nxt[i] = nxt[i + 1];
// cout << nxt[i][0] << ' ';
}
mp.clear();
jump[n + 1] = jump[n + 2] = n + 2;
depth[n + 1] = 0;
for (int i = n; i >= 1; i--) {
int p = nxt[i];
depth[i] = depth[p] + 1;
if (depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]]) jump[i] = jump[jump[p]];
else jump[i] = p;
}
while(q--) {
int l, r;
cin >> l >> r;
assert(r <= n);
int res = 0;
while(nxt[l] <= r + 1) {
if (jump[l] <= r + 1) res += depth[l] - depth[jump[l]], l = jump[l];
else res++, l = nxt[l];
}
cout << res << '\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... |