Hi.
I started from a SQRT decomposition and then moved to a SegmentTree based solution.
My idea is to maintain a global variable CURR which simply contains the last used group-id.
Build an array BLOCK which contains the current group-id of each element and an array LASTIN which contains, for every group-id, the index of the last contained element.
Then build a SegmentTree which supports lazy propagation over BLOCK and is able to retrieve (over a query [L, R]) the current group-id of element L.
For any query of type 2 just use binary search. The cost is O((log N)^2) (because we need log N queries over the tree).
For query of type 1 is a bit intricate I think… let’s discuss salient events. Suppose to change the value at an index 1 <= i <= n - 2 (0 based indexing). The new value could merge 2 segments or split an existing one. For the first case just call an update over the SegmentTree for [i, LASTIN[query(i + 1)]] to set the range to query(i - 1). For the second case we have to set [i + 1, LASTIN[query(i + 1)]] to (++ CURR) (because it is a new group now) and choose where putting the new element at position i (in the previous, in the successive or alone). Anyway it’s just another update of Tree and LASTIN.
However, I am not getting AC. Maybe there are some errors in the implementation. That would not be a problem.
I would like to know if someone sees some logical errors in my approach. That would be.