题目

对于序列A，它的逆序对数定义为满足i

输入格式

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

输出格式

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

输入样例

5 4

1

5

3

4

2

5

1

4

2

输出样例

5

2

2

1

样例解释

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

提示

N<=100000 M<=50000

题解

反过来插入元素

对于每个元素，对应一个三元组(t,x,y)，表示t时刻插入，位置x，权值y

每个元素插入时产生的逆序对数量为所有的满足如下条件的(t’,x’,y’)

t’ < t 且 x’ > x 且 y’ <ｙ

或者　t’ < t 且 x’ < x 且 y’ > y

这就是三维偏序，可以用CDQ分治

因为有两种情况，所以要正反统计两次

【压行代码50行不到，CDQ很感人】

#include<iostream>

#include<cstdio>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define lbt(x) (x & -x)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

inline int read(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}

    return out * flag;

}

struct Que{int t,x,y;}Q[maxn],T[maxn];

inline bool operator <(const Que& a,const Que& b){return a.x > b.x;}

int N,M,A[maxn],B[maxn],C[maxn],cnt,Qi,s[maxn];

LL ans[maxn];

void add(int u,int v){while (u <= N) s[u] += v,u += lbt(u);}

int query(int u){int Ans = 0; while (u) Ans += s[u],u -= lbt(u); return Ans;}

void cdq(int l,int r){

    if (l == r) return;

    int mid = l + r >> 1,l1 = l,l2 = mid + 1;

    for (int i = l; i <= r; i++)

        if (Q[i].t <= mid) add(Q[i].y,1);

        else ans[Q[i].t] += query(Q[i].y);

    for (int i = l; i <= r; i++)

        if (Q[i].t <= mid) add(Q[i].y,-1);

    for (int i = r; i >= l; i--)

        if (Q[i].t <= mid) add(N - Q[i].y + 1,1);

        else ans[Q[i].t] += query(N - Q[i].y + 1);

    for (int i = l; i <= r; i++)

        if (Q[i].t <= mid) T[l1++] = Q[i],add(N - Q[i].y + 1,-1);

        else T[l2++] = Q[i];

    for (int i = l; i <= r; i++) Q[i] = T[i];

    cdq(l,mid); cdq(mid + 1,r);

}

int main(){

    cnt = N = read(); M = read();

    REP(i,N) B[A[i] = read()] = i;

    REP(i,M){C[Q[i].x = B[Q[i].y = read()]] = true; Q[i].t = cnt--; ++Qi;}

    REP(i,N) if (!C[i]) Q[++Qi] = (Que){cnt--,i,A[i]};

    sort(Q + 1,Q + 1 + N);

    cdq(1,N);

    REP(i,N) ans[i] += ans[i - 1];

    for (int i = 0; i < M; i++) printf("%lld\n",ans[N - i]);

    return 0;

}