这道题是 CDQ 分治的板子题。那么我们就不用 CDQ 分治。

这里分享一个 KD-Tree 做法。KD-Tree 上每个节点存储每个数的位置和值这两种数据。每次删除前查询有多少个节点满足与被删除节点有逆序对关系。这就是相对于上一次查询减少的逆序对个数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,rt,tot;
int rak[100005];
long long ans[100005];
struct BIT{
	int c[100005];
	void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
	int query(int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
}bit;
struct Point{
	int rk,val;
}a[100005];
struct tree{
	int lv,ls,rs,rk,val,sz,maxk,maxv,mink,minv;
}t[100005];

void pushup(int o){
	int ls=t[o].ls,rs=t[o].rs;
	t[o].sz=t[ls].sz+t[rs].sz+t[o].lv;
	if(ls){
		t[o].maxk=max(t[o].maxk,t[ls].maxk);
		t[o].maxv=max(t[o].maxv,t[ls].maxv);
		t[o].mink=min(t[o].mink,t[ls].mink);
		t[o].minv=min(t[o].minv,t[ls].minv);
	}
	if(rs){
		t[o].maxk=max(t[o].maxk,t[rs].maxk);
		t[o].maxv=max(t[o].maxv,t[rs].maxv);
		t[o].mink=min(t[o].mink,t[rs].mink);
		t[o].minv=min(t[o].minv,t[rs].minv);
	}
}

void up(int o){
	int ls=t[o].ls,rs=t[o].rs;
	t[o].sz=t[ls].sz+t[rs].sz+t[o].lv;
}

void del(int o,int k,int v,int d){
	if(!o||!t[o].sz)return ;
	if(t[o].mink>k||t[o].maxk<k||t[o].minv>v||t[o].maxv<v)return;
	if(t[o].rk==k&&t[o].val==v){t[o].lv--;t[o].sz--;return;}
	if(d){
		if(v<t[o].val)del(t[o].ls,k,v,d^1);
		else del(t[o].rs,k,v,d^1);
	}else{
		if(k<t[o].rk)del(t[o].ls,k,v,d^1);
		else del(t[o].rs,k,v,d^1);
	}
	up(o);
}

//查询位置在被删除节点之前且值比被删除节点大的节点数量
long long query1(int o,int k,int v){
	if(!o||!t[o].sz)return 0;
	if(t[o].mink>=k||t[o].maxv<=v)return 0;
	if(t[o].maxk<k&&t[o].minv>v)return t[o].sz;
	long long res=0;
	if(t[o].rk<k&&t[o].val>v)res+=t[o].lv;
	return res+query1(t[o].ls,k,v)+query1(t[o].rs,k,v);
}


//查询位置在被删除节点之后且值比被删除节点小的节点数量
long long query2(int o,int k,int v){
	if(!o||!t[o].sz)return 0;
	if(k>=t[o].maxk||v<=t[o].minv)return 0;
	if(k<t[o].mink&&v>t[o].maxv)return t[o].sz;
	long long res=0;
	if(k<t[o].rk&&v>t[o].val)res+=t[o].lv;
	return res+query2(t[o].ls,k,v)+query2(t[o].rs,k,v);
}

void build(int &o,int l,int r,bool d){
	o=++tot;int mid=(l+r)>>1;
	nth_element(a+l,a+mid,a+r+1,[=](Point c,Point cc){return d ? c.val < cc.val : c.rk < cc.rk;});
	t[o].rk=t[o].maxk=t[o].mink=a[mid].rk,
	t[o].val=t[o].maxv=t[o].minv=a[mid].val;
	t[o].lv=1;
	if(l<mid)build(t[o].ls,l,mid-1,d^1);
	if(mid<r)build(t[o].rs,mid+1,r,d^1);
	pushup(o);
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i].val=read(),a[i].rk=i,rak[a[i].val]=i;
	for(int i=n;i>=1;i--)ans[0]+=bit.query(a[i].val),bit.add(a[i].val,1);
	build(rt,1,n,0);
	for(int i=1;i<=m;i++){
		int x=read();
		ans[i]=ans[i-1]-query1(rt,rak[x],x)-query2(rt,rak[x],x);
		del(rt,rak[x],x,0);
	}
	for(int i=0;i<m;i++)printf("%lld\n",ans[i]);
	return 0;
}

我的常数太大，kdt 草不过 Hydro-bzoj，所以这里来一个 cdq 分治的做法。

逆序对大家都会求。

可以计算本题每次操作后结果和上次结果的变化量。

因此此题就可以转化为动态的二维平面单点加与区间查询。

即，设当前点为 $(i,A_i)$，你要查询的是在直线 $x=i$ 左侧在直线 $y=A_i$ 上侧的带权和与在直线 $x=i$ 右侧在直线 $y=A_i$ 下侧的带权和，修改即单点 $(i,A_i)$ 加上 $-1$ 的权。

于是借由 cdq 分治，我们只用处理左侧修改对右侧查询的影响，这个只用一或两轮扫描线，树状数组维护；或再次 cdq 即可。

于是这就做完了。

当然还有一种方法，叫做时光倒流。具体策略类似，此处不提。

Code

// 我的 kdt 过不了 Hydro。
// 还是老老实实 cdq 罢。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
uint n;
namespace BIT
{
    uint A[100005];
    voi add(uint p,uint v){p++;while(p<=n)A[p]+=v,p+=lowbit(p);}
    uint find(uint r){
        uint ans=0;while(r)ans+=A[r],r-=lowbit(r);
        return ans;
    }
    uint find(uint l,uint r){return find(r)-find(l);}
}
uint At[100005],A[100005],Ans[100005];
struct Op{uint op,x,y,v;}P[400005];
voi dfs(uint l,uint r)
{
    if(l+1==r)return;
    uint mid=(l+r)>>1;dfs(l,mid),dfs(mid,r);std::vector<Op>V;
    for(uint i=l;i<mid;i++)if(!P[i].op)V.push_back(P[i]);
    for(uint i=mid;i<r;i++)if(P[i].op)V.push_back(P[i]);
    std::sort(V.begin(),V.end(),[](Op a,Op b){return a.x<b.x;});
    for(auto p:V)if(!p.op)BIT::add(p.y,p.v);else Ans[p.v]+=BIT::find(p.y+1,n);
    for(auto p:V)if(!p.op)BIT::add(p.y,-p.v);
    std::reverse(V.begin(),V.end());
    for(auto p:V)if(!p.op)BIT::add(p.y,p.v);else Ans[p.v]+=BIT::find(p.y);
    for(auto p:V)if(!p.op)BIT::add(p.y,-p.v);
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    uint m,tp=0;scanf("%u%u",&n,&m);
    for(uint i=0;i<n;i++)scanf("%u",A+i),At[--A[i]]=i,P[tp++]={0,i,A[i],1};
    for(uint i=0,v;i<m;i++)scanf("%u",&v),v--,P[tp++]={0,At[v],v,-1u},P[tp++]={1,At[v],v,i};
    dfs(0,tp);
    ullt ans=0;
    for(uint i=0;i<n;i++)ans+=BIT::find(A[i],n),BIT::add(A[i],1);
    for(uint i=0;i<m;i++)printf("%llu\n",ans),ans-=Ans[i];
    return 0;
}