Why I got a TLE with a complexity O(T * logn * logn)

Revision en1, by Subingbupt, 2024-09-24 17:29:25

contest link I got a TLE in G of this contest.

Let me brief you on the question.

There is an array a with a length n(2 <= n <= 1e5)(1 <= ai <= n) There are T queries(1 <= T <= 1e5) For every query, there are four integers l, r, p, q(1 <= l <= r <= n, 1 <= p < q <= n) Then, change the array. Keep the elements equal to p and q. Remove other elements. Output the inverse number of the array after changing. After every query, the array becomes to the initial one.

I came up with a divide and conquer algorithm.

Let me describe my solution.282174326

The key point lies in how to get the answer of the big problem(the range of [l, r]) after getting the answer of the small problem(the range of [l, (l + r) / 2] and the range of [(l + r) / 2 + 1, r]).

The inverse number of range[l, r] equals to the inverse number of range[l, (l + r) / 2] plus the inverse number of range[(l + r) / 2 + 1, r] plus the amount of q in range[l, (l + r) / 2] multiply the amount of p in range[(l + r) / 2 + 1, r].

I can get the amount of an element x in range[l, r] in O(logn) using binary search.

Of course, I need to get the ID vector for each element.

Tags divide and conquer, tle, ccpc, help me

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Subingbupt 2024-09-27 03:40:29 850
en3 English Subingbupt 2024-09-24 18:16:51 850
en2 English Subingbupt 2024-09-24 17:33:01 38
en1 English Subingbupt 2024-09-24 17:29:25 1264 Initial revision (published)