P3157 动态逆序对（归并排序+树状数组套主席树）
hhz6830975
2017-12-26 12:59:07
先归并排序处理出初始逆序对数
然后树状数组套主席树进行修改和查询
删除数x时（设x位置为pos[x]），从原逆序对数中减去与该数有关的逆序对数，即（[1,pos[x]-1]中大于x的数的个数）+（[pos[x]+1,n]中小于x的数的个数），并从树状数组中将x删除
**另外注意存答案要用long long，否则会爆**
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100010;
typedef long long LL;
int n,m,a[maxn],pos[maxn];
LL ans;
inline int read(){
int ret=0,sign=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') sign=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
return ret*sign;
}
struct node{
int sum,son[2];
}T[maxn*300];
int root[maxn],cnt;
int tmp1[maxn],tmp2[maxn];
LL merge(int l,int r){
if(l==r) return 0;
int mid=(l+r)>>1;
LL ret=merge(l,mid)+merge(mid+1,r);
int i=l,j=mid+1,k=l;
for(;j<=r;j++){
while(i<=mid&&tmp1[i]<=tmp1[j]) tmp2[k++]=tmp1[i++];
ret+=mid-i+1,tmp2[k++]=tmp1[j];
}
for(;i<=mid;i++)
tmp2[k++]=tmp1[i];
for(int p=l;p<=r;p++)
tmp1[p]=tmp2[p];
return ret;
}
void ins(int &u,int l,int r,int x,int op){
if(!u) u=++cnt;
T[u].sum+=op;
int mid=(l+r)>>1;
if(l==r) return;
if(x<=mid) ins(T[u].son[0],l,mid,x,op);
else ins(T[u].son[1],mid+1,r,x,op);
}
inline int lbt(int x){return x&(-x);}
inline void add(int u,int op){for(int i=u;i<=n;i+=lbt(i)) ins(root[i],1,n,a[u],op);}
int tmpU[2][20],tmpN[2];
LL query(int l,int r,int x,int op){
if(l>r) return 0;
tmpN[0]=tmpN[1]=0;
for(int i=l-1;i;i-=lbt(i)) tmpU[0][++tmpN[0]]=root[i];
for(int i=r;i;i-=lbt(i)) tmpU[1][++tmpN[1]]=root[i];
int vl=1,vr=n;
LL ret=0;
if(op==1) while(1){
if(vr==x) break;
int mid=(vl+vr)>>1,rsum=0;
for(int i=1;i<=tmpN[0];i++) rsum-=T[T[tmpU[0][i]].son[1]].sum;
for(int i=1;i<=tmpN[1];i++) rsum+=T[T[tmpU[1][i]].son[1]].sum;
int rela=x>mid;
if(!rela) ret+=rsum,vr=mid;
else vl=mid+1;
for(int i=1;i<=tmpN[0];i++) tmpU[0][i]=T[tmpU[0][i]].son[rela];
for(int i=1;i<=tmpN[1];i++) tmpU[1][i]=T[tmpU[1][i]].son[rela];
}
else while(1){
if(vl==x) break;
int mid=(vl+vr)>>1,lsum=0;
for(int i=1;i<=tmpN[0];i++) lsum-=T[T[tmpU[0][i]].son[0]].sum;
for(int i=1;i<=tmpN[1];i++) lsum+=T[T[tmpU[1][i]].son[0]].sum;
int rela=x>mid;
if(rela) ret+=lsum,vl=mid+1;
else vr=mid;
for(int i=1;i<=tmpN[0];i++) tmpU[0][i]=T[tmpU[0][i]].son[rela];
for(int i=1;i<=tmpN[1];i++) tmpU[1][i]=T[tmpU[1][i]].son[rela];
}
return ret;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
tmp1[i]=a[i]=read(),pos[a[i]]=i;
ans=merge(1,n);
for(int i=1;i<=n;i++)
add(i,1);
for(int i=1;i<=m;i++){
int x=read();
printf("%lld\n",ans);
ans-=query(1,pos[x]-1,x,1)+query(pos[x]+1,n,x,-1);
add(pos[x],-1);
}
return 0;
}
```