The 9 Axioms of the Universe#11767

The 9 Axioms of the Universe (Editorial)

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

Let's define the prefix sum array $p$ , where $p_{0} = 0$ p_0 = 0 and $p_{i} = p_{i - 1} + a_{i}$ p_i = p_{i-1} + a_i for each $i > 0$ i > 0. A segment $[l, r]$ [l, r] has a sum of $0$ if and only if $p_{r} = p_{l - 1}$ 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}$ 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}}$ \{p_i\}.
If $p_{i}$ p_i is not in $b$ , add $p_{i}$ p_i to $b$ ( $b := b \cup {p_{i}}$ 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}}$ go_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$ l \geq i with $p_{l} = p_{r}$ 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)$ O(n \log{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
*/

C++