luogu

UVA

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2e5 + 5;

int n, m;
struct E { int t, h, v, ans; } x[N];
int c[N], de[N];

bool cmpt(E a, E b) 
{ 
	if(a.t != b.t) 
		return a.t < b.t; 
	return a.v < b.v;
}
bool cmpv(E a, E b) { return a.v < b.v; }

void add(int x)
{
	while(x <= n)
	{
		c[x] ++;
		x += (x & -x); 
	}
}

void pop(int x)
{
	while(x <= n)
	{
		c[x] --;
		x += (x & -x);
	}
}

int query(int x)
{
	int res = 0;
	while(x)
	{
		res += c[x];
		x -= (x & -x);
	}
	return res;
}

void solve(int l, int r)
{
	if(l == r) return;
	int mid = (l + r) >> 1;
	solve(l, mid); solve(mid + 1, r);
	sort(x + l, x + mid + 1, cmpv);
	sort(x + mid + 1, x + r + 1, cmpv);
	int i = l, j = mid + 1;
	while(j <= r)
	{
		while(i <= mid && x[i].v <= x[j].v)
			add(x[i].h), i ++;
		x[j].ans += i - l - query(x[j].h); j ++;
	}
	for(j = l ; j < i ; j ++) pop(x[j].h); 
	i = mid; j = r;
	while(j > mid)
	{
		while(i >= l && x[i].v >= x[j].v)
			add(x[i].h), i --;
		x[j].ans += query(x[j].h); j --;
	}
	for(j = mid ; j > i ; j --) pop(x[j].h);
}

signed main()
{

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	int a;
	for(int i = 1 ; i <= n ; i ++)
	{
		cin >> a;
		x[a].v = a;
		x[a].h = i;
	} 
	for(int i = 1 ; i <= m ; i ++)
	{
		cin >> de[i];
		x[de[i]].t = n - i + 1;
	}
	for(int i = 1 ; i <= n ; i ++)
		if(!x[i].t) x[i].t = 1;
	
	sort(x + 1, x + n + 1, cmpt);
	solve(1, n);
	
	sort(x + 1, x + n + 1, cmpv);
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++) 
		ans += x[i].ans;
	for(int i = 1 ; i < m ; i ++)
	{
		cout << ans << "\n";
		ans -= x[de[i]].ans;
	}
	cout << ans;
	

	return 0;
}