[BZOJ 3295] 动态逆序对

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
ll res=0;
struct PrTree{int ls,rs,cnt;}seg[MAXN*60];
int n,m,x,rt[MAXN],dat[MAXN],pre[MAXN],suf[MAXN],pos[MAXN],bit[MAXN],tot;

inline int lowbit(int x){return x&(-x);}
void upd(int x){while(x<=n) bit[x]++,x+=lowbit(x);}
int qry(int x){int ret=0;while(x) ret+=bit[x],x-=lowbit(x);return ret;}

void Update(int &cur,int pos,int val,int l,int r)
{
    if(!cur) cur=++tot;
    seg[cur].cnt+=val;
    if(l==r) return;int mid=(l+r)>>1;
    if(pos<=mid) Update(seg[cur].ls,pos,val,l,mid);
    else Update(seg[cur].rs,pos,val,mid+1,r);
}

int Query(int a,int b,int k,int l,int r)
{
    if(!k) return 0;
    if(a<=l&&r<=b) return seg[k].cnt;
    int ret=0,mid=(l+r)>>1;
    if(a<=mid) ret+=Query(a,b,seg[k].ls,l,mid);
    if(b>mid) ret+=Query(a,b,seg[k].rs,mid+1,r);
    return ret;
}

ll cal(int pl,int pr,int vl,int vr)
{
    if(vl>vr) return 0;ll ret=0;
    for(int i=pl-1;i;i-=lowbit(i))
        res-=Query(vl,vr,rt[i],1,n);
    for(int i=pr;i;i-=lowbit(i))
        res+=Query(vl,vr,rt[i],1,n);
    return ret;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&dat[i]);pos[dat[i]]=i;
        pre[i]=(i-1)-qry(dat[i]);res+=pre[i];upd(dat[i]);
    }
    memset(bit,0,sizeof(bit));
    for(int i=n;i>=1;i--)
        suf[i]=qry(dat[i]),upd(dat[i]);
    
    while(m--)
    {
        printf("%lld\n",res);
        scanf("%d",&x);int p=pos[x];
        res-=pre[p]+suf[p]-cal(1,p-1,x+1,n)-cal(p+1,n,1,x-1);
        
        for(int i=p;i<=n;i+=lowbit(i))
            Update(rt[i],x,1,1,n);
    }
    return 0;
}