解题报告：luogu P4378

题目链接：P4378 [USACO18OPEN]Out of Sorts S
？？？？神似\(Online\;Judge\)的\(T2\)，如果考之前做了这题多好，然后就果断抄了那个题的代码(你会发现很相似
注意\(ans+1\)，因为最后还要检查一遍，当然有跟简单的做法，但是找逆序对最好了(并不好写)。

\(Code\):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100005;
const ll inf=2147483647;
ll n,ans=0;
inline ll read()
{
    ll x=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') w=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*w;
}
struct node
{
    int id;
    ll val;
}at[MAXN],rt[MAXN],cnt[MAXN];
inline void qsort(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    qsort(l,mid),qsort(mid+1,r);
    int i=l,j=mid+1,c=l-1;
    while(i<=mid&&j<=r)
    {
        if(at[i].val<=at[j].val) rt[++c]=at[i++];
        else rt[++c]=at[j],cnt[at[j++].id].val+=(ll)(mid-i+1);
    }
    while(i<=mid) rt[++c]=at[i++];
    while(j<=r) rt[++c]=at[j++];
    for(register int i=l;i<=r;i++) at[i]=rt[i]; 
}
int main()
{
    scanf("%lld",&n);
    for(register int i=1;i<=n;i++) at[i].val=read(),at[i].id=i;
    qsort(1,n);
    for(int i=1;i<=n;i++) ans=max(ans,cnt[i].val);
    printf("%d\n",ans+1);
    return 0;
} 

解题报告：luogu P4378

原文：https://www.cnblogs.com/tlx-blog/p/12516462.html