BZOJ3295 动态逆序对（树套树）

code：

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int a[100005],n,m,id[100005],bit[100005],lson[10000005],rson[10000005],tree[10000005],cnt;
long long ans;
int lowbit(int x){
return x&-x;
}
void addy(int &u,int l,int r,int x,int y){
if(!u)
u=++cnt;
if(l==r){
tree[u]+=y;
return;
}
int mid=(l+r)>>1;
if(x<=mid)
else
tree[u]=tree[lson[u]]+tree[rson[u]];
}
while(x<=n){
x+=lowbit(x);
}
}
int queryy(int u,int l,int r,int i,int j){
if(!u)
return 0;
if(l==i&&r==j)
return tree[u];
int mid=(l+r)>>1;
if(j<=mid)
return queryy(lson[u],l,mid,i,j);
else
if(i>mid)
return queryy(rson[u],mid+1,r,i,j);
return queryy(lson[u],l,mid,i,mid)+queryy(rson[u],mid+1,r,mid+1,j);
}
int queryx(int x,int l,int r){
int ans=0;
while(x){
ans+=queryy(x,1,n,l,r);
x-=lowbit(x);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
cnt=n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ans+=(long long)queryx(i-1,a[i]+1,n);
id[a[i]]=i;
}
while(m--){
printf("%lld\n",ans);
int x;
scanf("%d",&x);
ans-=(long long)queryx(id[x]-1,x+1,n);
ans-=(long long)queryx(n,1,x-1);
ans+=(long long)queryx(id[x]-1,1,x-1);