Dynamic Inversions II

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

给出N个数a[1],a[2] ... a[N],a[1]...a[N]是1-N的一个排列,即1 <= a[i] <= N且每个数都不相同。有M个操作,每个操作给出x,y两个数,你将a[x],a[y]交换,然后求交换后数组的逆序对个数 % 2。
逆序对的意思是1 <= i < j <= N 且a[i] > a[j].

Input

多组数据,每组数据:

两个数N,M,接下来一行有N个数a[1]... a[N]

最后M行每行两个数x,y

1 <= N,M <= 10^5, 1 <= x < y <= N,1 <= a[i] <= N

Output

对于每组数据,输出M + 1行,第一行是开始时的逆序对数目 % 2,接下去M行每行一个数,表示这次修改后的逆序对数目 % 2

Sample Input

2 1
1 2
1 2

Sample Output

0
1

Source

dream

Manager

Information
Solved Number39
Submit Number88
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel