HBEAR - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

This problem can be solved in O(N^2+ N^3log N+ N^2 log N + K).
We first pre-compute the sum[x][y] where sum[x][y] means the number of honey in row-x column 1 to y, i.e cell[x][1]…cell[x][y]. Complexity for this part is O(N^2)

Then we can get the number of special rectangles with size exactly A x B satisfying the requirement (there must be at least K-units of honey) by fixing the left pointers and right pointers (thus we have fix size of column), after that perform the sweep operation to check the valid rectangles. Note that the sweep operation runs in O(N). You store the result in ans[A][B], ans[A][B] means the number of special rectangle satisfying the requirement with size exactly A x B. Complexity for this part is O(N^3 log N)

We then pre-compute the result of each query in an array called res[A][B]. res[A][B] means the number of special rectangles with the property that the size of the row is at most A and the size of the column is at most B. You can use 2-D BIT to compute res[A][B].

Complexity for calculating res[A][B] is O(N^2 log N). You can answer each query in O(1) and you have K queries thus the complexity becomes O(K).
P.S.: All variables are 1-based.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.