CK87DANC Editorial

general
, , , , ,
1

Problem Link:

Practice

Contest

Author: Mohammad Shahhoud & Said Sryhini

Tester: Hasan Jadouh

Editorialist: Said Sryheni

Difficulty:

Medium.

Prerequisites :

Prefix XOR, Trie Tree, Minimum Range Lazy Segment Tree, Sweep Line.

Problem:

Given an array of N elements and an integer M, you are to answer Q queries. In each query you are given two integers L and R. You are to find the minimum range [i, j], that falls completely inside the range [L, R], and the logical XOR of its elements is no less than the given integer M.

Explanation:

Main algorithm:

  1. For each index i find the smallest range that ends at i, and the XOR of its elements is no less than M using a trie tree.

  2. Build a minimum range lazy segment tree whose leaves are the given queries sorted in non-decreasing order by their ending R.

  3. Answer the queries offline. Sweep over the indexes and the left side of each query.

  4. When encountaring the start of a query activate its corresponding location inside the segment tree.

  5. When encountaring an index, get the smallest range that starts at i (let’s denote the end as j), and lazy update all the queries that end in the range [j, \infty[ with the length of the range [i, j].

  6. Iterate over all the queries and get their answer through a query to the segment tree.

Extended Explanation:

First let’s find a more efficent way to calculate the XOR of all the elements inside a given range. We can do so by calculating the prefix XOR for each index in the given array. Let’s denote such an array as Pref, where Pref_i = Pref_{i - 1} \oplus D_i. Now the logical XOR for all the elements in the range [L, R] can be calculated as Pref_R - Pref_{L - 1}.

Consider the binary representation of the values of Pref over a 30-bit representation. Create a trie tree, where each node has two children {0, 1} denoting the bits of the elements from the given array. The root of the trie tree will contain the most significant bit, while the leaves will contain the least significant bits.

Iterate over array’s elements from left to right. For each index i, we need to find the largest index j such that Pref_i - Pref_{j - 1} \le M. In order to do so, for each index first insert the value of Pref_{i - 1}. Now we need to find the largest index inside our trie tree, such that the above mentioned operation holds true. In other words we need to query the formed trie tree passing the value of Pref_i. While iterating over the trie, let’s define the corresponding bit of M as B_m and the corresponding bit of Pref_i as B_i. Also, for each node let’s store the value of the maximum index whose binary representation passes through this node, let’s denote it as MX. In each node we may encounter one of the following two conditions:

  1. B_m = 1. In this case we have no other choice but to go to the child whose value is 1 - B_i. This is because to get the value of 1 out of an XOR operation, we need to have two different bits.

  2. B_m = 0. In this case we have two option:

    • Either go to the child whose value is B_i, because the XOR of the same bit is 0. Note that in this case the calculated value still equals to M.
    • Or go to the child whose value is 1 - B_i. This will give us a resulting bit that equals to 1. In this case the formed value is already greater than M, and there’s no need to further investigate the subtree of the current node since we already know the value of the largest index that passes through this node, and it’s stored in the variable MX, so we simply return it.

Obviously when reaching a leaf node, we need to return the value of MX.

So far we manages to understand how to efficentely handle step number 1. Now the problem reduces to: Given ranges [i, j] and queries [L, R], find for each query the smallest range [i, j] that falls completely inside the range [L, R].

Moving to step 2 We build a minimum range lazy segment tree whose leaves are the given queries sorted in non-decreasing order by the value of their R. The initial value of each query must be -\infty.The purpose of such segment tree will be explained below.

Sweep over both the left side of each query [L, R] and the left side of the calculated ranges [i, j].

  • When encountering a query [L, R] activate its corresponding leaf by setting its value to \infty.

  • When encountering a range [i, j] we know for sure that all the queries whose left side is smaller than i has already been activated. Among these queries, only the ones that end at R >= j actually covers the current range. Since the queries [L, R] inside our segment tree are sorted in non-decreasing order of their end R, we can lazy update all these queries in our segment tree. In other words update all the queries whose ending R is in the range [j, \infty[. Please pay special attention that 2 queries may have the same ending, so to find the first query whose R is no less than j we perform a simple binary search opearation over the queries array which is sorted in non-decreasing order by their end.

After sweep operation is finished, we can now simply iterate over all the queries by the order given in the input, and query our segment tree for their value.

Time Complexity: O((N + Q) . (log(Q) + log(N)) + N . log(10^9))

Check setter and tester solutions for the implementation.

Solution 1

Solution 2

1 Like