题解 P4280 【[AHOI2008]逆序对】

· · 题解

这题我们维护一个大于等于某值的前缀和和一个小于等于某值的后缀和

从左往右扫，对每个位置保证最少贡献的情况下取最小的那个

时间复杂度\Theta(NK)

说实话这题紫题难度有点偏高，差不多是提高组级别难度

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1e5+5;
const int MAXM=105;

int n,m;
int a[MAXN];
int lis[2][MAXM];
long long ans;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){scanf("%d",&a[i]);if(a[i]!=-1) ++lis[1][a[i]];}
    for(int i=1;i<=m;++i) lis[1][i]+=lis[1][i-1];
    for(int i=1;i<=n;++i){
        if(a[i]==-1){
            int c=0,d=0,ct=0,mx=0x7fffffff;
            for(int j=1;j<=m;++j){
                if(lis[0][j+1]+lis[1][j-1]<mx) mx=lis[0][j+1]+lis[1][j-1],ct=j;
            }a[i]=ct;
        }else for(int j=a[i];j<=m;++j) --lis[1][j];
        ans+=lis[0][a[i]+1];
        for(int j=1;j<=a[i];++j) ++lis[0][j];
    }printf("%lld\n",ans);
    return 0;
}