BZOJ3295: [Cqoi2011]动态逆序对

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3295

Solution

树状数组套主席树。
预处理出每个数之前/后比他大/小的数的个数，记pr[i],su[i]。
每次删点i时 ans-=pr[i]+su[i]-已删比它大和比它小的数的个数。
统计已删点可以用树状数组套主席树做。
打着打着就抄了黄学长的

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 100005
#define M 5000005
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
long long ans;
ll c[N],pos[N],pr[N],su[N],num[N],root[N];
ll left[M],right[M],sum[M],A[50],B[50];
ll n,m,x,size;
ll get(ll x){ll ans=0;for (;x;x-=x&-x) ans+=c[x]; return ans;}
void add(ll x,ll v){for (;x<=n;x+=x&-x) c[x]+=v;}
void updata(ll l,ll r,ll &p,ll v){
    if (!p) p=++size;
    sum[p]++; if (l==r) return;
    ll mid=l+r>>1;
    if (v<=mid) updata(l,mid,left[p],v);
    else updata(mid+1,r,right[p],v);
}
ll askmore(ll x,ll y,ll num){
    A[0]=B[0]=0; ll tmp=0,l=1,r=n; x--;
    for (ll i=x;i;i-=i&-i) A[++A[0]]=root[i];
    for (ll i=y;i;i-=i&-i) B[++B[0]]=root[i];
    while (l!=r){
        ll mid=l+r>>1;
        if (num<=mid){
            for (ll i=1;i<=A[0];i++) tmp-=sum[right[A[i]]];
            for (ll i=1;i<=B[0];i++) tmp+=sum[right[B[i]]];
            for (ll i=1;i<=A[0];i++) A[i]=left[A[i]];
            for (ll i=1;i<=B[0];i++) B[i]=left[B[i]];
            r=mid;
        }else{
            for (ll i=1;i<=A[0];i++) A[i]=right[A[i]];
            for (ll i=1;i<=B[0];i++) B[i]=right[B[i]];
            l=mid+1;
        }
    }
    return tmp;
}
ll askless(ll x,ll y,ll num){
    A[0]=B[0]=0; ll tmp=0,l=1,r=n; x--;
    for (ll i=x;i;i-=i&-i) A[++A[0]]=root[i];
    for (ll i=y;i;i-=i&-i) B[++B[0]]=root[i];
    while (l!=r){
        ll mid=l+r>>1;
        if (num>mid){
            for (ll i=1;i<=A[0];i++) tmp-=sum[left[A[i]]];
            for (ll i=1;i<=B[0];i++) tmp+=sum[left[B[i]]];
            for (ll i=1;i<=A[0];i++) A[i]=right[A[i]];
            for (ll i=1;i<=B[0];i++) B[i]=right[B[i]];
            l=mid+1;
        }else{
            for (ll i=1;i<=A[0];i++) A[i]=left[A[i]];
            for (ll i=1;i<=B[0];i++) B[i]=left[B[i]];
            r=mid;
        }
    }
    return tmp;
}
int main(){
    n=read(); m=read();
    for (ll i=1;i<=n;i++){
        pos[num[i]=read()]=i;
        ans+=pr[i]=get(n)-get(num[i]);
        add(num[i],1);
    }
    memset(c,0,sizeof c);
    for (ll i=n;i;i--){
        su[i]=get(num[i]-1);
        add(num[i],1);
    }
    while (m--){
        printf("%lld\n",ans);
        x=pos[read()];
        ans-=pr[x]+su[x]-askmore(1,x-1,num[x])-askless(x+1,n,num[x]);
        for (ll j=x;j<=n;j+=j&-j) updata(1,n,root[j],num[x]);
    }
}