Lately I have been solving this problem, lucky array. I implmented a O(m log n + 30 * n log n) where n, m <= 1e5(my submission). My solution got tle in some test cases. And I have found that the solution in the editorial is the same as mine. Then I tried using bottom-up segment tree instead of top-down but it didn't aid the issue.

I think the main reason that causes the tle is because the execution time is multiplied by 2. And that is too much. I had once encounter the same issue but with different tasks, I managed to optimized well and passed. But I couldn't this time. I think that maybe the time limit should be increased if the execution time have to be multiplied by 2 ? Or it would become a constant optimizing problem.