#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100005
#define maxk 6000005
using namespace std; int n,m,size,num[maxn],pos[maxn],tsum[maxn],t1[maxn],t2[maxn];
typedef long long ll;
ll ans;
int sum[maxk],lc[maxk],rc[maxk],root[maxn]; int lowbit(int x){
return x&(-x);
} void tree_insert(int x){
for (int i=x;i<=n;i+=lowbit(i)) tsum[i]++;
} int tree_sum(int x){
int temp=;
for (int i=x;i>;i-=lowbit(i)) temp+=tsum[i];
return temp;
} int query_sum(int k,int l,int r,int x,int y){
if (!k) return ;
if (l>=x&&r<=y){
return sum[k];
}
int mid=(l+r)/,temp=;
if (x<=mid) temp+=query_sum(lc[k],l,mid,x,y);
if (y>mid) temp+=query_sum(rc[k],mid+,r,x,y);
return temp;
} int query(int lim,int l,int r){
int temp=;
for (int i=lim;i>;i-=lowbit(i)){
temp+=query_sum(root[i],,n,l,r);
}
return temp;
} void update(int &k,int l,int r,int x){
if (!k) k=++size;
sum[k]++;
if (l==r) return;
int mid=(l+r)/;
if (x<=mid) update(lc[k],l,mid,x);
else update(rc[k],mid+,r,x);
} void insert(int lim,int x){
for (int i=lim;i<=n;i+=lowbit(i)){
update(root[i],,n,x);
}
} int main(){
// freopen("dtnxd.in","r",stdin);
// freopen("dtnxd.out","w",stdout);
scanf("%d%d",&n,&m),ans=size=;
memset(sum,,sizeof(sum));
memset(root,,sizeof(root));
memset(tsum,,sizeof(tsum));
for (int i=;i<=n;i++){
scanf("%d",&num[i]),pos[num[i]]=i;
t1[i]=tree_sum(n)-tree_sum(num[i]);
ans+=t1[i];
tree_insert(num[i]);
}
memset(tsum,,sizeof(tsum));
for (int i=n;i>=;i--){
t2[i]=tree_sum(num[i]-);
tree_insert(num[i]);
}
memset(tsum,,sizeof(tsum));
// for (int i=1;i<=n;i++) printf("%d %d\n",t1[i],t2[i]);
int u,v;
for (int i=;i<=m;i++){
scanf("%d",&u),v=pos[u];
printf("%lld\n",ans);
ans-=(t1[v]+t2[v]);
ans+=query(v-,u+,n);
ans+=query(n,,u-);
ans-=query(v,,u-);
insert(v,u);
}
return ;
}
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3295
题目大意：对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
做法：一种暴力写法，就是每次删除前，重新用树状数组维护逆序对，复杂度mnlogn，是接受不了的。我们考虑每次删除一个数后对ans的影响，其影响就是ans-=前面未被删除的数中比它大的个数+后面未被删除的数中比它小的数的个数。这是一个经典的问题：询问一段区间l~r中权值在x~y范围内的个数，支持修改操作，我们能想到的便是树状数组套动态开点的权值线段树（可持久化线段树），但是恶心的是这题卡空间，我们可以这样优化一下：
我们用一维树状数组即可预处理出两个数组，t1[]，t2[]，分别表示初始序列中在i之前的比它大的个数、初始序列中在i之后的比它小的个数，我们就不需要把初始的n个数也加进树套树中了，我们删除一个数，ans-=（t1+t2-在它之前的已被删除的比它大的个数-在它之后已被删除的比它小的个数），我们便只需要将m个数加入到树套树中了，空间复杂度优化了不少，mlogn^2，不会MLE。
还有一种cdq分治的写法，用的归并排序的思想，以后再写吧。
树套树。