题目链接

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

题目大意

最初一个数组里面全是严格单调递增的，交换若干对数，求最终逆序数。

解题思路

好难啊！
详细地说一下思路，网上找了好多题解，看了半个晚上才明白的。
大致思路：
离散化+树状数组。
详细思路：

S1：

想的是先都交换完了，再树状数组求一下逆序数就行，但是很显然数组开不下这么大的。而交换次数为1e5，那么最多存在2e5个数被交换了，所以可以离散化处理一下。
对应到下面代码：
用orig数组的含义是origin，用来存储最开始被交换的数的大小。
之后就是标准离散化代码了，
都做到这种题了，不会还有人不会离散化吧，不会吧，不会吧，不会那个人就是你吧
都做到这种题了，不会还有人不会树状数组吧，不会吧，不会吧，不会那个人就是你吧

S2：

对now进行初始化，now[i]=i，同时refl数组的含义是reflect映射，refl[i]表示数值为i的数在now数组中对应的编号，refl[orig[i]]表示在orig数组中第i大（已经排好序了）的被交换的数在now数组中的编号。
开始数组orig是排好序的，所以now也是按照1，2，3……初始化的，即orig[1]对应编号为1，orig[2]对应编号为2……。

S3

对我们新建的now数组进行交换操作，详见代码注释

S4

首先我们讲解一下，为什么要可以通过求交换数与交换数之间的逆序对+交换数与非交换数之间的逆序对得到答案。因为很显然，原数组为单调递增序列，根本不存在逆序对，未被交换的数与未被交换的数之间不存在逆序对，所以交换数与交换数之间的逆序对+交换数与非交换数之间的逆序对，即为答案。
对于求交换数之间的逆序对比较好求，只要树状数组对离散化后的交换数数组（即now数组）求一下逆序对就行；
而对于非交换数与交换数之间的逆序对就不是很好求了。
举个例子：
图片说明
交换5和9，6 ~ 8是不会改变的，（所以非交换数之间的逆序对是不会变的），看一下交换操作是如何对逆序数产生影响的。只看框内的数（因为只考虑交换数与非交换数之间产生的逆序数），在交换前，6前面原来不存在比6大的，但是现在多了个9，逆序数+1；同样的7前面也多了个9，逆序数+1，8前面也多了个9，逆序数+1，这样一来就算出了交换数9与非交换数6~8对逆序数的影响了。5本来位于序列最前面，但是现在却被在6，7，8之后了，逆序数+3，（还是注意不考虑9对5逆序数的影响，因为我们只讨论交换数与非交换数，而5和9对逆序数的影响，其实已经在“交换数之间的逆序数的影响”中讨论过了）。好了那么交换数与非交换数之间产生的逆序数就是交换数之间的数的个数吧。但是这是交换数9和5之间没有其他交换数的情况，要是9和5之间也存在其他交换数，我们就要去掉某些情况。

显然，10是交换数吧，与6交换了，要不然它怎么会到5 ~ 9之间呢。
在讨论交换数5或9与非交换数对逆序数的影响时，要把与计算交换数之间对逆序数重复的部分删除掉，所以单单数出5和9之间的数的个数是不行的，会重复计算交换数之间的逆序数，所以我们要减去5和9之间交换数产生的逆序数的个数。
详解见代码注释。

树状数组求逆序数，
不会吧不会吧，不会真的有人还不会求逆序对吧，不会吧不会吧，不会那个人就是你吧

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+100;

map<int,int> refl;
ll ans,c[N<<1];
int n,now[N<<1],orig[N<<1],cnt;


ll lowbit(ll x)
{
    return x&(-x);
}
ll getsum(ll x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(ll x,int num)
{
    while(x<=cnt)
    {
        c[x]+=num;
        x+=lowbit(x);
    }
}
struct op
{
    ll a,b;    
};
op s[N];//s表示swap操作的两个对象

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i].a>>s[i].b;
        orig[++cnt]=s[i].a;
        orig[++cnt]=s[i].b;
    }
    //离散化//S1
    sort(orig+1,orig+cnt+1);
    cnt=unique(orig+1,orig+cnt+1)-orig-1;
    //S2
    for(int i=1;i<=cnt;i++)
    {
        now[i]=i;
        refl[orig[i]]=i;
    }
    //S3
    for(int i=1;i<=n;i++)
    {
        int p=refl[s[i].a],q=refl[s[i].b];//通过reflect一下被交换数，得到其在now数组中的编号，对now数组进行交换
        swap(now[p],now[q]);
    }
    memset(c,0,sizeof c);//可有可无
    //S4
    for(int i=1;i<=cnt;i++)//求交换数与交换数的逆序数
    //注意这里是求交换数与交换数之间的逆序数，所以直接通过now数组就行，
    //因为我们只需要直到被交换数之间的大小关系就行，
    //所以用编号（即离散化后对应的数值）来计算是完全没问题的
    {
        update(now[i],1);
        ans+=i-getsum(now[i]);
    }
    for(int i=1;i<=cnt;i++)//求交换数与非交换数的逆序数
    {
        ans+=abs(orig[now[i]]-orig[i]-1)-abs(now[i]-i-1);//now[i]与i互为交换数对应的编号，通过orig访问到对应的交换数，再做差；后者的abs表示now数组的差即为重复的部分
    }
    cout<<ans<<endl;
}