首发题解

发现写过文，摘抄下来。
前置芝士：CDQ分治
读题之后容易发现最后一个输入没用
可以发现每次输出的答案后一个都比前一个小
看似是废话，那我们思考一下小了多少呢？
很明显是删除元素对答案的负贡献。每个答案都多计算一个元素的负贡献，可以考虑用类似前缀和的方法。先计算原序列总贡献，再递推每个删除元素的负贡献。
问题转化为：如何寻找每次删除操作的负贡献？
先对代码进行简化，不需要去重，并考虑用sort直接实现。接下来可以将元素被删时间$Time$看作第三维的属性，注意到对于删除操作 $i$,其负贡献的倒数为序列中满足 $Time_i < Time_j,$ $Val_i<Val_j,$ $Pos_i>Pos_j$ 或$Time_i<Time_j,$ $Val_i>Val_j,$ $Pos_i<Pos_j$ 的元素个数。将其转化为三维偏序问题，进行答案运算时不考虑 $Time$,将序列从左到右遍历统计第一种贡献，再倒序处理第二种贡献。删除时像整体二分，用-1抵消插入操作；在计算贡献时乘上自己的 op ，确保插入操作统计正贡献、删除操作统计负贡献。本题有一定思考难度，请自行理解。
注意到求的是逆序对数量的总和，再看看数据量，不开 long long 见祖宗
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int pos,val,op,id;
    bool operator <(const node&xyl)const{return pos<xyl.pos;}
}a[150005];
int n,N,m,ans[50005],tree[100005],idx[100005];
void modify(int x,int d){
    for(int i=x;i<=n;i+=i&(-i))tree[i]+=d;
}
int sum(int x){
    int res=0;
    for(int i=x;i>=1;i-=i&(-i))res+=tree[i];
    return res;
}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq(l,mid),cdq(mid+1,r);
    for(;cnt2<=r;++cnt2){
        while(cnt1<=mid&&a[cnt1].pos<a[cnt2].pos)modify(a[cnt1].val,a[cnt1].op),++cnt1;
        ans[a[cnt2].id]+=a[cnt2].op*(sum(n)-sum(a[cnt2].val));
    }
    for(int i=l;i<cnt1;++i)modify(a[i].val,-a[i].op);
    for(cnt1=mid,cnt2=r;cnt2>=mid+1;--cnt2){
        while(cnt1>=l&&a[cnt1].pos>a[cnt2].pos)modify(a[cnt1].val,a[cnt1].op),--cnt1;
        ans[a[cnt2].id]+=a[cnt2].op*sum(a[cnt2].val-1);
    }
    for(int i=mid;i>cnt1;--i)modify(a[i].val,-a[i].op);
    sort(a+l,a+r+1);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[++N]={i,read(),1,0},idx[a[N].val]=i;
    for(int i=1;i<=m;++i)a[++N].val=read(),a[N].pos=idx[a[N].val],a[N].id=i,a[N].op=-1;
    cdq(1,N);
    for(int i=1;i<m;++i)ans[i]+=ans[i-1];
    for(int i=0;i<m;++i)write(ans[i]),putchar('\n');
    return 0;
}

所有解法：
$CDQ$ 分治 $O(Nlog^2N)$
树状数组套主席树 $O(Nlog^2N)$
分块 $O(N\sqrt N)$
线段树套平衡树 $O(NlogN+Mlog^2N)$（甚至题解还有线段树套朴素BST）
$K-D$ 树 $O(N\sqrt N)$