题目描述

Description

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

Output

输出包含m行，依次为删除每个元素之前，逆序对的个数。

Sample Input

5 4
1
5
3
4
2
5
1
4
2

Sample Output

5
2
2
1

样例解释

(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

HINT

N<=100000 M<=50000

题目分析

考虑什么样的数才能产生逆序对?
死的比它晚 比它小 位置在它后面
死的比它晚 比它大 位置在它前面
那我们把时间顺序也考虑进去 和位置关系 大小关系构成三位偏序 CDQ直接上！
求出每个时刻删除的数能产生的逆序对 对于没有被删除的数 我们将它们的时间附上m+1 并且ans[m+1]要/2
最后求出后缀和即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct your
{
    int x,y,z;
}a[100100*2];
long long ans[100100];
int num[100100],f[100100],f2[100100];
void update1(int x) { for(;x;x-=x&-x) f[x]++; }
void update2(int x) { for(;x<=n;x+=x&-x) f2[x]++; }
int ask1(int x) { int sum=0; for(;x<=n;x+=x&-x) sum+=f[x]; return sum; }
int ask2(int x) { int sum=0; for(;x;x-=x&-x) sum+=f2[x]; return sum; }
void clean1(int x) { for(;x;x-=x&-x) f[x]=0; }
void clean2(int x) { for(;x<=n;x+=x&-x) f2[x]=0; }
bool cmp(your j,your k) { return j.y>k.y;}
void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(a+l,a+mid+1,cmp),sort(a+mid+1,a+r+1,cmp);
    int tmp=l,nmp=mid+1;
    for(;nmp<=r;nmp++)
    {
        while(tmp<=mid&&a[tmp].y>=a[nmp].y)
            update1(a[tmp].z),tmp++;    
        ans[a[nmp].y]=(long long) ans[a[nmp].y]+ask1(a[nmp].z+1);
    }
    tmp=l,nmp=mid+1;
    for(;tmp<=mid;tmp++)
    {
        while(nmp<=r&&a[nmp].y>=a[tmp].y)
            update2(a[nmp].z),nmp++;
        ans[a[tmp].y]=(long long) ans[a[tmp].y]+ask2(a[tmp].z-1);
    }
    for(int i=l;i<=mid;i++) clean1(a[i].z);
    for(int i=mid+1;i<=r;i++) clean2(a[i].z);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].z),a[i].x=i;
    for(int x,i=1;i<=m;i++)
        scanf("%d",&x),num[x]=i;
    for(int i=1;i<=n;i++)
    {
        if(!num[a[i].z]) num[a[i].z]=m+1;
        a[i].y=num[a[i].z]; 
    }
    cdq(1,n);
    ans[m+1]/=2;
    for(int i=m;i>=1;i--) ans[i]+=ans[i+1];
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}