I - Infinite Inversions CodeForces - 540E

题意：一个无限的自然数序列进行n次操作，每次交换其中2个位置上的数，求逆序数个数。

题解：操作数很大，如果直接求逆序数个数会超时。而最多有1e5的操作次数，那么可以把点离散化，两个交换点之间加入新的点，该点的权值即是两个点之间的点的个数。离散化后用树状数组直接求其逆序数。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5 * 100010;
typedef long long ll;
struct node
{
    ll a,b;
}nod[maxn];
ll n,tot,cnt,ans;
ll p[maxn],x[maxn],y[maxn],w[maxn],sum[maxn];
ll lowbit(ll x)
{
    return x & -x;
}
void addnode(ll x,ll v)
{
    while(x <= maxn)
    {
        sum[x] += v;
        x += lowbit(x);
    }
}
ll getsum(ll x)
{
    ll res = 0;
    while(x > 0)
    {
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}
int main()
{
    scanf("%lld",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld %lld",&nod[i].a,&nod[i].b);
        x[++tot] = nod[i].a;
        x[++tot] = nod[i].b;
    }
    sort(x + 1,x + 1 + tot);
    ll len = unique(x + 1,x + 1 + tot) - x - 1;
    for(int i = 1;i <= len;i++)
    {
        y[++cnt] = x[i];
        w[cnt] = 1;
        if(x[i] + 1 < x[i + 1])
        {
            y[++cnt] = x[i] + 1;
            w[cnt] = x[i + 1] - x[i] - 1;
        }
    }
    for(int i = 1;i <= cnt;i++) p[i] = i;
    for(int i = 1;i <= n;i++)
    {
        int pos1 = lower_bound(y + 1,y + 1 + cnt,nod[i].a) - y;
        int pos2 = lower_bound(y + 1,y + 1 + cnt,nod[i].b) - y;
        swap(p[pos1],p[pos2]);
    }
    for(int i = cnt;i >= 1;i--)
    {
        ans += w[p[i]] * getsum(p[i]);
        addnode(p[i],w[p[i]]);
    }
    printf("%lld\n",ans);
    return 0;
}