Hi. I am having problem trying to solve JOI 2013/2014 — Historical Research. The english problem statement can be found here.

For those who understand Japanese, the editorial can be found here

The input and output data can be found here

My approach is as follows:

Let product = element × frequency in subarray [L, R]

We use a BST to answer our max product queries and element updates efficiently, Each element of the BST would be  < product, element, frequency >  and the elements in the BST are sorted by product.

Let N be the number of elements in our array and Q be the number of queries.

Perform square root decomposition on the queries by breaking them into blocks and sorting them in increasing order of left bound followed by increasing order of right bound. Time-complexity of this operation is O(Q × logQ).

We keep 2 pointers to track the left and right bound of the subarray that we have calculated the element frequency for. Every time we shift the left pointer, we remove the elements from the left side of the subarray from the BST. Every time we shift the right pointer, we add the new elements in the subarray to the BST.

Of course, we have to update the product accordingly. Time-complexity of this operation is . This is because each query can only be in one block and block size is . Hence, the left pointer can only move by on each query (i.e. in total) and the right pointer moves by O(N) in every block and we have blocks. Hence, right pointer moves by in total. Finally, each movement incurs an update operation in the BST which is O(logN). That proves the time-complexity for this part.

Every time we need to query the maximum product, we just query the largest element in the BST, which is O(logN).

Hence, the total time-complexity is . However, 1 ≤ N, Q ≤ 100, 000, which implies that the algorithm will perform operations in the worst case (do note that the time-limit is only 4s). I tried coding this solution and as expected, it passed all but the last subtask (which uses the largest input).

Could someone please advise me on how I could optimize my solution's time-complexity?