求解逆序对（不一样的离散化加权值线段树）

题意：原本是一个从1到n的数组，给你一些对(x,y)让你交换，交换完后求逆序对的个数，这里x和y到1e9
思路，将区间合并为点，再离散化，之后归并，权值线段树，树状数组正常求逆序对即可

#include<cstdio>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
const int maxn = 100005;
struct node{
    int x,y;
    node(int _x,int _y):x(_x),y(_y){
    }
    node(){
    }
}res[maxn*3];
struct tree{
    int l,r,sum;
}t[maxn*8];
void build(int l,int r,int k){
    t[k].l=l;
    t[k].r=r;
    t[k].sum=0;
    if(l==r){
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
}
void insert(int p,int summ,int k){
    if(t[k].l==t[k].r){
        t[k].sum+=summ;
        return;
    }
    int mid=(t[k].l+t[k].r)/2;
    if(p<=mid) insert(p,summ,k*2);
    else insert(p,summ,k*2+1);
    t[k].sum=t[k*2].sum+t[k*2+1].sum;
}
int ans=0;
void search(int l,int r,int k){
    //printf("%d %d %d %d %d %d\n",t[k].l,t[k].r,t[k].sum,l,r,k);
    if(l<=t[k].l&&t[k].r<=r){

        ans+=t[k].sum;
        return;
    }
    int mid=(t[k].l+t[k].r)/2;
    if(mid>=l) search(l,r,k*2);
    if(mid<r) search(l,r,k*2+1);
}
map<int,int> mp;
int x[maxn];
int y[maxn];
int all[maxn];
signed main(){

    int k;
    scanf("%lld",&k);
    for(int i=0;i<k;i++){
        scanf("%lld%lld",&x[i],&y[i]);
        all[2*i] = x[i];
        all[2*i+1] = y[i];
    }
    sort(all,all+2*k);
    int n = unique(all,all+2*k)-all;
    //for(int i=0;i<n;i++)     printf("%d ",all[i]);
    int now=0,sum=0;

    for(int i=0;i<n;i++){
        if(all[i]-now>1){
            res[sum] = node(sum,all[i]-now-1); 
            sum++;
        }
        //printf("%d",sum); 
        res[sum] = node(sum,1);
        mp[all[i]]=sum;
        sum++;
        now = all[i];
    }

    //printf("%d %d %d",mp[2],mp[1],mp[10]);
    for(int i=0;i<k;i++){
        int xx=mp[x[i]];
        int yy=mp[y[i]];
        node a = res[xx];
        res[xx] = res[yy];
        res[yy] = a;    
    }
    build(0,sum-1,1);
    int las=0;
    for(int i=sum-1;i>=0;i--){
        //printf("a %lld %lld\n",res[i].x,res[i].y);
        ans=0;
        search(0,res[i].x,1);
        ans*=res[i].y;
        //printf("%d\n",ans);
        las+=ans;
        insert(res[i].x,res[i].y,1);
    }
    printf("%lld\n",las);

    return 0;
} 
/*
2
1 15
7 27
*/