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

· · 题解

注意到可以先求出归并排序求出原数组逆序对数量（即只考虑相邻交换的话需要多少次），然后考虑远程交换产生的贡献。这是因为什么时候远程交换都一样。

再注意到如果我们交换第 i 号元素和第 j 号元素，那么他们之间所有值小于 a_i 且 大于 a_j 的元素就能产生 -1 的贡献，显然我们要找到交换哪两个元素产生的贡献最小。

接下来我们注意到如果一个元素前面有一个元素比他大，那么它绝对不可能作为产生贡献最小的区间的左端点。同理如果一个元素后面有一个元素比他小，那么它也绝对不可能作为产生贡献最小的区间的右端点。

那么一个元素前面所有元素都比他小，我们就把他加入到合法左端点集合中。一个元素后面所有元素都比他大，我们就把他加入到合法右端点集合中。用单调队列分别求出合法左端点集合和合法右端点集合。

现在我们的合法右端点集合和合法左端点集合按照元素编号升序排序后，注意到他们的值也是升序的。

排序后我们注意到对于每一个元素，能让它产生贡献的所有左端点都是连续的，能让它产生贡献的所有右端点也都是连续的。如果我们选择的左端点可以让它产生贡献并且我们选择的右端点可以让它产生贡献，这个元素就可以产生 -1 的贡献。

这时我们注意到如果我们以所有合法左端点为 x 轴，以所有合法右端点为 y 轴建立平面直角坐标系，则可以使每一个元素产生 -1 的贡献合法左端点和合法右端点是一个矩形，我们要求的就是选一个点，使它被最多的矩形包含。一共 n 个矩形，直接扫描线即可。

代码（扫描线用线段树实现）：

#include <bits/stdc++.h>
using namespace std;
const long long N=100010;
long long n,a[N],b[N],gui[N],ecnt,mx,mn=1e9,ans,zjh,lpos[N],lval[N],rpos[N],rval[N],lcnt,rcnt;
long long mergesort(long long l,long long r)
{
    if(l>=r)
    {
        return 0;
    }
    long long mid=(l+r)>>1;
    long long anss=mergesort(l,mid)+mergesort(mid+1,r);
    long long i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(b[i]<=b[j])
        {
            gui[k++]=b[i++];
        }
        else
        {
            anss+=(mid-i+1);
            gui[k++]=b[j++];
        }
    }
    while(i<=mid)
    {
        gui[k++]=b[i++];
    }
    while(j<=r)
    {
        gui[k++]=b[j++];
    }
    for(long long t=l;t<=r;t++)
    {
        b[t]=gui[t];
    }
    return anss;
}
//归并排序求逆序对 
struct tree
{
    long long mx,lazy;
}tr[4*N];
void change(long long now,long long l,long long r,long long ql,long long qr,long long z)
{
    if(ql>r||qr<l)
    {
        return ;
    }
    if(ql<=l&&r<=qr)
    {
        tr[now].mx+=z;
        tr[now].lazy+=z;
        return ;
    }
    long long mid=(l+r)>>1;
    change(now*2,l,mid,ql,qr,z);
    change(now*2+1,mid+1,r,ql,qr,z);
    tr[now].mx=max(tr[now*2].mx,tr[now*2+1].mx)+tr[now].lazy;
    return ;
}
//线段树 
struct sao
{
    long long x,y1,y2,z;
}sj[N*8];
bool cmp(sao a1,sao a2)
{
    return a1.x<a2.x;
}
//扫描线事件 
void add(long long l1,long long l2,long long r1,long long r2,long long w)
{
    sj[++ecnt]={l1,r1,r2,w};
    sj[++ecnt]={l2+1,r1,r2,-w};
    return ; 
}
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
        //保留原数组，用新数组算逆序对 
    }
    if(n==1)
    {
        cout<<0;
        return 0;
    }
    zjh=mergesort(1,n);
    if(zjh==0)
    {
        for(int i=2;i<=n;i++)
        {
            if(a[i]==a[i-1])
            {
                cout<<0;
                return 0;
            }
        }
        cout<<1;
        return 0;
    }
    //只考虑相邻交换的话需要多少次
    for(long long i=1;i<=n;i++)
    {
        if(a[i]>mx)
        {
            lpos[++lcnt]=i;
            lval[lcnt]=a[i];
            mx=a[i];
        }
    }
    for(long long i=n;i>=1;i--)
    {
        if(a[i]<mn)
        {
            rpos[++rcnt]=i;
            rval[rcnt]=a[i];
            mn=a[i];
        }
    }
    for(long long i=1;i<=rcnt/2;i++)
    {
        swap(rpos[i],rpos[rcnt-i+1]);
        swap(rval[i],rval[rcnt-i+1]);
    }
    //计算合法左右端点 
    for(long long i=1;i<=n;i++)
    {
        long long v=a[i];
        long long r1=upper_bound(lpos+1,lpos+lcnt+1,i)-lpos-1,l1=upper_bound(lval+1,lval+lcnt+1,v)-lval;
        long long r2=lower_bound(rval+1,rval+rcnt+1,v)-rval-1,l2=lower_bound(rpos+1,rpos+rcnt+1,i+1)-rpos;
        if(l1<=r1&&l2<=r2)
        {
            add(l1,r1,l2,r2,2);
        }
        long long r=lower_bound(rval+1,rval+rcnt+1,v)-rval;
        if(r<=rcnt&&rval[r]==v&&rpos[r]>i&&l1<=r1)
        {
            add(l1,r1,r,r,1);
        }
        long long l=lower_bound(lval+1,lval+lcnt+1,v)-lval;
        if(l<=lcnt&&lval[l]==v&&lpos[l]<i&&l2<=r2)
        {
            add(l,l,l2,r2,1);
        }
    }
    //生成扫描线事件 
    sort(sj+1,sj+ecnt+1,cmp);
    long long i=1;
    for(long long x=1;x<=lcnt;x++)
    {
        while(i<=ecnt&&sj[i].x==x)
        {
            change(1,1,rcnt,sj[i].y1,sj[i].y2,sj[i].z);
            i++;
        }
        ans=max(ans,tr[1].mx);
    }
    //计算贡献 
    cout<<max(0ll,zjh-ans-1);
    return 0;
}