P4375 [USACO18OPEN]Out of Sorts G 题解

· · 题解

一道珂爱并且喵喵的可爱题。

题目简述

题目分析

我们先说结论，假设 a 已经经历过离散化，那么答案是：

\max_{i=1}^n \{\sum_{j=1}^i [a_j>i]\}

我们证明一下。

这个式子其实就是在 [1,i] 中不属于这个区间的数的个数。

每一次如果 [1,i] 没有排序好，左冒泡走掉的肯定不属于这个区间，并且右冒泡肯定会补回来一个，所以单独对于这个区间来说就需要 \sum_{j=1}^i [a_j>i] 的次数。

那么排序，就是要对任意的 i，下标为 [1,i] 的数当中只有 [1,i] 所以结论得证。

参考代码

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int n;
struct node{
    int val,id;
}a[MAXN];
bool cmp1(node x,node y){return ((x.val!=y.val)?x.val<y.val:x.id<y.id);}
bool cmp2(node x,node y){return x.id<y.id;}
int t[MAXN];
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    while(x<=n){
        t[x]++;
        x+=lowbit(x);
    }
}
int que(int x){
    int res=0;
    while(x>0){
        res+=t[x];
        x-=lowbit(x);
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].val,a[i].id=i;
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++)
        a[i].val=i;
    sort(a+1,a+n+1,cmp2);
    int ans=1;
    for(int i=1;i<=n;i++){
        add(a[i].val);
        ans=max(ans,i-que(i));
    }
    cout<<ans<<endl;
}