[CF540E] Infinite Inversions

Description

现在有一个由所有正整数组成的无限递增序列。对这个序列执行 (n) 次交换操作。每次一个操作，给出两个整数 (a,b)，交换位置 (a) 和 (b) 处的元素。在所有操作结束后，输出最终序列的逆序对个数。

Solution

离散化，利用左闭右开区间 ([l,r)) 作为单个结点

离散化后直接交换，交换后用按照顺序从小到大扫一遍，线段树统计即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2000005;

int n,t1,t2,ind;
map<int,int> mp;
vector <int> vec_value;

struct Node
{
    int l,r,id;
    int len()
    {
        return r-l;
    }
};

vector <Node> vec;
map<int,int> single_index;
int ida[N],idb[N];

int a[N];

void modify(int p,int l,int r,int pos,int key)
{
    a[p]+=key;
    if(l<r)
    {
        if(pos<=(l+r)/2) modify(p*2,l,(l+r)/2,pos,key);
        else modify(p*2+1,(l+r)/2+1,r,pos,key);
    }
}

int query(int p,int l,int r,int ql,int qr)
{
    if(l>qr || r<ql) return 0;
    if(l>=ql && r<=qr) return a[p];
    return query(p*2,l,(l+r)/2,ql,qr) + query(p*2+1,(l+r)/2+1,r,ql,qr);
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t1>>t2;
        mp[t1]++;
        mp[t2]++;
        ida[i]=t1;
        idb[i]=t2;
    }

    for(auto &i:mp)
    {
        vec_value.push_back(i.first);
    }

    if(vec_value.size()) 
    {
        int i=0;
        vec.push_back({vec_value[i],vec_value[i]+1});
        single_index[vec_value[i]]=vec.size()-1;
    }

    for(int i=1;i<vec_value.size();i++)
    {
        if(vec_value[i]>vec_value[i-1]+1)
        {
            vec.push_back({vec_value[i-1]+1,vec_value[i]});
        }
        vec.push_back({vec_value[i],vec_value[i]+1});
        single_index[vec_value[i]]=vec.size()-1;
    }

    int m=vec.size();

    for(int i=0;i<m;i++)
    {
        vec[i].id=i+1;
    }

    for(int i=1;i<=n;i++)
    {
        int p=single_index[ida[i]], q=single_index[idb[i]];
        swap(vec[p],vec[q]);
    }

    /*for(int i=1;i<=m;i++)
    {
        cout<<vec[i-1].l<<" "<<vec[i-1].r<<endl;
    }
    cout<<endl;*/

    int ans=0;

    /* Brute force version
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            if(vec[i-1].l > vec[j-1].l)
            {
                ans+=vec[i-1].len()*vec[j-1].len();
            }
        }
    }*/

    for(int i=0;i<m;i++)
    {
        ans+=query(1,1,m,vec[i].id+1,m)*vec[i].len();
        modify(1,1,m,vec[i].id+1,vec[i].len());
    }

    cout<<ans<<endl;
}