【题解】洛谷P1975排序

分块，注意重复的值之间的处理。跟普通分块的操作一样的啦，具体可以参见‘不勤劳的图书管理员’。

#include <bits/stdc++.h>

using namespace std;

#define maxn 500000

#define lowbit(i) i & (-i)

#define int long long

int n, m, cnt, ans, B, c[][maxn];

struct node

{

    int num, id, rank;

}a[];

int read()

{

    int x = ;

    char c;

    c = getchar();

    while(c < '' || c > '') c = getchar();

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x;

}

int Get_ans(int x, int y)

{

    if(a[x].rank < a[y].rank) return ;

    else if(a[x].rank > a[y].rank) return -;

    return ;

}

bool cmp1(node a, node b)

{

    if(a.num != b.num) return a.num < b.num;

    return a.id < b.id;

}

bool cmp2(node a, node b)

{

    return a.id < b.id;

}

void update(int opt, int x, int sum)

{

    if(!x) return;

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

        c[opt][i] += sum;

}

int query(int opt, int x)

{

    if(x < ) return ;

    int ans = ;

    for(int i = x; i; i -= lowbit(i))

        ans += c[opt][i];

    return ans;

}

signed main()

{

    n = read();

    B = sqrt(n);

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

        a[i].num = read(), a[i].id = i;

    sort(a + , a +  + n, cmp1);

    a[].rank = ;

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

        if(a[i].num == a[i - ].num) a[i].rank = a[i - ].rank;

        else a[i].rank = ++ cnt;

    sort(a + , a +  + n, cmp2);

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

        update(i / B, a[i].rank, );

    for(int i = n; i >= ; i --)

    {

        ans += query(n / B + , a[i].rank - );

        update(n / B + , a[i].rank, );

    }

    m = read();

    cout << ans << endl;

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

    {

        int x = read(), y = read();

        if(x > y) swap(y, x);

        int p = x / B, q = y / B;

        if(a[x].rank < a[y].rank) ans ++;

        else if(a[x].rank > a[y].rank) ans --;

        if(p == q)

        {

            for(int i = x + ; i < y; i ++)

                ans += Get_ans(x, i) + Get_ans(i, y);

            swap(a[x], a[y]);

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

            continue;

        }

        for(int i = x + ; i < (p + ) * B; i ++)

            if(i <= n) ans += Get_ans(x, i) + Get_ans(i, y);

        for(int i = q * B; i < y; i ++)

            ans += Get_ans(i, y) + Get_ans(x, i);

        for(int i = p + ; i < q; i ++)

        {

            ans = (ans - query(i, a[x].rank - ) + query(i, a[y].rank - ));

            ans = (ans - query(i, a[x].rank)  + query(i, a[y].rank));

        }

        update(p, a[x].rank, -), update(q, a[y].rank, -);

        update(q, a[x].rank, ), update(p, a[y].rank, );

        swap(a[x], a[y]);

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

    }

    return ;

}