题解：CF1830E Bully Sort

· · 题解

题解：CF1830E Bully Sort

思路

很明显可以把数组有序刻画为逆序对个数为 0。

很明显“bully swap”操作可以看作分段的，每一段会让最大的 p_i \ne p “bully swap”到 p_i 那里。

我们考察一次对于 p 的“bully swap”对逆序对的影响。

设这次“bully swap”跨过了 l 个数，交换了 p,x。显然这 l 个数都小于 p 并且大于 x。那么逆序对的数量就会减去 2l+1，加 1 是因为数对 (p,x) 也变成正序对了。我们把这个 1 摊到 x 上面去。

然后 p 会这样一直交换到位置 p。记轮到 p 开始“bully swap”时，p 初始在 pos_p。

那么我们其实可以刻画出总的逆序对个数了。

sum = \sum_i2(i-pos_i)+w_i

其中 w_i 表示 i 操作了几次才到位置 i。

我们交换顺序可得：

\sum_i w_i = sum - \sum_i2(i-pos_i)

动态逆序对的好维护的，树套树可以做到双 \log。

考虑怎么求 pos_i。

假如在初始排列中 i 在 rnk_i，那么 pos_i = \min(i,rnk_i)。

证明是简单的，很明显不会出现 rnk_i \le pos_i，因为还没轮到你的时候你不会往右边交换，而 rnk_i > i 则必定会交换到 i，考虑在你右边的比你小的一定都会被交换到你前面去，因为在你左边的比你大的的数量多与在你右边的比你小的的数量，而比你小的都在左边，那么你一定不会被交换到小于 i 的位置，而你最后又一定小于等于 i，于是你只能是 i。

然后这个就可以快速维护了。

于是做完了，时间复杂度 \mathcal{O}(n \log^2 n)。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,q,p[500005],ls[80000005],rs[80000005],tree[80000005],rt[500005],tot;
long long ans;
void push_up(int p)
{
    tree[p] = tree[ls[p]] + tree[rs[p]];
}
void update_in(int x,int pl,int pr,int &p,int d)
{
    if(!p) p = ++tot;
    if(pl == pr)
    {
        tree[p] += d;
        return;
    }
    int mid = (pl+pr)/2;
    if(x <= mid) update_in(x,pl,mid,ls[p],d);
    else update_in(x,mid+1,pr,rs[p],d);
    push_up(p);
}
int query_in(int l,int r,int pl,int pr,int p)
{
    if(!p) return 0;
    if(l <= pl && pr <= r)
    {
        return tree[p];
    }
    int mid = (pl+pr)/2,sum = 0;
    if(l <= mid) sum += query_in(l,r,pl,mid,ls[p]);
    if(mid+1 <= r) sum += query_in(l,r,mid+1,pr,rs[p]);
    return sum;
}
int lowbit(int x)
{
    return x & -x;
}
void update_out(int x,int y,int d)
{
    while(x <= n)
    {
        update_in(y,1,n,rt[x],d);
        x += lowbit(x);
    }
}
int query_out(int x,int l,int r)
{
    int sum = 0;
    while(x)
    {
        sum += query_in(l,r,1,n,rt[x]);
        x -= lowbit(x);
    }
    return sum;
}
void print()
{
    cout << "matrix:\n";
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cout << query_out(i,j,j)-query_out(i-1,j,j) << " ";
        }
        cout << endl;
    }
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
        update_out(i,p[i],1);
        ans -= (i-1) - query_out(i-1,1,p[i]-1);
        // cout << (i-1) - query_out(i-1,1,p[i]-1) << " ";
        ans += 2*(p[i]-min(i,p[i]));
        // cout << 2*(p[i]-min(i,p[i])) << endl;
    }
    // cout << ans << endl;
    while(q--)
    {
        int x,y;
        cin >> x >> y;
        ans -= 2*(p[x]-min(x,p[x]));
        // cout << ans << endl;
        ans -= 2*(p[y]-min(y,p[y]));
        // cout << ans << endl;
        update_out(x,p[x],-1);
        update_out(y,p[y],-1);
        // cout << ans << endl;
        if(p[x] < p[y])
        {
            if(x < y) ans -= 2*(query_out(y-1,p[x]+1,p[y]-1)-query_out(x,p[x]+1,p[y]-1))+1;
            // cout << "delta = -" << 2*(query_out(y-1,p[x]+1,p[y]-1)-query_out(x,p[x]+1,p[y]-1))+1 << endl;
        }
        else
        {
            if(x < y) ans += 2*(query_out(y-1,p[y]+1,p[x]-1)-query_out(x,p[y]+1,p[x]-1))+1;
            // cout << "delta = " << 2*(query_out(y-1,p[y]+1,p[x]-1)-query_out(x,p[y]+1,p[x]-1))+1 << endl;
        }
        // cout << ans << endl;
        swap(p[x],p[y]);
        ans += 2*(p[x]-min(x,p[x]));
        // cout << ans << endl;
        ans += 2*(p[y]-min(y,p[y]));
        // cout << ans << endl;
        update_out(x,p[x],1);
        update_out(y,p[y],1);
        cout << ans << '\n';
        // print();
    }
    return 0;
}