OpenJudge

1020:Challenge 13

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
262144kB
描述

给一个长为N的数列,有M次操作,操作仅有一种(每个位置刚开始都分别属于单独的一个集合):

合并两个位置所属的集合,并求出两集合间形成的逆序对数目

输入
第一行两个正整数N和M。
第二行N个整数表示这个数列。
接下来M行,每行是两个整数x和y,表示将x和y所属的集合合并,若x和y属于一个集合,则输出-1,否则输出将x所在集合放置在y所在集合前时,形成的逆序对数目。
输出
对每一个询问操作单独输出一行,表示答案。
样例输入
5 3
1 2 3 4 5
1 2
3 2
1 3
样例输出
0
2
-1
提示
1<=N<=10^5,1<=M<=10^5,输入保证合法,且所有整数可用带符号32位整型存储。
全局题号
5844
添加于
2014-01-24
提交次数
25
尝试人数
5
通过人数
5