[bzoj3295]-[CQOI2011]动态逆序对

题目（BZOJ）
题目（洛谷）
 
这题就是对每个点建个三元组：(时间，坐标，值)，然后就转化为三维偏序裸题了......
cdq分治重要思想：一维排序，二维分治，三维维护

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=100050;
int n,m,a[N],pos[N];
ll sum,ans[N];
ll c[N];
inline int lowbit(int x){return x&(-x);}
inline void change(int x,ll v){while(x<=n){c[x]+=v;x+=lowbit(x);}}
inline ll query(int x){ll ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
struct querys{
	int tim,pos,val,del;
}q[N],b[N];
inline bool cmp1(const querys &x,const querys &y){
	return x.tim<y.tim;
}
inline bool cmp2(const querys &x,const querys &y){
	if(x.pos==y.pos)return x.val<y.val;
	else return x.pos<y.pos;
}
void solve(int L,int R){
	if(L>=R)return;
	int mid=(L+R)>>1,cnt=0;
	for(int i=L;i<=mid;++i)b[++cnt]=q[i],b[cnt].del=0;
	for(int i=mid+1;i<=R;++i)b[++cnt]=q[i],b[cnt].del=1;
	sort(b+1,b+cnt+1,cmp2);
	for(int i=1;i<=cnt;++i){
		if(b[i].del==0)change(b[i].val,1);
		else ans[b[i].tim]+=query(n)-query(b[i].val);
	}
	for(int i=1;i<=cnt;++i)if(b[i].del==0)change(b[i].val,-1);
	for(int i=cnt;i;--i){
		if(b[i].del==0)change(b[i].val,1);
		else ans[b[i].tim]+=query(b[i].val);
	}
	for(int i=1;i<=cnt;++i)if(b[i].del==0)change(b[i].val,-1);
	solve(L,mid);
	solve(mid+1,R);
}
int main(){
	read(n),read(m);int nn=n;
	for(int i=1;i<=n;++i){
		read(a[i]);pos[a[i]]=i;
		q[i].pos=i;q[i].val=a[i];
	}
	for(int i=1;i<=m;++i){
		int x;read(x);
		q[pos[x]].tim=nn--;
	}
	for(int i=1;i<=n;++i)if(!q[i].tim)q[i].tim=nn--;
	sort(q+1,q+n+1,cmp1);
	solve(1,n);
	for(int i=1;i<=n;++i)sum+=ans[i];
	for(int i=n;i>n-m;--i)printf(
	return 0;
}