CF竞赛题目讲解_CF540E(树状数组)

//https://codeforces.com/problemset/problem/540/E

//题意：给定一个连续的 increasing 无限序列{1,2,3,4,5,6…}，然后给出几个区间，将区间2端的值进行swap，最后求有多少个逆序对。即 i < j and a[i] > a[j].

//思路

// 将题目要进行交换的点都保存下来，然后再把中间没有出现的区间离散化成一个点，权值是这段区间有几个数据。

/* 例如

2

1 4

5 9 

就可以转化成 1 2 3 4 5 6 . 其中 2代表【2,3】权值为2，5代表【6,7,8】权值为3。 */

/* 然后用一个vecotr保存这些转化后的点，vector里面存一个pair,pair的first代表这个点的起始值，second代表有多少个数，

5所代表的【6,7,8】 所以second保存的是3，first保存的是6。

用一个id数组存储转化后的各个数在树状数组中的序号，

然后在vector中查找位置进行端点交换，最后id数组保存的就是交换后的位置，然后逆序求一下逆序对就即可。

*/