P3157 [CQOI2011] 动态逆序对
题目描述
对于序列 \(a\)，它的逆序对数定义为集合
中的元素个数。
现在给出 \(1\sim n\) 的一个排列，按照某种顺序依次删除 \(m\) 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
输入格式
第一行包含两个整数 \(n\) 和 \(m\)，即初始元素的个数和删除的元素个数。
以下 \(n\) 行，每行包含一个 \(1 \sim n\) 之间的正整数，即初始排列。
接下来 \(m\) 行，每行一个正整数，依次为每次删除的元素。
输出格式
输出包含 \(m\) 行，依次为删除每个元素之前，逆序对的个数。
输入输出样例 #1
输入 #1
5 4
1
5
3
4
2
5
1
4
2
输出 #1
5
2
2
1
说明/提示
【数据范围】
对于 \(100\%\) 的数据，\(1\le n \le 10^5\)，\(1\le m \le 50000\)。
【样例解释】
删除每个元素之前的序列依次为：
解题报告
这题很适合用来训练 CDQ 分治和树套树。
树套树的没什么好讲的，树状数组维护主席树，训练代码能力来的。主要讲 CDQ 分治。
首先把删除的操作转为倒着插入的操作，这样每个数就有一个出现时间。
要写 CDQ 分治，要先明确偏序情况，很显然，这题是个三维偏序：出现时间、在数组中的位置、数值大小。对于数组中的每一个数，我们建立结构体 \(node(t,p,x)\)，并将原数组的信息转存到 \(node\) 数组 \(Q\) 中。那么，如果 \(Q_i\) 可以对 \(Q_j\) 的产生价值，当且仅当同时满足以下条件：
这样就完成了题意的转化。
然后就是 CDQ 分治的标准操作：先对第一维排序，用归并的方法维护第二维，用树状数组维护第三维。
这里用两点需要注意：
\(1\).对每个计算 \(Q_i\) 价值时，既要统计第二维 \(p\) 比它小并且第三维 \(x\) 比它大的，又要统计第二维 \(p\) 比它大并且第三维 \(x\) 比它小的。
\(2\).归并时，我们统计的是每个时间点的新产生的价值，所以最后应该进行一次前缀和。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=101100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int n,m;
int A[N];// ----------------------------------------#define lowbit(x) ( x&(-x) )
int T[N];inline void update(int x)
{ for(;x<=n;x+=lowbit(x)) T[x]++; }inline void Clear(int x)
{ for(;x<=n;x+=lowbit(x)) T[x]=0; }inline int query(int x)
{int sum=0;for(;x>0;x-=lowbit(x))sum+=T[x];return sum;
}//--------------------------------------struct ask
{int t,p,x;// 出现时间，出现的位置，数值大小
}Q[N],tmp[N];
int ans[N];bool rule_p(ask u,ask v)
{ return u.p<v.p; }inline void debug()
{cout<<endl;for(int i=1;i<=n;i++)printf("%d %d %d\n",Q[i].t,Q[i].p,Q[i].x);
}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,pos=l;for(;j<=r;j++){while(i<=mid && Q[i].p<Q[j].p){update(Q[i].x);tmp[pos++]=Q[i++];}ans[Q[j].t]+=query(n)-query(Q[j].x);tmp[pos++]=Q[j];}for(int k=l;k<i;k++) Clear(Q[k].x);while(i<=mid) tmp[pos++]=Q[i++];for(int k=l;k<=r;k++)Q[k]=tmp[k];// debug();for(int k=r;k>=l;k--){if(Q[k].t<=mid) update(Q[k].x);else ans[Q[k].t]+=query(Q[k].x);}for(int k=r;k>=l;k--)if(Q[k].t<=mid) Clear(Q[k].x);
}// ----------------------------------------
int D[N];bool rule_t(ask u,ask v)
{if(u.t!=v.t) return u.t<v.t;return u.p<v.p;
}inline void Prepare()
{int tim=n;for(int i=1;i<=n;i++) D[A[i]]=i;for(int i=1;i<=n;i++) Q[i]=(ask){ 0,i,A[i] };for(int i=1;i<=m;i++){int x=read();Q[D[x]].t=tim--;}for(int i=n;i>0;i--) if(!Q[i].t) Q[i].t=tim--;sort(Q+1,Q+n+1,rule_t);// debug();
}signed main()
{n=read(),m=read();for(int i=1;i<=n;i++) A[i]=read();Prepare(); cdq(1,n);for(int i=1;i<=n;i++) ans[i]+=ans[i-1];for(int i=n;i>n-m;i--) printf("%d\n",ans[i]);// debug();return 0;
}