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], because p < q.
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 before all the queries.
Your solution is actually $$$O(n * T * logn)$$$, since you run divide and conquer algorithm for each query, and each time it visits $$$O(n)$$$ segments, for each segment doing cnt query, which takes $$$O(log n)$$$ time,
thanks for your reply, but why n * logn for each query
In D&C, if you are in segment $$$[tl,tr]$$$, where $$$tl \lt tr$$$, you descend downwards to segments $$$[tl,(tl+tr)/2]$$$, $$$[(tl+tr)/2+1,tr]$$$, until $$$tl=tr$$$.
As such, if you run some query($$$tl,tr,p,q$$$), it will visit all segments $$$[i,i]$$$, where $$$tl \lt =i \lt =tr$$$, and there are $$$O(n)$$$ of them.
I think you confused this with something like segment tree, but important difference in segtree is that you exit node each time you are fully in/out query segment.
thank you so much!