#include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin() , x.end() const int SQRT = 632; void solve(){ int n; cin >> n; int arr[n]; for(int i = 0;i<n;i++)cin >> arr[i]; int nxt[n+1]; fill(nxt , nxt + n+1 , n+1); { vector<long long>pre(n+1); pre[0] = 0; for(int i = 0;i<n;i++){ pre[i+1] = pre[i] + arr[i]; } map<long long,int>mpa; for(int i = n;i>=0;i--){ if(mpa.count(pre[i])){ nxt[i] = mpa[pre[i]]; } mpa[pre[i]] = i; } } vector<int>tree[n+2] , path; { int edge[n+1]; memset(edge , -1 , sizeof(edge)); for(int i = 0;i<=n;i++){ edge[i] = nxt[i]; } for(int i = n;i>=0;i--){ if(i < n) edge[i] = min(edge[i] , edge[i+1]); tree[edge[i]].push_back(i); } } int jump1[n+1] , jump2[n+1]; memset(jump1 , -1 , sizeof(jump1)); memset(jump2 , -1 , sizeof(jump2)); function<void(int)> dfs = [&](int node){ if(!path.empty()){ jump1[node] = path.back(); } if(sz(path) - SQRT >= 0){ jump2[node] = path[sz(path) - SQRT]; } path.push_back(node); for(auto itr : tree[node]){ dfs(itr); } path.pop_back(); }; dfs(n+1); int q; cin >> q; while(q--){ int l,r; cin >> l >> r; l--; int ans = 0; while(l <= n and jump2[l] <= r and jump2[l] != -1){ ans += SQRT; l = jump2[l]; } while(l <= n and jump1[l] <= r and jump1[l] != -1){ ans++; l = jump1[l]; } cout << ans << '\n'; } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase=1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; }

In file included from /usr/include/string.h:548,
                 from /usr/include/c++/13/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:121,
                 from sumzero.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'void solve()' at sumzero.cpp:33:9:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified bound between 18446744065119617028 and 18446744073709551612 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   59 |   return __builtin___memset_chk (__dest, __ch, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
   60 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~