题解：P15810 [JOI 2013 Final] 冒泡排序 / Bubble Sort

· · 题解

题意已经够简洁了不再赘述。

首先我们肯定都知道一个结论：冒泡排序交换次数等于序列逆序对数量。考虑没有相同数字的情况下，我们求出交换两个数最多可以减少多少逆序对就行了。

题目中有相同数字，做法也类似，但是先判断一些特殊情况。如果原序列中没有逆序对，也就是排好了，如果数字各不相同，那么无论初始交换哪两个数，最后都要操作一次；否则可以交换两个相同数字，最后仍然是排好序的。

考虑其他情况下如何求交换两个数最多减少的逆序对数量。交换两个数 a_i 和 a_j，其中 i<j，那么减少的逆序对数量是 \sum\limits_{k=i+1}^{j-1}[a_k<a_i]+\sum\limits_{k=i+1}^{j-1}[a_k>a_j]-\sum\limits_{k=i+1}^{j-1}[a_k>a_i]-\sum\limits_{k=i+1}^{j-1}[a_k<a_j]=\sum\limits_{k=i+1}^{j-1}[a_j<a_k\le a_i] + \sum\limits_{k=i+1}^{j-1}[a_j\le a_k<a_i]。

显然的，选取的 i 和 j 满足 a_i>a_j 答案不劣。若 i_1<i_2 且 a_{i_1}>a_{i_2}，选取 i_1 一定不劣。同理 j_1>j_2 且 a_{j_1}<a_{j_2}，选取 j_1 一定不劣。

因此，我们要选取的 a_i 为前缀最大值，a_j 为后缀最小值。一组一组求不现实，考虑每一个点 k 对哪些前缀最大值和后缀最大值有贡献，找出 i 的范围和 j 的范围，那么对于其中的每一对 (i,j) 答案加一，我们要求出贡献最大的 (i,j)。

我们枚举每一个 k，二分找出 i 和 j 的范围，贡献形如一个矩形，因此可以通过扫描线解决。

代码：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
const int N=1e5+5;
#define ll long long 
#define ri register int
int n,a[N],px[N],plen;
int premax[N],sufmin[N];
int pnum,snum;
vector<pair<int,int> >Add[N],Del[N];
int num[N];
int mx[N<<2],add[N<<2];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int k){
    while(x<=plen)num[x]+=k,x+=lowbit(x);
    return;
}
inline int query(int x){
    int res=0;
    while(x)res+=num[x],x-=lowbit(x);
    return res;
}
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void push_up(int x){
    mx[x]=max(mx[ls(x)],mx[rs(x)]);
    return;
}
inline void push_down_add(int x,int k){
    add[x]+=k;
    mx[x]+=k;
    return;
}
inline void push_down(int x){
    if(!add[x])return;
    push_down_add(ls(x),add[x]);
    push_down_add(rs(x),add[x]);
    add[x]=0;
    return;
}
inline void update(int x,int nowl,int nowr,int l,int r,int k){
    if(l<=nowl&&nowr<=r)return void(push_down_add(x,k));
    push_down(x);
    int mid=nowl+nowr>>1;
    if(l<=mid)update(ls(x),nowl,mid,l,r,k);
    if(mid<r)update(rs(x),mid+1,nowr,l,r,k);
    push_up(x);
    return;
}
inline void solve(){
    cin>>n;
    for(ri i=1;i<=n;++i)cin>>a[i],px[i]=a[i];
    sort(px+1,px+n+1);
    plen=unique(px+1,px+n+1)-px-1;
    for(ri i=1;i<=n;++i)a[i]=lower_bound(px+1,px+plen+1,a[i])-px;
    int maxx=0,minx=plen+1;
    ll tot=0;
    for(ri i=n;i>=1;--i){
        tot+=query(a[i]-1);
        update(a[i],1);
    }
    if(!tot&&plen!=n)return void(cout<<0<<endl);
    if(!tot)return void(cout<<1<<endl);
    for(ri i=1;i<=n;++i)
        if(a[i]>maxx){
            maxx=a[i];
            premax[++pnum]=i;
        }
    for(ri i=n;i>=1;--i)
        if(a[i]<minx){
            minx=a[i];
            sufmin[++snum]=i;
        }
    for(ri i=1;i<=n;++i){
        int l=1,r=pnum+1,mid,La,Ra,Lb,Rb;
        while(l<r){
            mid=l+r>>1;
            premax[mid]<i?l=mid+1:r=mid;
        }
        Ra=l-1;l=1;r=pnum+1;
        while(l<r){
            mid=l+r>>1;
            a[premax[mid]]>a[i]?r=mid:l=mid+1;
        }
        La=r;
        if(La>Ra)continue;
        l=1;r=snum+1;
        while(l<r){
            mid=l+r>>1;
            a[sufmin[mid]]<=a[i]?r=mid:l=mid+1;
        }
        Lb=r;
        l=1;r=snum+1;
        while(l<r){
            mid=l+r>>1;
            sufmin[mid]>i?l=mid+1:r=mid;
        }
        Rb=l-1;
        if(Lb>Rb)continue;
        Add[La].push_back({Lb,Rb});
        Del[Ra+1].push_back({Lb,Rb});
    }
    for(ri i=1;i<=n;++i){
        int l=1,r=pnum+1,mid,La,Ra,Lb,Rb;
        while(l<r){
            mid=l+r>>1;
            premax[mid]<i?l=mid+1:r=mid;
        }
        Ra=l-1;l=1;r=pnum+1;
        while(l<r){
            mid=l+r>>1;
            a[premax[mid]]>=a[i]?r=mid:l=mid+1;
        }
        La=r;
        if(La>Ra)continue;
        l=1;r=snum+1;
        while(l<r){
            mid=l+r>>1;
            a[sufmin[mid]]<a[i]?r=mid:l=mid+1;
        }
        Lb=r;
        l=1;r=snum+1;
        while(l<r){
            mid=l+r>>1;
            sufmin[mid]>i?l=mid+1:r=mid;
        }
        Rb=l-1;
        if(Lb>Rb)continue;
        Add[La].push_back({Lb,Rb});
        Del[Ra+1].push_back({Lb,Rb});
    }
    int res=0;
    for(int i=1;i<=n;++i){
        for(vector<pair<int,int> >::iterator it=Add[i].begin();it!=Add[i].end();++it)
            update(1,1,snum,it->first,it->second,1);
        for(vector<pair<int,int> >::iterator it=Del[i].begin();it!=Del[i].end();++it)
            update(1,1,snum,it->first,it->second,-1);
        res=max(res,mx[1]);
    }
    cout<<tot-res-1<<endl;
    return;
}
int main(){
    IOS;
    int _=1;
    while(_--)solve();
    return 0;
} 
/*
华风夏韵，洛水天依！ 
*/

记录。