Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
2
2
1
各种方法都可做
树套树（5.9s）
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std; int n,m,l,r,o,p,num=;
long long ans=;
inline int read(){
p=;o=getchar();
while(o<''||o>'') o=getchar();
while(o>=''&&o<='') p=p*+o-,o=getchar();
return p;
}
int root[],a[],tt[];
struct tree{
int l,r,k;
tree(){
k=;
}
};
tree t[];
inline void insert(int &p,int l,int r,int k){
if (p==) p=++num;
t[p].k++;
if (l==r) return;
int mid=l+r>>;
if (k<=mid) insert(t[p].l,l,mid,k);else insert(t[p].r,mid+,r,k);
}
inline void del(int p,int l,int r,int k){
t[p].k--;
if (l==r) return;
int mid=l+r>>;
if (k<=mid) del(t[p].l,l,mid,k);else del(t[p].r,mid+,r,k);
}
inline int qui(int p,int l,int r,int k){
if (p==) return ;
if (r==k) return t[p].k;
int mid=l+r>>;
if (k<=mid) return qui(t[p].l,l,mid,k);else return qui(t[p].r,mid+,r,k)+(t[p].l==?:t[t[p].l].k);
}
inline int qua(int p,int l,int r,int k){
if (p==) return ;
if (l==k) return t[p].k;
int mid=l+r>>;
if (k<=mid) return qua(t[p].l,l,mid,k)+(t[p].r==?:t[t[p].r].k);else return qua(t[p].r,mid+,r,k);
}
inline int lo(int x){return x&(-x);}
inline void in(int i,int k){
while(i<=n){
insert(root[i],,n,k);
i+=lo(i);
}
}
inline void de(int i,int k){
while(i<=n){
del(root[i],,n,k);
i+=lo(i);
}
}
inline long long ask(int x,int k){
long long s=;
k++;
while(x>){
if (k<=n) s+=qua(root[x],,n,k);
x-=lo(x);
}
return s;
}
inline long long aski(int x,int k){
long long s=;
k--;
while(x>){
if (k>=) s+=qui(root[x],,n,k);
x-=lo(x);
}
return s;
}
int main(){
register int i,j;
n=read();
m=read();
for (i=;i<=n;i++) in(i,a[i]=read()),tt[a[i]]=i;
for (i=;i<=n;i++) ans+=ask(i,a[i]);
while(m--){
printf("%lld\n",ans);
l=read();r=tt[l];
if (a[r]==) continue;a[r]=;
ans-=ask(r,l)+aski(n,l)-aski(r,l);
de(r,l);
}
}
CDQ分治
#include<cstdio>
#include<algorithm>
using namespace std;
int read_p,read_ca,pr_num,pr_ch[];
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
inline void pr(long long k){
pr_num=;
while(k>) pr_ch[++pr_num]=k%,k/=;
while(pr_num)
putchar(pr_ch[pr_num--]+);
putchar('\n');
}
struct na{
int x,y,t;
}b[],o[],y[];
int n,m,u[],ti[],s[];
long long ans[][];
inline int low(int x){return x&(-x);} inline void add(int x){
while (x<=n){
s[x]++;
x+=low(x);
}
}
inline void del(int x){
while (x<=n){
s[x]--;
x+=low(x);
}
}
inline int ask(int x){
int ans=;
while (x>){
ans+=s[x];
x-=low(x);
}
return ans;
}
inline bool cmp(na a,na b){
if ((a.x==b.x)&&(a.y==b.y)) return a.t<b.t;
if (a.x==b.x) return a.y>b.y;
return a.x<b.x;
}
inline bool tmp(na a,na b){
if ((a.x==b.x)&&(a.y==b.y)) return a.t<b.t;
if (a.x==b.x) return a.y<b.y;
return a.x>b.x;
}
inline void work0(int l,int r){
if (l==r) return;
int mid=l+r>>,ll=l-,rr=mid;
for (register int i=l;i<=r;i++){
if (b[i].t<=mid) add(n-b[i].y+);
if (b[i].t>mid) ans[b[i].t][]+=ask(n-b[i].y+);
}
for (register int i=l;i<=r;i++)
if (b[i].t<=mid) o[++ll]=b[i];else o[++rr]=b[i];
for (register int i=l;i<=r;i++) b[i]=o[i];
for (register int i=l;i<=r;i++) if (b[i].t<=mid) del(n-b[i].y+);
work0(l,mid);work0(mid+,r);
}
inline void work1(int l,int r){
if (l==r) return;
int mid=l+r>>,ll=l-,rr=mid;
for (register int i=l;i<=r;i++){
if (y[i].t<=mid) add(y[i].y);
if (y[i].t>mid) ans[y[i].t][]+=ask(y[i].y);
}
for (register int i=l;i<=r;i++) if (y[i].t<=mid) del(y[i].y);
for (register int i=l;i<=r;i++)
if (y[i].t<=mid) o[++ll]=y[i];else o[++rr]=y[i];
for (register int i=l;i<=r;i++) y[i]=o[i];
work1(l,mid);work1(mid+,r);
}
int main(){
register int i,j=;
n=read();m=read();
for (i=;i<=n;i++) u[read()]=i;
for (i=;i<m;i++) ti[read()]=m-i;
for (i=;i<=n;i++){
if (ti[i]==) b[i].t=++j;else b[i].t=n-m+ti[i];
b[i].x=u[i];b[i].y=i;
y[i]=b[i];
}
sort(b+,b+n+,cmp);
sort(y+,y+n+,tmp);
work0(,n);work1(,n);
for (int i=;i<=n;i++) ans[i][]+=ans[i-][],ans[i][]+=ans[i-][];
for (int i=n;i>j;i--) pr(ans[i][]+ans[i][]);
}