#include <iostream>
#include <map>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
using namespace std;
int const N=1e5+10,LG=19;
int nx[N],mn[N],pre[N];
pair<int,int> calc[N][LG]={};
inline void solve()
{
int n,q;
cin>>n;
map<long long,int>ind;
ind[0]=-1;
int a[n];
for (auto& i:a)
cin>>i;
long long sm=0;
for (int i=0;i<n;i++)
{
nx[i]=-1;
sm+=a[i];
if (ind.find(sm)!=ind.end())
{
pre[i]=ind[sm]+1;
nx[ind[sm]+1]=i;
}
ind[sm]=i;
}
for (int i=0;i<=n+1;i++)
for (int j=0;j<LG;j++)
calc[i][j]={n,n};
mn[n]=n+10;
set<pair<int,int>>s;
for (int i=n-1;i>=0;i--)
{
mn[i]=mn[i+1];
if (nx[i]!=-1)
{
int f=mn[nx[i]+1];
mn[i]=min(mn[i],nx[i]);
s.insert({nx[i],i});
}
if (s.size()==0)
continue;
calc[i][0]=*begin(s);
}
for (int i=n-1;i>=0;i--)
{
for (int j=1;j<LG;j++)
{
calc[i][j]=calc[min(n,calc[i][j-1].first+1)][j-1];
}
}
cin>>q;
while (q--)
{
int l,r;
cin>>l>>r;
l--;r--;
int ans=0;
for (int i=LG-1;i>=0;i--)
{
if (calc[l][i].first<=r)
{
ans+=(1<<i);
l=calc[l][i].first+1;
}
}
cout<<ans<<endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |