Description：

$n$ 个人排成一排，每个人有身高，每次将所有身高小于等于 $k$ 的人按顺序排列，询问序列逆序对数。

$1\leqslant n\leqslant300000$

Solution：

先求出 $val[i]$ 表示在身高第 $i$ 的人和小于等于他的数形成了多少逆序对，这个可以把所有人按身高从小到大排序，每次在树状数组中下标位置加一，注意同样的数要按位置从大到小排序，发现每次就是去掉所有 $\leqslant k$ 的之间的逆序对数，保留 $>k$ 的之间的和 $\leqslant k$ 和 $>k$ 的逆序对，于是把 $val[i]$ 做个前缀和 $ans[]$ ，最开始的逆序对就是 $ans[n]$ ，然后对于每次询问，如果有更多的逆序对被去掉了，就不停减 $val[cur]$ 直到 $a[s[cur]]>k$ ，因为 $val[i]$ 的含义是他和比他小的，所以这样做恰好削掉了所有 $\leqslant k$ 的数之间的逆序对。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

int a[MAXN];

int c[MAXN];

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

void add(int p,int x){for(int i = p;i <= n;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];

bool cmp_a(int x,int y){return (a[x] == a[y] ? x > y : a[x] < a[y]);}

int val[MAXN];

long long ans[MAXN];

int main()

{

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

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

	for(int i = 1;i <= n;++i)s[i] = i;

	sort(s + 1,s + 1 + n,cmp_a);

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

	{

		val[i] = query(n) - query(s[i]);

		add(s[i],1);

		ans[i] = ans[i - 1] + val[i];

	}

	int k;

	int cur = 1;

	long long res = ans[n];

	cout << res << endl;

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

	{

		scanf("%d",&k);k = a[k]; 

		while(cur <= n && k >= a[s[cur]])

		{

			res -= val[cur];

			++cur;

		}

		printf("%lld\n",res);

	}

	return 0;

}