Infinite Inversions(树状数组+离散化)

思路及代码参考：https://blog.csdn.net/u014800748/article/details/45420085

There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swap operations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions aand b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and p_i > p_j.

Input

The first line contains a single integer n (1 ≤ n ≤ 10⁵) — the number of swapoperations applied to the sequence.

Each of the next n lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10⁹, a_i ≠ b_i) — the arguments of the swap operation.

Output

Print a single integer — the number of inversions in the resulting sequence.

Examples

Input

2
4 2
1 4

Output

Input

Output

Note

In the first sample the sequence is being modified as follows: . It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<cmath>

const int maxn=2e5+;

typedef long long ll;

using namespace std;

ll s[maxn],sum[maxn];

int ss[maxn];

int a[maxn],b[maxn],pos[maxn];

int lowbit(int x)

{

    return x&(-x);

}

int n;

void update(int pos,int ad)

{

    while(pos<=maxn)

    {

        s[pos]+=ad;

        pos+=lowbit(pos);

    }

}

ll getnum(int pos)

{

    ll res=;

    while(pos>)

    {

        res+=s[pos];

        pos-=lowbit(pos);

    }

    return res;

}

int main()

{

    int n;

    while (~scanf("%d", &n))

    {

        for (int i = ; i <= n; i++)

        {

            scanf("%d%d", &a[i], &b[i]);

            ss[i] = a[i];

            ss[i + n] = b[i];

            pos[i] = i;

            pos[i + n] = i + n;

        }

        sort(ss + , ss +  * n + );

        ss[] = ;

        int cnt = ;

        for (int i = ; i <=  * n;i++)

        if (i ==  || ss[i] != ss[i - ])

            ss[++cnt] = ss[i];

        sum[] = ;

        for (int i = ; i <= cnt; i++)

            sum[i] = sum[i - ] + ss[i] - ss[i - ] - ;

        for (int i = ; i <= n; i++)

        {

            int aa = lower_bound(ss + , ss + cnt + , a[i]) - ss;

            int bb = lower_bound(ss + ,ss + cnt + , b[i]) - ss;

            swap(pos[aa], pos[bb]);

        }

        memset(s, , sizeof(s));

        ll ans = ;

        for (int i = cnt; i; i--)

        {

            ans += getnum(pos[i]);

            ans += abs(sum[i]-sum[pos[i]]);

            update(pos[i], );

        }

        printf("%lld\n", ans);

    }

   return ;

}

巴特西

Infinite Inversions(树状数组+离散化)

最新文章

热门文章