传送门

CDQ分治

感觉CDQ分治擅长于处理1-3维度内数据的不等关系，一般的处理都是一维sort，二维CDQ，三维树状数组一类的。一般的总体复杂度都是$O(Nlog^2N)$。

这道题的的维度可以视为3个，一是时间，二是位置，三是初值。位置不够的手动补全就行了。然后做两次CDQ分治即可。

//BZOJ 3295//by Cydiater//2016.10.13#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstdlib>#include <iomanip>#include <cstdio>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M,num[MAXN],del[MAXN],ask,Pos[MAXN];ll c[MAXN];bool avail[MAXN];struct DEL{	int t,v,pos;ll ans;	DEL(){ans=0;}}a[MAXN],b[MAXN];namespace solution{	inline int lowbit(int i){return ((i)&(-i));}	inline bool cmp(DEL x,DEL y){return x.t<y.t;}	inline bool re_cmp(DEL x,DEL y){return x.t>y.t;}	inline void insert(int pos,int v){for(int i=pos;i>=1;i-=lowbit(i))c[i]+=v;}	inline int get(int pos){int tmp=0;for(int i=pos;i<=N;i+=lowbit(i))tmp+=c[i];return tmp;}	inline	void Insert(int pos,int v){for(int i=pos;i<=N;i+=lowbit(i))c[i]+=v;}	inline int Get(int pos){int tmp=0;for(int i=pos;i>=1;i-=lowbit(i))tmp+=c[i];return tmp;}	void init(){		memset(avail,0,sizeof(avail));		N=read();M=read();		up(i,1,N)Pos[(num[i]=read())]=i;		up(i,1,M){			del[i]=read();			avail[del[i]]=1;		}ask=M;		up(i,1,N)if(!avail[i])del[++M]=i;		down(i,M,1){			a[i].t=M-i+1;a[i].v=del[i];a[i].pos=Pos[a[i].v];		}//no equal so sort only t -> added time		sort(a+1,a+M+1,cmp);	}	void slove1(int leftt,int rightt){		if(leftt==rightt)		return;		int mid=(leftt+rightt)>>1;		slove1(leftt,mid);slove1(mid+1,rightt);//sorted by pos		int point=leftt;		up(i,mid+1,rightt){			int lim=a[i].pos;			while(point<=mid&&a[point].pos<lim)insert(a[point++].v,1);			a[i].ans+=get(a[i].v+1);		}		up(i,leftt,point-1)insert(a[i].v,-1);		int j=leftt,k=mid+1;		up(i,leftt,rightt)b[i]=((j<=mid&&a[j].pos<a[k].pos)||k>rightt)?a[j++]:a[k++];		up(i,leftt,rightt)a[i]=b[i];	}	void slove2(int leftt,int rightt){		if(leftt==rightt)		return;		int mid=(leftt+rightt)>>1;		slove2(leftt,mid);slove2(mid+1,rightt);//sorted by pos		int point=leftt;		up(i,mid+1,rightt){			int lim=a[i].pos;			while(point<=mid&&a[point].pos>lim)Insert(a[point++].v,1);			a[i].ans+=Get(a[i].v-1);		}		up(i,leftt,point-1)Insert(a[i].v,-1);		int j=leftt,k=mid+1;		up(i,leftt,rightt)b[i]=((j<=mid&&a[j].pos>a[k].pos)||k>rightt)?a[j++]:a[k++];		up(i,leftt,rightt)a[i]=b[i];	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	slove1(1,M);	sort(a+1,a+M+1,cmp);	slove2(1,M);	sort(a+1,a+M+1,cmp);	up(i,1,M)a[i].ans+=a[i-1].ans;	sort(a+1,a+M+1,re_cmp);	up(i,1,ask)printf("%lld\n",a[i].ans);	return 0;}

BZOJ3295: [Cqoi2011]动态逆序对