Hello everyone. Last week my teacher gived me a problem and told me to solve it using sqrt, but it wasn't easy for me and when I tried to find a solution using sqrt I didn't found any answer and know I want to write a blog of solve 916D using sqrt for next people who want to solve this problem by sqrt.

This blog is my first blog and I appologize if it isn't good enough.

In this problem we should handle five queries:

1- Add a new word to to-do list with a priority.

2- Change priority of a word.

3- Remove a word from to-do list.

4- Find how many words have a priority less than priority of given word.

5- Change the to-do list to its last versions.

The main idea of the solution is that we can decompose the to-do list to blocks with langth at most T and than when we want to make a change in to-do list, we can just make a change in one block; but we in this problem we should save the last versions of to-do list, so we dublicate that block we must change it and now we change the new block (we can maintain the blocks in a vector or array). Also we should save an array of length n/T for each query, that contain indexes of blocks of that version of to-do list, thus for undo query we should just copy the array of target version in new version.

At next we should have two type blocks:

1- A block that contain priorities in not decreasing order (it can be vector or array) so we can find how many priorities are less than given priority for any block with binary search (using lower_bound).

2- A block for find that a word is in the i-th block or not and if it is in i-th block then what is its priority (at first I used unordered_map but it's better with array).

In the next step of solving we should convert the words to integers using unordered_map or map (unordered_map is better) and we should make an unique id for any word, by doing this we can say a word with k * T ≤ id < (k + 1) * T must go to k-th block of each queriy's array of blocks.

For first query in the block of second type we set priority of given word equal to given priority and we add given priority to block of first type using insert method of vector (it take O(T) operations) (if a word's priority is zero in second type block, then it isn't exists).

For second query we change the priority of given word in second type block and we remove the old priority of first type block using erase method of vector and we insert the new priority in that block by insert method of vector (it takes O(T) operations).

For third query we just erase the word's priority from first type block and we set priotity of that word equal to zero in second type block.

For fourth query we go through blocks of first type in array of that version of to-do list and using lower_bound we find number of priorities less than given word's priority in each first type block.

For fiveth query we just copy the target version of to-do list is the new version of to-do list.

You can see my solution code in 225492217.

Thanks for reading my first blog and sorry for my poor english.

I'm waiting to read your usefull comments for my next blogs.