[文章目录]
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。N<=100000 M<=50000
如果不往CDQ上想估计得想一天。。。
将询问分治。先统计每个数字所在的逆序对的数量，那么如果不考虑其他元素的去除的话，数量即为去掉其的逆序对数减少量。
将询问分治，如果一个节点删除，对之后删除的节点删除时逆序对数减少的个数有影响。
如果当前数字在序列中位于后面数字的前面，那么如果改数字大于后面数字，后面数字删除时减少的数量-1。
如果在后面，同理，仅当小于后面数字的时候后面数字影响-1。
加上时间一维，还是三维偏序统计个数问题。
由于上次写CDQ的时候发现归并快很多，所以，我。。。又写了两个版本的代码。。。
当然还是归并快了。
归并：960ms 无脑sort：1740ms
以下为归并的代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll sum;
int n,m,pos[101000],atp[101000],atq[101000];
int ans[101000],ques[101000],b[101000],f[101000];
int query(int x){int re=0; while(x>0) re+=f[x],x-=-x&x; return re;}
void fix(int x,int y){while(x<=n) f[x]+=y,x+=-x&x;}
int query_da(int x){int re=0; while(x<=n) re+=f[x],x+=-x&x; return re;}
void fix_da(int x,int y){while(x>0) f[x]+=y,x-=-x&x;}
bool cmp(int x,int y){return atq[x]<atq[y];}
void solve(int l,int r)
{
if(l==r) return ;
int mid=l+r>>1,h1=l,h2=mid+1;
solve(l,mid); solve(mid+1,r);
for(int i=l;i<=r;++i)
{
if(h2>r||(h1<=mid&&atp[ques[h1]]<atp[ques[h2]])) fix_da(ques[h1],1),b[i]=ques[h1++];
else ans[ques[h2]]-=query_da(ques[h2]),b[i]=ques[h2++];
}
for(int i=l;i<=mid;++i) fix_da(ques[i],-1);
h1=mid,h2=r;
for(int i=l;i<=r;++i)
{
if(h2<=mid||(h1>=l&&atp[ques[h1]]>atp[ques[h2]])) fix(ques[h1],1),h1--;
else ans[ques[h2]]-=query(ques[h2]),h2--;
}
for(int i=l;i<=mid;++i) fix(ques[i],-1);
for(int i=l;i<=r;++i) ques[i]=b[i];
}
int main()
{
scanf("%d%d",&n,&m);int i;
for(i=1;i<=n;++i)
scanf("%d",pos+i),atp[pos[i]]=i;
for(i=1;i<=m;++i)
scanf("%d",ques+i),atq[ques[i]]=i;
for(i=1;i<=n;++i)
{
ans[pos[i]]=query_da(pos[i]);
sum+=ans[pos[i]];
fix_da(pos[i],1);
}
memset(f,0,sizeof f);
for(i=n;i;--i)
{
ans[pos[i]]+=query(pos[i]);
fix(pos[i],1);
}
memset(f,0,sizeof f);
solve(1,m); sort(ques+1,ques+m+1,cmp);
for(i=1;i<=m;++i)
{
printf("%lld\n",sum);
sum-=ans[ques[i]];
}
return 0;
}