题目
对于序列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分治 因为有两种情况，所以要正反统计两次 【#include#include #include #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;}