二维偏序
Q: 给定N个有序对 \((a,b)\)，求对于每个 \((a,b)\)，满足 \(a_0 < a\) 且 \(b_0 < b\) 的有序对 \((a_0,b_0)\) 有多少个
经典的逆序对问题，可以考虑用树状数组解决，先按照第一维排序，然后离散化在第一维已经处理的情况下去边处理第二维边记录。
1. CF1311F Moving Points
不难发现，先将 \(x\) 按升序排序，然后考虑 \(v\)，对于 \(x_i<x_j\)，如果 \(v_i>v_j\) 那么对答案的贡献为 \(0\)，否则贡献为 \(x_j-x_i\)，而对于所有的 \(i<j\) 都是如此，所以可以考虑开两个树状数组，一个用于记录当前已经发现的 \(小于v_j\) 的个数，另一个记录 \(小于v_j\) 的距离之和，所以就欧了。
const int N=200010;
int n,a[N],l[N];
struct Node{
ll x,v;
}node[N];
ll dis[N],tr[N];
inline int lowbit(int x){return x&(-x);}
inline void Add(int x,ll d,ll tree[])
{while(x<=n) tree[x]+=d,x+=lowbit(x);}
inline ll Ask(int x,ll tree[]){
ll res=0;
while(x) res+=tree[x],x-=lowbit(x);
return res;
}
signed main(){
IOS
cin>>n;
for(int i=1;i<=n;++i) cin>>node[i].x;
for(int i=1;i<=n;++i) cin>>node[i].v,a[i]=node[i].v;
sort(node+1,node+1+n,[&](Node A,Node B)
{ return A.x<B.x;});
sort(a+1,a+1+n); int len=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=n;++i) l[i]=lower_bound(a+1,a+1+len,node[i].v)-a;
ll ans=0;
for(int i=1;i<=n;++i){
ans+=Ask(l[i],tr)*node[i].x-Ask(l[i],dis);
Add(l[i],node[i].x,dis);
Add(l[i],1,tr);
}
cout<<ans<<'\n';
return 0;
}
三维偏序
三元组 \((a,b,c)\)，求有多少个 \((a_i,b_i,c_i) \leqslant (a_j,b_j,c_j)\)。
解法有很多，如 \(KD-Tree\)，但是目前只学了 \(CDQ(陈丹琦)分治\)。
需要注意的是，CDQ分治只适用于“可以将在线操作转化成离线”的情况，毕竟是分治，是在得到所有命令之后的函数，不能动态维护
不妨先按第一维排序。由于直接计算很困难，所以考虑类似归并排序的分治解决，即考虑左边对右边的贡献，可以在 \(nlogn\) 时间复杂度内算出所有答案。
首先考虑一段区间 \([l,r]\)，令 \(mid=(l+r)/2\)，那么根据分治思想，考虑左边对右边做出的贡献。因为先前已经将第一维排序过，所以此时对于第一维，左半边元素一定小于右半边元素。这样子很想逆序对问题，可以用 \(Fenwick \ Tree\)：此时将左右半边各按第二维进行排序，然后进行双指针扫描，比如，\(i=l,j=mid+1\)，那么对于右边元素 \(j\)，左边 \(i\) 元素的第二维必须小于等于它才能对之做出贡献，但是由于第三维不确定，所以将第三维放入树状数组之类的数据结构，那么此时对于 \(j\)，只需要找出树状数组中存储的第三维小于等于它的就好了，如此就是左边对右边该数的贡献。发现每一个数左边对它的贡献都一定计算过，所以正确性显然。
1. P3810 三维偏序
就是上面所说。
struct Node{
int x,y,z,tot,res;
}a[N],b[N];
inline void CDQ(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ(l,mid),CDQ(mid+1,r);
sort(b+l,b+1+mid,[&](Node A,Node B)
{ return (A.y==B.y)?A.z<B.z:A.y<B.y;});
sort(b+1+mid,b+1+r,[&](Node A,Node B)
{ return (A.y==B.y)?A.z<B.z:A.y<B.y;});//以第二维为关键字排序
int i=mid+1,j=l;
for(;i<=r;++i){
while(b[i].y>=b[j].y&&j<=mid)//j<=mid为边界
Add(b[j].z,b[j].tot),++j;
b[i].res+=Ask(b[i].z);
}
for(i=l;i<j;++i) Add(b[i].z,-b[i].tot);//清空,l~j-1段
}
signed main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
IOS
cin>>n>>mx;
for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+1+n,[&](Node A,Node B)
{return A.x<B.x||(A.x==B.x&&A.y<B.y)||(A.x==B.x&&A.y==B.y&&A.z<B.z);});
for(int i=1;i<=n;){//去重
int j=i+1;
while(j<=n&&(a[i].x==a[j].x&&a[i].y==a[j].y&&a[i].z==a[j].z)) ++j;
++m; b[m]=a[i],b[m].tot=j-i; i=j;
}
CDQ(1,m);
for(int i=1;i<=m;++i)
ans[b[i].res+b[i].tot-1]+=b[i].tot;
for(int i=0;i<n;++i) cout<<ans[i]<<'\n';
return 0;
}
2. P4390 [BalkanOI2007] Mokia
这道题中第一维变成了时间，后两维成为了平面坐标。
不过需要注意的是，询问的是正方形区域，所以考虑容斥，即二维前缀和计数方法。
const int Q=200010,N=2000010;
int n,m,mx,tr[N],ans[Q];
struct O{int opt,x,y,tot,num;}o[Q];
inline int lowbit(int x){ return x&(-x);}
inline void Add(int x,int val,int tree[])
{while(x<=mx) tree[x]+=val,x+=lowbit(x);}
inline int Ask(int x,int tree[]){
if(!x) return 0;
int res=0;
while(x) res+=tree[x],x-=lowbit(x);
return res;
}
inline void CDQ(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ(l,mid),CDQ(mid+1,r);
sort(o+l,o+mid+1,[&](O A,O B){
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
});
sort(o+mid+1,o+r+1,[&](O A,O B){
if(A.x==B.x) return A.y<B.y;
return A.x<B.x;
});
int i=l,j=mid+1;
for(;j<=r;++j){
if(o[j].opt&1) continue;
while(i<=mid&&o[i].x<=o[j].x){
if(o[i].opt&1) Add(o[i].y,o[i].tot,tr);
++i;
}
ans[o[j].num]+=Ask(o[j].y,tr)*o[j].tot;
}
for(j=l;j<i;++j) if(o[j].opt&1) Add(o[j].y,-o[j].tot,tr);
}
signed main(){
IOS
int opt; cin>>opt>>mx; ++mx;
while(cin>>opt&&opt!=3){
if(opt&1){
int x,y,a;
cin>>x>>y>>a;
o[++m]={opt,x,y,a,0};
} else{
int xa,ya,xb,yb;
cin>>xa>>ya>>xb>>yb; ++n;
o[++m]={opt,xb,yb,1,n};
o[++m]={opt,xa-1,yb,-1,n};
o[++m]={opt,xb,ya-1,-1,n};
o[++m]={opt,xa-1,ya-1,1,n};
}
}
CDQ(1,m);
for(int i=1;i<=n;++i)
cout<<ans[i]<<'\n';
return 0;
}