Observing the constraints, it’s pretty obvious that approximate O(n × log(n)) solution is needed to pass. So, we need a data structure that can join two disjoint sets and measure the current size of any set efficiently. Disjoint Set Union (DSU) is a data structure that can perform these efficiently. Type 1 and Type 2 queries are pretty straightforward operations in DSU actually. In type 1 queries, we will store the assignment operations in a vector or an array.
Let's focus on type 3 queries. Student u and a special number x are given. We will iterate from the last valid assignment operations to the first valid assignment operations and roll back the updates that occurred in the i-th assignment operation. While iterating and rolling back, if the size of the team of student u becomes less than x in an operation, that means this operation is the special operation, and we will stop iterating. As we have rolled back the updates of this special operation already, we have to execute this operation again. The later valid assignment operations after this special operation are already rolled back. So, they have no effect on our DSU structure now. Don’t forget to erase those later operations from the vector. Erasing can be done in O(n). Now, we can print the size of the student u’s team.
Why this will fit in time limit? Look, we are rolling back the updates of a canceled assignment operation only once. After that, we are erasing them from the vectors. In each iteration, we are finding the size of the student u’s team which can be performed in O(log(n)). So, the whole iteration, rolling back and checking size procedures have O(n × log(n)) complexity.
