求逆序对

但这肯定不是普通的求逆序对题目：数据范围太大了，会超时。

尽管数据范围很大，但是k不大，最多只牵涉到了2k个数。

我们举个例子：

需要交换的两组数是：1—6 , 4—9。

我们可以发现，数2、3可以看做一个整体，数7、8可以看做一个整体。

也就是说，一段连续的数，我们可以把它看做一个整体，记录下它的代表元id和权值t。

什么意思呢？我们来看处理之后应该是怎样的：

（1,1) ， (2,2) ， (4,1) ， (5,1) ， (6,1) ， (7,2) ， (9,1)

我们就把所有的连续区间记做了二元组。用这个区间最小的数作代表元，权值就是区间数的个数。

然后进行交换：

（6,1），（2,2），（9,1），（5,1），（1,1），（7,2），（4,1）

剩下的就是普通的求逆序对了。

别忘了离散化。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,st,tot;
struct aaa{
    int x,y;
}Q[N];//记录需要交换的数
int t[2*N],id[2*N];//t:权值。id:代表元
int s[2*N],row[22*N];
ll ans,c[2*N];

int query(int val){//离散化的查询
    return lower_bound(row+1,row+1+tot,val)-row;
}

void adds(int pos,ll w){//
    for(;pos<=tot;pos+=pos&-pos) c[pos]+=w;
    return;
}

ll asks(int pos){
    ll sum=0;
    for(;pos;pos-=pos&-pos) sum+=c[pos];
    return sum;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&Q[i].x,&Q[i].y);
        s[i]=Q[i].x;s[i+n]=Q[i].y;
    }
    sort(s+1,s+1+2*n);
    st=unique(s+1,s+1+2*n)-(s+1);
    row[++tot]=s[1];t[tot]=1;
    for(int i=2;i<=st;i++){
        if(s[i]-s[i-1]>1){
            row[++tot]=s[i-1]+1;
            t[tot]=s[i]-s[i-1]-1;
        }
        row[++tot]=s[i];t[tot]=1;
    }
    for(int i=1;i<=tot;i++) id[i]=i;
    for(int i=1;i<=n;i++){
        int x=query(Q[i].x),y=query(Q[i].y);
        swap(t[x],t[y]);
        swap(id[x],id[y]);
    }
    for(int i=tot;i>=1;i--){
        ans+=asks(id[i]-1)*(ll)t[i];//注意，乘法 
        adds(id[i],(ll)t[i]);
    } 
    printf("%lld",ans);
    return 0;
}