Description：

给你一个数列，有一些数不确定，确定这些数使得整个数列有最小的逆序对数。

$1\leqslant n\leqslant 10000,1\leqslant m\leqslant m$

Solution：

发现填的数一定是递增的，因为如果 $a_i>a_j$ ，那么互换他们，较小的到了前面，较大的到了后面，逆序对数一定变少，也就是说只用考虑填的数和原数列形成的逆序对以及原数列就有的逆序对，那就可以先预处理出在每个位置填某个数与其他位置形成的逆序对，然后设 $f[i][j]$ 表示在 $i$ 位置放 $j$ 的最小逆序对数，有转移 $f[i][j]=\min(f[last][l]+v[i][j])(l\leqslant j)$ ，发现可以前缀和优化一下。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

int a[MAXN];

#define MAXM 110

int f[MAXN][MAXM];

int pre[MAXN][MAXM],suf[MAXN][MAXM];

int lowbit(int x){return x & (-x);}

int c[MAXM];

void add(int p,int x){for(int i = p;i <= m;i += lowbit(i))c[i] += x;return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int s[MAXN][MAXM];

int main()

{

	scanf("%d%d",&n,&m);

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

	int sum = 0;

	for(int i = 1;i <= n;++i)

	{

		if(a[i] != -1)

		{

			add(a[i],1);

			sum += query(m) - query(a[i]);

		}

		else

		{

			for(int j = 1;j <= m;++j)

				pre[i][j] += query(m) - query(j);

		}

	}

	memset(c,0,sizeof(c));

	for(int i = n;i >= 1;--i)

	{

		if(a[i] != -1)

		{

			add(a[i],1);

		}

		else

		{

			for(int j = 1;j <= m;++j)

				suf[i][j] += query(j - 1);

		}

	}

	memset(f,0x3f,sizeof(f));

	f[0][1] = 0;

	memset(s,0x3f,sizeof(s));

	memset(s[0],0,sizeof(s[0]));

	int last = 0;

	for(int i = 1;i <= n;++i)

	{

		if(a[i] != -1)

		{

			add(a[i],1);

		}

		else

		{

			for(int j = 1;j <= m;++j)

			{

				f[i][j] = s[last][j] + pre[i][j] + suf[i][j];

				s[i][j] = min(s[i][j - 1],f[i][j]);

			}

			last = i;

		}

	}

	int ans = 0x3f3f3f3f;

	for(int i = 1;i <= m;++i)

	{

		ans = min(ans,f[last][i]);

	}

	cout << ans + sum << endl;

	return 0;

}