P9596 [JOI Open 2018] 冒泡排序 2 题解

_•́へ•́╬_ · 2023-09-04 17:52:48 · 题解

思路

维护每个数之前的比他大的数的个数，全局最大值就是答案。

为啥呢？这些比他大的数都要到他右边去，一趟最多带一个过去，所以个数就是趟数。

考虑如何维护。

朴素维护是树套树。

使用性质：如果一个数，在他的右边有比他小的数，那么这个数之前的比他大的数的个数一定不是最大值。这样的数，我们就不必维护他的真实值，只要实际值比真实值小就行了。

然后大概有好几种做法。我参考了 loj 的最短解，他去掉了“之前”的限制，直接维护比每个数大的数的个数。如何维护呢？他用这个数的下标减去比这个数小的数的个数。

有个要注意的就是数字相同的时候，要认为左边的比右边小，离散化时可以做到。

code

#include<stdio.h>
#include<algorithm>
#define N 500009
#define lc ((i)<<1|1)
#define rc ((i)+1<<1)
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,q,a[N],x[N],v[N],maxn[N<<3],lazy[N<<3];
long long lsh[N<<1],lsz;
inline void upd(int i,int l,int r,int ql,int qr,int x)
{
    if(qr<l||r<ql)return;
    if(ql<=l&&r<=qr){maxn[i]+=x;lazy[i]+=x;return;}
    int mid=l+r>>1;upd(lc,l,mid,ql,qr,x);upd(rc,mid+1,r,ql,qr,x);
    maxn[i]=max(maxn[lc],maxn[rc])+lazy[i];
}
main()
{
    read(n);read(q);
    for(int i=0;i<n;read(a[i]),lsh[lsz++]=a[i]*(long long)(n)+i,++i);
    for(int i=0;i<q;read(x[i]),read(v[i]),
        lsh[lsz++]=v[i]*(long long)(n)+x[i],++i);
    sort(lsh,lsh+lsz);lsz=unique(lsh,lsh+lsz)-lsh;
    for(int i=0;i<n;++i)
        a[i]=lower_bound(lsh,lsh+lsz,a[i]*(long long)(n)+i)-lsh;
    for(int i=0;i<q;++i)
        v[i]=lower_bound(lsh,lsh+lsz,v[i]*(long long)(n)+x[i])-lsh;
    for(int i=0;i<n;++i)
        upd(0,0,lsz-1,a[i],a[i],i),
        upd(0,0,lsz-1,a[i]+1,lsz-1,-1);
    for(int i=0;i<q;++i)
    {
        upd(0,0,lsz-1,a[x[i]],a[x[i]],-x[i]),
        upd(0,0,lsz-1,a[x[i]]+1,lsz-1,1);
        a[x[i]]=v[i];
        upd(0,0,lsz-1,v[i],v[i],x[i]),
        upd(0,0,lsz-1,v[i]+1,lsz-1,-1);
        printf("%d\n",maxn[0]);
    }
}