Разбор

Problem Author:	Kostiantyn Denysov
Prepared by:	Illia Shevchenko
Editorial by:	Kostiantyn Denysov

Let's define the prefix sum array $p$ , where $p_{0} = 0$ and $p_{i} = p_{i - 1} + a_{i}$ for each $i > 0$ . A segment $[l, r]$ has a sum of $0$ if and only if $p_{r} = p_{l - 1}$ .

Suppose we want to solve a problem on the entire array $a$ , which involves changing the minimal number of integers so that there is no subarray with a $0$ sum. We can approach this using a greedy algorithm (the proof is left to the reader):

Initialize a set $b$ to ${0}$ , which represents the set of previous prefix sums.
Iterate over the elements from left to right, with $i$ representing the index of the current element being considered.
If $p_{i}$ is in set $b$ , then a subarray with a $0$ sum exists, and we change the element at $i$ (incrementing the operation count) and update $b$ to ${p_{i}}$ .
If $p_{i}$ is not in $b$ , add $p_{i}$ to $b$ ( $b := b \cup {p_{i}}$ ).

To speed up this algorithm, we can compute the array $g o$ , where $g o_{i} = min {j ∣ j > i \land p_{j} = p_{i}}$ . This means for each position $i$ , we determine the smallest subarray starting at this position with a $0$ sum. Then, for each position $i$ , we can find the minimum $r$ such that there exists an $l \geq i$ with $p_{l} = p_{r}$ . To do this, we can compute suffix minimums of the array $g o$ . Let the resulting array be $n x t$ .

With the array $n x t$ , we can easily determine the next time when we need to change an element, similar to the approach described in the greedy algorithm.

Since the number of changes can be large, doing them naively might be inefficient. Therefore, we can use a sparse table to make these calculations much faster.

Time complexity: $O (n lo g n)$

//in honor of TimDee

/*
In honor of Anton Tsypko
I want earrings with minecreaft
I want earrings with birbie
*/

//#include "fish.h"

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <bitset>
#include <cmath>
#include <string>

using namespace std;

//#define int long long


const int log_ = 21;
int inf = 1000000000ll;
int mod = 1000000007;

using ll = long long;


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n , q;
    cin >> n >> q;

    vector <int> a(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    ll p = 0;

    vector <ll> pref(n+1);


    for (int i = 0; i < n; i++)
    {
        p += a[i];

        pref[i + 1] = p;
    }


    vector <vector <int>> bin(n + 3);

    for (int i = 0; i < bin.size(); i++)
    {
        bin[i].resize(log_);
    }

    map<ll, int> mp;
    int rx = n + 2;
    for (int i = n; i >= 0; i--)
    {
        if (mp.count(pref[i]) != 0)
        {
            rx = min(rx, mp[pref[i]]);
        }
        bin[i][0] = rx;
        mp[pref[i]] = i;
    }
    bin[n + 1][0] = n + 2;
    bin[n + 2][0] = n + 2;

    for (int j = 1; j < log_; j++)
    {
        for (int i = 0; i <= n + 2; i++)
        {
            bin[i][j] = bin[bin[i][j - 1]][j - 1];
        }
    }
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;

        l--;


        int ans = 0;

        for (int j = log_ - 1; j >= 0; j--)
        {
            int lx = bin[l][j];

            if (lx <= r)
            {
                l = lx;
                ans += (1 << j);
            }
        }




        cout << ans << "\n";
    }
}

/*
7
*/