Yes indeed.This problem can be solved using sqrt decomposition.

Does anybody have Java implementation for the same?

I solved is with sqrt decomp and dsu. My java solution TLEd tho so I just ported it to c++ to get it to pass. I think it's probably solvable with sqrt decomp in java but you might need to do something smarter than I am or perhaps add some more optimizations. JAVA: 33816939 C++ : 33817280

Here's my AC Solution : 33799911 .

I did get TLE in one of my submission on Test 2, link : 33755328, it was due to way the elments in one bucket were shifted from x to y. Intially, I used merge() to shift element to y and then delete the elements from x. This leads to TLE. After using splice() , if worked fine till test case 114, because of way I've coded the process,made necessary changes in the implementation, and it works in 2047ms.

I did see a submission with sqrt decomposition working in ~970ms. link :33736310

Well, SQRT decompostions works for this problem. It's only the way they have been implemented in the code leads to TLE.

I don't have much knowledge of Java implementation, so can't help with your code.

Here's a link to an interesting question, it asks you to change element x to y in range l to r, and also count element x in range l to r : https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/replace-27c5286c/ , consider it as more advance version of this question. Tester's (Bohdan Pryshchenko) solution is in C++.