Hello again Codeforces community!
I'm back with another problem, which I'm not able to solve. I don't have any link, it isn't from any site.
You are given a permutation of size N and Q queries. In 1 query, you are given x and y, and you need to swap the values on position x and y (formally, you need to swap v[x] and v[y]). After every query, you have to print the number of prefixes of the permutation, that are permutations.
For example, if you have array A = [2, 1, 3, 4], the answer is 3 (permutation at index 2, 3 and 4).
Example:
Input:
4 3
1 4 3 2
2 3
2 4 1 2
Output:
2 3 2
1 <= N, Q <= 100000.
The only approach I could come up with was brute force. Could anyone help me?
What is input format? It’s not clear from the example.
You are given N and Q. The next line contains the permutation. On every line of the last Q lines, there is a query (x, y) with the meaning from above.
Well, first of all, i thought about that. You also need another sum, let's say the sum of squares (this will guarantee that if both sums are equal, the prefix is a permutation). But this is where I got stuck, how can you count number of 0s fast in a range
I guess ans[i] >= 0 always, so number of 0s is equal to number of minimum, if minimum is 0. Seems like RMQ
Subtract $$$i$$$ from $$$v(i)$$$ (in the segment tree representation). Now, the segment tree would keep in its nodes the sum of values, the minimum value of any prefix sum, and the number of positions with this minimum value. Note that when swapping $$$x$$$ and $$$y$$$ the only nodes which have to be recomputed are are the ones containing either $$$x$$$ or $$$y$$$, so it’s only $$$O(log(n))$$$ of them.
Finally, after each update check that the value at the root is zero, and answer its count.
Yea, thanks. Now I realise how easy it was...
No worries. Here is the implementation and some code that asserts the correctness:
https://pastebin.com/1gBZFw1g