BZOJ 3295: [Cqoi2011]动态逆序对 [CDQ分治]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2e5+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}
int n,m;
int mp[N];
struct Operation{
    int t,x,y;
    Operation(){}
    Operation(int t,int id,int v):t(t),x(id),y(v){}
    bool operator <(const Operation &r)const{
        return x==r.x ? y<r.y : x<r.x;
    }
}a[N],t[N];
inline bool cmpTime(const Operation &a,const Operation &b){
    return a.t==b.t ? a.x<b.x : a.t<b.t;
}
int c[N];
inline int lowbit(int x){return x&-x;}
inline void add(int p,int v){for(;p<=n;p+=lowbit(p)) c[p]+=v;}
inline int sum(int p){
    int re=0;
    for(;p;p-=lowbit(p)) re+=c[p];
    return re;
}
ll ans[N];
void CDQ(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    int i=l,j=mid+1,p=l;
    while(i<=mid||j<=r){
        if(j>r||(i<=mid&&a[i]<a[j])) add(a[i].y,1),t[p++]=a[i++];
        else ans[a[j].t]+=sum(n)-sum(a[j].y),t[p++]=a[j++];
    }
    for(int i=l;i<=mid;i++) add(a[i].y,-1);
    for(int i=l;i<=r;i++) a[i]=t[i];
    for(int i=r;i>=l;i--){
        if(a[i].t<=mid) add(a[i].y,1);
        else ans[a[i].t]+=sum(a[i].y);
    }
    for(int i=l;i<=r;i++) if(a[i].t<=mid) add(a[i].y,-1);
}
int main(){
    //freopen("inverse.in","r",stdin);
    //freopen("inverse.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=Operation(0,i,read()),mp[a[i].y]=i;
    int Tim=n;
    for(int i=1;i<=m;i++) a[mp[read()]].t=Tim--;
    for(int i=1;i<=n;i++) if(!a[i].t) a[i].t=Tim--;
    sort(a+1,a+1+n,cmpTime);
    //for(int i=1;i<=10;i++) printf("hi %d %d %d\n",i,a[i].t,a[i].y);
    CDQ(1,n);
    //for(int i=1;i<=10;i++) printf("ans %d %d\n",i,ans[i]);
    for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
    for(int i=n;i>=n-m+1;i--) printf("%lld\n",ans[i]);
}