Editorial for Inaho II


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

The solution to this problem is simply an N-dimensional Binary Indexed Tree (BIT).

One needs an efficient method to sum an N-dimensional hypercuboid. This means that the final code should have an extremely small constant factor. For the summation formula, one should utilize the Inclusion-Exclusion Principle to determine which of the 2^N queried corners of the N-dimensional hypercuboid to add, and which to subtract. That is, for corner i, the query consists of summing the density between (1\ 1 \dots 1) to (x_{i_1}\ x_{i_2} \dots x_{i_N}). This can be done using N for loops (which is impractical), or a recursive function.

In addition, instead of using an N-dimensional array to store the Binary Indexed Tree, one should use a 1-dimensional array of size 10^7. Given the N indices in the summation/update statements, a prefix or a suffix product array can be utilized to calculate the actual index in the 1-dimensional array.

A sample recursive function in C++ is shown.

int binary_indexed_tree[10000005], prefix_product_array[11];

int query(const int N, int current_dimension, int pos, int idx[])
{
    if (current_dimension == N)
        return binary_indexed_tree[pos];
    int sum = 0;
    for (int x = idx[current_dimension]; x > 0; x-=x&-x)
        sum += query(N, current_dimension+1, pos + (x-1) * prefix_product_array[current_dimension], idx);
    return sum;
}

However, this function is too slow and TLEs. Instead of calling said recursive function 2^N times, each with a different corner, and then figuring out which of these corners to add, and which to subtract, one needs a method of directly summing the hypercuboid in one recursive function call. With some thought, one can figure out that the above function only needs to be slightly modified. That is, for each dimension, one needs to add the upperbound indices (like the for loop shown above), and subtract the lowerbound indices. This can be accomplished with another for loop that subtracts the query() calls instead of adds them. Implementation is left as an exercise for the reader. Although the time complexity is the same for complexity analysis, the latter solution has a smaller constant factor.

An update statement should be approached similarly. A recursive function can be utilized to update a certain index. In fact, the above recursive function can be slightly modified into an update function, and this will not TLE since this function only needs to be called once per update statement.

An update recursive function in C++ is shown below.

int binary_indexed_tree[10000005], prefix_product_array[11], dimension_length[11], actual_array[10000005];

void update(const int N, int current_dimension, int pos, int idx[], int value)
{
    if (current_dimension == N)
    {
        binary_indexed_tree[pos] += value;
        return;
    }
    for (int x = idx[current_dimension]; x <= dimension_length[current_dimension]; x+=x&-x)
        update(N, current_dimension+1, pos + (x-1) * prefix_product_array[current_dimension], idx, value);
}

Note that the time limit was set very strict such that solutions which were not optimized TLE's. On a worst case, the intended solution in C++ takes approximately 2 seconds.

Time Complexity: \mathcal O\left(Q \times 2^N \times \prod_{i=1}^N \log l_i\right)


Comments

There are no comments at the moment.