蒟蒻刚开始学分块，刚从分块入门中出来。
听机房一位数据结构大佬说这题用分块可以$n\sqrt{n}$过，于是经历了漫长的（近一天）的思考，用了种神奇的二维树状数组+分块$O(n\sqrt{n})$过了，好像题解里没有我这种写法来水一发
不扯了讲正题。
支持删除的逆序对，一个基本思路是先求出来一开始逆序对个数，每次删除将这个数的贡献从答案中减去。
怎么求一个数的贡献？
一个数的贡献分两部分：前面比它大的数的个数，后面比它小的数的个数，这些都能组成逆序对。
如何维护这个贡献？
暴力$O(n)$扫描
我们可以数列分块，每个块开一个n大小的数组$f[n]$，$f[i]$表示在这个块中小于等于i的数有几个，计算贡献时（假设这个数为i，在块p中，共有len个块)可以用类似于前缀和统计块 1~p-1的$f[n]-f[i]$（i+1~n的数的数量），再统计块p+1~len的$f[i-1]$（1~i-1的数的数量），最后对块p内的暴力统计，三部分加起来就是这个数的贡献，单次操作时间为$O(\sqrt{n})$,空间为$O(n\sqrt{n})$。
但是问题来了，如何修改？
我们可以注意到，由于每删除一个数就会对这个f数组产生影响，所以必须考虑修改。
这个f数组与前缀和类似，那么前缀和支持修改？
树状数组啊！
把f数组改为树状数组，统计时用树状数组询问，顺带把每一个块执行add(i,-1)（相当于去掉这个数）
然后问题又双来了，这样做单次时间复杂度为$O(n\sqrt{n} logn)$，计算器一算达到了1e8，有点悬啊。试一下果然T了。
还是放弃吧继续优化。
观察一下查询贡献的过程：统计块 1~p-1的$f[n]-f[i]$（i+1~n的数的数量），再统计块p+1~len的$f[i-1]$（1~i-1的数的数量），最后对块p内的暴力统计。
对块p暴力统计肯定没法优化了（即使优化了效果也微乎其微），重点是粗体标出的部分。
两段连续的区间？
前缀和？
那么再加工一下 f 数组：用f[i][j]表示前 i 个块内小于等于 j 的数的数量
这样$O(\sqrt{n}logn)$的暴力统计被优化到了$O(logn)$。
然而问题又双叒来了咋这么多问题
还是老问题，删除数伴随着 f 数组的变化， f 数组不仅第二维要支持修改，第一维也需要修改。
又是支持修改的前缀和？
还是树状数组啊！
于是思路来了：
开二维树状数组，第一维维护块的前缀和，第二位维护数的前缀和
块外的整块用二维树状数组$O(log(\sqrt{n}) log n)≈O(log^2 n)$查询，块内暴力$O(\sqrt{n})$扫描
再用树状数组改一下
时间复杂度：$O(n (\sqrt{n} + log^2n)) ≈ O(n \sqrt{n})$
空间复杂度：$O(n\sqrt{n})$
除了空间压着线（125MB）效率还是不错的：不开O2 1400ms，开O2 900ms
代码：
#define mian main
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 100005
//下面是瞎define的
#define pn putchar('\n')
#define ps putchar(' ')
#define px(x) putchar('x')
#define pX(x) putchar(x)
using namespace std;
inline int read(){
int x=0,y=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return y?-x:x;
}//快读
#define lowb(x) x&-x
int n,len;
int a[maxn],be[maxn],pos[maxn];
bool dis[maxn];
//解释一下毒瘤的变量名
//a : 原数列
//be : belong , 记录每个位置属于哪个块
//pos : position , 记录每个数的位置
//dis : disappear,记录这个位置是否被删除了,用于块内的暴力统计
struct Tree_Array{
//标准的翻译:tree树,array数组,合起来tree_array树状数组(大雾
//结构体内的就是第二维的树状数组,因为二维数组难看所以开进结构体里了
int tree[maxn];
inline void add(int x,int d){
while(x<=n)tree[x]+=d,x+=lowb(x);
}
inline int ask(int x){
int ans=0;
while(x)ans+=tree[x],x-=lowb(x);
return ans;
}
}ta[320],init;
//ta:Tree_Array的缩写,就是那个二维的树状数组
//init:initialization,用于统计初始逆序对数量
//为什么我要用树状数组统计?正好写了个树状数组结构体那就用上呗(才不是我归并排序都打错了)
inline void ADD(int x,int y,int d){
//x为第一维,y为第二维,d为加的数值
while(x<=len)ta[x].add(y,d),x+=lowb(x);
}//整个二维树状数组加
inline int ASK(int x,int y){
//同上的查询
int ans=0;
while(x)ans+=ta[x].ask(y),x-=lowb(x);
return ans;
}
int mian(){
n=read();
int m=read(),sq=sqrt(n);
long long ans=0;//一定要开long long
len=n/sq+(bool)(n%sq);//诡异的块的个数,好像就我这么毒瘤的写分块吧...
for(register int i=1;i<=n;++i)
a[i]=read(),pos[a[i]]=i;
for(register int i=1;i<=len;++i){
int l=sq*(i-1)+1,r=min(l+sq-1,n);
for(register int j=l;j<=r;++j){
ans+=init.ask(n)-init.ask(a[j]);
init.add(a[j],1);//前两个是统计初始逆序对的
ADD(i,a[j],1);//将前i个块的前a[j]的值+1,初始化二维树状数组
be[j]=i;//记录be数组
}
}
while(m--){
int k=read();
printf("%lld\n",ans);
if(be[pos[k]]>1)
ans-=ASK(be[pos[k]]-1,n)-ASK(be[pos[k]]-1,k);
//前一部分的统计,翻译过来:块1~be[pos[k]]的小于等于n的数的个数-块1~be[pos[k]]的小于等于k的个数,即为块1~be[pos[k]]的大于k的个数
if(be[pos[k]]<len)
ans-=ASK(len,k-1)-ASK(be[pos[k]],k-1);
//同上,块be[pos[k]]+1~len的小于k的数的个数
int r=min(be[pos[k]]*sq,n);
for(register int i=sq*(be[pos[k]]-1)+1;i<pos[k];++i)
if(!dis[i]&&a[i]>k)--ans;
for(register int i=pos[k]+1;i<=r;++i)
if(!dis[i]&&a[i]<k)--ans;
//上面为块内暴力统计
ADD(be[pos[k]],k,-1);
//去掉这个数在二维树状数组中的值
dis[pos[k]]=1;
}
}
