Basically you implemented DSU using maps
I used pbds(ordered set) instead of treap but got TLE in all except first subtask although its time complexity is O(Q∗log(N)) per test case
Can someone explain what mistake I am doing Code
i also tried same approach but complexity of this algo this O(Q*log(q)*log(q)) which is around 4 * 10^9 which is resulting in TLE.
what is O(log*(n)) ? what is * ?
I thought segment tree will be used and my mind was moving around segment tree only. I just managed to get 20 points, but now when i see the editorial, i am like…
A very nice solution indeed!
\log_2(2*10^5)=19 whereas log^*_2(2*10^5)=4
Google it.
atleast give me a key word to search
Already gave. Search log^*(n)
The input size is huge, 10^{18}. Lazy propogation won’t make a difference. Dsu with path compression using maps will work fine as mentioned by editorialist.
yes…(20 char limit)
Thnks! got it now…
Is the bonus problem also for people who are using path compression??
Is it possible to solve this problem using Square Root decomposition?
By storing all the updated elements in an array of vectors and querying only those buckets which lie in the range l to r.
Works for all cases.
Using path compression/using union by rank/using both.
Easy modification.
yep
solution:- add a query of type 3 with 3 followed by the index of the element.
If the element is not zero before the update: Do nothing. Else: set par[par[node]]=node and del par[node]: This modification is for the code which is using path compression
wrong using only path compression complexity is q*α(q).
α is the inverse of the ackermann function and in CP terms α of a number is not more than 4.So linear complexity.
Okay. Cool. \hspace{1mm}
My solution with and without path compression takes equal time.
Does that mean union by rank is also O(4) ?
I am not sure about union by rank
I have used a similar approach as the tester, but I am getting TLE on the last subtask. Link to my solution : CodeChef: Practical coding for everyone