P4375 [USACO18OPEN] Out of Sorts G——找规律+权值树状数组

· · 个人记录

题意简述

双向冒泡排序，求循环次数

暴力模拟50pts

### 正解 冒泡排序，可以想到逆序对 但是不好确定一次消掉的元素，所以先不考虑 我们可以注意到对于一个区间 $[1,i]$ 来说（**很重要的视角**） 每一个排名大于i的数**最后都会被运走** 每一次如果 $[1,i]$ 没有排序好，左冒泡走掉的肯定不属于这个区间（**而且只有一个**），并且右冒泡肯定会补回来一个 所以只要维护每个区间 $[1,i]$ 中排名大于i的数再取个最大值好了 **离散化后用权值树状数组维护**，时间复杂度 $O(n \log n) 
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+5;

int cnt=0;
int n,a[MAXN];

int b[MAXN];
#define lowbit(x) (x&-x)

int query(int idx){
    int sum=0;
    while(idx){
        sum+=b[idx];
        idx-=lowbit(idx);
    }
    return sum;
}//

void revise(int idx,int k){
    while(idx<=n){
        b[idx]+=k;
        idx+=lowbit(idx);
    }
}//

//树状数组求每一个数后比它小的数量 

int lisan[MAXN];

int erf(int x,int l,int r){
    int mid;
    while(l<r){
        mid=(l+r+1)>>1;
        if(lisan[mid]<=x) l=mid;
        else r=mid-1;
    }
    return l;
}//

void discretize(){
    for(int i=1;i<=n;++i){
        lisan[i]=a[i];
    }
    sort(lisan+1,lisan+1+n);
    for(int i=1;i<=n;++i)
        a[i]=erf(a[i],1,n);
}//

void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);

    discretize();

    int maxn=0;

    for(int i=n;i>=1;--i){
        printf("%d:%d\n",i,query(i));
        maxn=max(maxn,query(i));
        revise(a[i],1);
    }

    printf("%d",max(1,maxn));
}

int main(){
    work();
    return 0;
}
//这篇看过题解