Lemur95's blog

Need help with this interesting problem
By Lemur95, history, 4 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is input format? It’s not clear from the example.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  • i think you have to use range sum queries
  • assuming x<y, when you swap v[x] and v[y], only validity at indecies x,x+1,...,y-1 will change
  • at index n, it will be valid only if prefix_sum(1, n) == n*(n+1)/2 so all numbers from 1 to n exists
  • let ans[i] = prefix_sum(1, i) — (i*(i+1)/2), this means that i is valid only if ans[i] == 0
  • i didn't reach a full solution, but what left is how to count number of zeros in ans after performing range sum query which make prefix_sum valid after every swap
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I guess ans[i] >= 0 always, so number of 0s is equal to number of minimum, if minimum is 0. Seems like RMQ

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply