Editorial for CCC '19 S5 - Triangle: The Data Structure


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.

Right-align the 2D array. If we iterate over the 2D array in increasing size order of minor diagonal, insert those values into a 2D max-BIT, we can query the bottom-right corner of a triangle the moment we have inserted all of the values in the given triangle into the 2D BIT, assuming the default values are otherwise zero. This approach is \mathcal{O}(N^2 \log^2 N).

Edit from another editorial author: You can solve it in \mathcal{O}(N^2 \log K).


Comments


  • 1
    31501357  commented on Feb. 22, 2023, 12:17 a.m. edit 2

    If anyone is confused, minor diagonal is bottom left to top right, or a1-h8 diagonal for chess. The query you want to do is the rectangle from (0, 0) to (x, y) where x is the rightmost column of the triangle and y is bottom row. To insert the diagonals, perform BIT update operation on all A[i][j] such that i+j=m for m from 2n-2 to n. You MUST make the query IMMEDIATELY after inserting the last diagonal of a subtriangle, otherwise, the query will contain numbers outside the subtriangle you wish to query.

    For example.

    4 2
          3
        1 2
      4 2 1
    6 1 4 2

    After inserting the bottom right subtriangle.

    0 0 0 0
    0 0 0 0
    0 0 0 1
    0 0 4 2

    Query (0, 0), (3, 3) before inserting anything else.

    After inserting the next diagonal.

    0 0 0 0
    0 0 0 2
    0 0 2 1
    0 1 2 4

    Immediately query (0, 0, 2, 3) and (0, 0, 3, 2) before inserting the next diagonal.

    Edit: You need a corner at the bottom right since for a MAX binary indexed tree, there is no inverse operation as opposed to a SUM BIT, so you the origin must be the corner for any query.

    Edit 2: Zero is the default value because it's smaller than any possible input value, of course if the input contained negative numbers you'd fill the matrix with something like -99999999. This is so they don't affect the queries, and so that performing the BIT update operation actually inserts the input number into the BIT. Also some modifications above.


  • 5
    Nils_Emmenegger  commented on Sept. 11, 2021, 7:50 p.m.

    In case you are curious or are having trouble passing with the \mathcal{O}(N^2\log^2 N) solution due to TLE (this sub barely passes with a 0.983s worst case), the \mathcal{O}(N^2\log K) mainly relies on the observation that the maximum element of a sub-triangle of a certain size can be found by taking the maximum of three sub-triangles with sizes two-thirds of the one that we want to find. Thus, starting from sub-triangles of size 1, we can keep solving for sub-triangles that get about 50% bigger each time, allowing us to find the maximum elements in sub-triangles of the desired size in \log K steps.

    Another way of going about it is observing that the maximum element of a sub-triangle of a certain size can be found by taking the maximum of two sub-triangles and one square whose sizes and side lengths respectively are half of the size of the sub-triangle we are trying to find.

    Both methods personally remind me of the construction of sparse tables.


    • 2
      DynamicSquid  commented on Feb. 16, 2022, 1:32 a.m.

      Won't you be skipping numbers of a triangle if you increase the size of a triangle by more than 1 each time?


      • 2
        andy_zhu23  commented on Feb. 16, 2022, 1:45 a.m.

        yes, but it doesn't matter, since you are able to get the maximum of each current triangle using the sub triangle 2/3 of the size of the current one anyway.