动态逆序对（重庆OI）

先写一个CDQ分治的写法吧，主席树。。。希望我以后会补。

题意：先给定一个 1 1 1~ n n n的全排列，然后有 m m m次删除操作，求每次删除操作之前逆序对的个数。

思路：

  1. 题目说求删除操作之前逆序对的个数，反过来不就是每次插入操作之后逆序对的个数吗？然后如果能求出每次插入操作所增加的逆序对个数，再利用前缀和不就可以得到答案了吗？
  2. 对，就是这么简单，把题目反过来，然后CDQ分治，CDQ部分难度比较低。
  3. CDQ部分：第一维按时间维度（反过来的时间），第二维按照插入元素的位置排序（两遍），第三维就是直接把元素的值插入树状数组中，然后统计答案。

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-7;

struct P{
    int v, id;
}p[maxn];

int n, m, q;
int pos[maxn], vis[maxn], del[maxn];
int b[maxn];
ll num[maxn];

bool cmp1(const P &a, const P &b) {
    return pos[a.v]<pos[b.v];
}

bool cmp2(const P &a, const P &b) {
    return pos[a.v]>pos[b.v];
}

inline void update(int x, int d) { while(x<=n) b[x]+=d, x+=x&-x; }
inline int query(int x) { int ans=0; while(x) ans+=b[x], x-=x&-x; return ans; }

void solve(int l, int r) {
    if(l==r) return;
    int m=(l+r)/2;
    solve(l,m), solve(m+1,r);

    sort(p+l,p+m+1,cmp1), sort(p+m+1,p+r+1,cmp1);
    int j=l;
    for(int i=m+1; i<=r; ++i) {
        while(j<=m&&pos[p[j].v]<pos[p[i].v]) update(p[j].v,1), ++j;
        num[p[i].id]+=j-l-query(p[i].v);
    }
    while(--j>=l) update(p[j].v,-1);

    sort(p+l,p+m+1,cmp2), sort(p+m+1,p+r+1,cmp2);
    j=l;
    for(int i=m+1; i<=r; ++i) {
        while(j<=m&&pos[p[j].v]>pos[p[i].v]) update(p[j].v,1), ++j;
        num[p[i].id]+=query(p[i].v);
    }
    while(--j>=l) update(p[j].v,-1);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read();
    for(int i=1; i<=n; ++i) pos[read()]=i;
    for(int i=1; i<=m; ++i) vis[del[i]=read()]=1;
    for(int i=1; i<=n; ++i) if(!vis[i]) p[++q].v=i;
    for(int i=1; i<=m; ++i) p[++q]=(P){del[m+1-i],i};
    solve(1,n);
    for(int i=1; i<=m; ++i) num[i]+=num[i-1];
    for(int i=m; i; --i) printf("%lld\n", num[i]);
}