ASISTENT - Asistent
You are given a permutation of first N natural numbers on which you are to perform K operations of following type: given integers A and B, your task is to swap elements on positions A and B in permutation and then output permutation rank modulo 1000 000 007.
Note: Difference from original task is that elements remain swapped after query.
Input
On first line of standard input you are given two integers (2 ≤ N ≤ 50 000, 1 ≤ K ≤ 30 000), length of permutation and number of operations.
On the next line there is permutation of first N natural numbers.
In next K lines there are two integers A, B ( 1 ≤ A, B ≤ N ).
Output
Output permutation rank after applying each of K operations.
Example
Input:
5 3
1 5 4 2 3
1 3
2 3
2 5
Output:
91
77
90
hide comments
shahidul1004:
2020-06-09 09:09:11
which algorithm is needed for this problem? |
|
Scape:
2016-03-08 23:03:13
Time limit is indeed too strict. O(N log^2 N) times out... |
|
applepi:
2011-09-15 02:07:18
Time Limit may be too strict T_T |
|
Vladimir Kirichenkoff:
2010-07-30 22:53:02
it's a number of the permutation. For example, rank 123 - 1, rank 132 - 2, rank 213 - 3, rank 231 - 4, rank 312 - 5, rank 321 = 6. |
|
Ivan Katanic:
2010-11-07 13:53:53
Yes, but you probably have big constant factor. Your solution times out on 6th case and it would fail even if time limit is 10 s, so far accepted solutions passed even 10th test under 6-7 s. |
|
Lox:
2010-06-27 11:47:05
Is an O(NlogN+K(logN)^2) approach expected to be accepted? I've got TLE. :S
|
Added by: | Ivan Katanic |
Date: | 2010-06-23 |
Time limit: | 1.585s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | Modified task from Croatian IOI Team Selection Test |