Dynamic Inversions

Time Limit: 30000/15000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

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

Input

多组数据,每组数据:

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

再下去一行是M,最后M行每行两个数x,y

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

 

Output

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

Sample Input

2
1 2
1
2 1
3
1 2 3
3
1 2
2 3
3 1

Sample Output

0
1
0
1
2
1

Hint

第二个样例,一开始1 2 3,逆序对数为0,交换第1,2个元素,变为2 1 3,答案为1,交换第2和3个元素,变为2 3 1,逆序对数为2,交换第3和1个元素,逆序对数为1,此时序列变成1 3  2

Source

dream

Manager

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