Chef and Swaps
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
This time, Chef has given you an array A containing N elements.
He had also asked you to answer M of his questions. Each question sounds like: "How many inversions will the array A contain, if we swap the elements at the i-th and the j-th positions?".
The inversion is such a pair of integers (i, j) that i < j and Ai > Aj.
The first line contains two integers N and M - the number of integers in the array A and the number of questions respectively.
The second line contains N space-separated integers - A1, A2, ..., AN, respectively.
Each of next M lines describes a question by two integers i and j - the 1-based indices of the numbers we'd like to swap in this question.
Output M lines. Output the answer to the i-th question of the i-th line.
- 1 ≤ N, M ≤ 2 * 105
- 1 ≤ i, j ≤ N
- 1 ≤ Ai ≤ 109
- Mind that we don't actually swap the elements, we only answer "what if" questions, so the array doesn't change after the question.
Input: 6 3 1 4 3 3 2 5 1 1 1 3 2 5 Output: 5 6 0
Inversions for the first case: (2, 3), (2, 4), (2, 5), (3, 5), (4, 5).
Inversions for the second case: (1, 3), (1, 5), (2, 3), (2, 4), (2,5), (4, 5).
In the third case the array looks like 1 2 3 3 4 5 and there are no inversions.
|Tags||berezin, fenwick, inversions, medium, sept14|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.