\(n\) 维偏序即给出若干个点对 \((a_{i},b_{i},\cdots,n_{i})\)，对每个 \(i\) 求出满足 \(a_{j}\gt a_{i},b_{j}\gt b_{i}\cdots,n_{j}\gt n_{i}\) 的 \(j\) 的个数
一维偏序
直接用权值线段树或者树状数组. 或者你直接离散化开桶前缀和.
二维偏序
考虑到先对全部点对按 \(a_{i}\) 排序，这样，任何点对只能被它前面的点产生贡献.
a 1 1 1 2 3 4 4 5
b 1 2 3 3 4 2 4 1
可以发现，\(i\) 处的答案可以转化为：其前方的点中满足一维偏序的点数.
所以我们考虑对点对从左到右扫一遍，每次向维护的动态树状数组中加入一个新节点，统计前缀和即可.
三维偏序
CDQ+数据结构 解法
按二维偏序的套路，先对 \(a_{i}\) 排序
然后我们考虑这样分解问题：向下对 \(b\) 进行归并排序，每次只统计 \(i\in[l,mid],j\in[mid+1,r]\) 的答案. 可以发现，对于区间内部的答案，总会有递归下去的子区间来求解，对于区间之间的答案，当前这一步将会求解出来，因此我们恰好统计了所有答案，这就是 CDQ 分治.
为什么我们在进行统计答案的时候需要对 \(b\) 排序？假设现在两个子区间内的 \(b\) 都是有序的（\(a\) 是完全有序的，我们不管它），那么在对 \(b\) 归并排序的过程中，会发现，只有 \(i\) 能对 \(j\) 产生贡献（因为 \(a\) 数组的限制），并且只有 \(i\) 数对的 \(b\) 比 \(j\) 数对的 \(b\) 更小的时候，\(i\) 才可能对 \(j\) 有贡献，表现在归并排序里就是只有比 \(j\) 先选的 \(i\) 才能对 \(j\) 有贡献. 基于这一点，我们才能用树状数组+CDQ分治来解决偏序问题.
#include<bits/stdc++.h>
using namespace std;
#define p &
int n,k;
struct node{
int a,b,c;
int cnt,res;
bool operator !=(const node &A)const{
return a!=A.a or b!=A.b or c!=A.c;
}
};
node e[100001];
node ue[100001];
int m,t;
int res[100001];
struct bit{
int a[200001];
function<int(int)> lowbit=[](int x){return x&-x;};
inline void add(int pos,int val){
while(pos<=k){
a[pos]+=val;
pos+=lowbit(pos);
}
};
inline int ask(int pos){//sum[pos]
int res=0;
while(pos){
res+=a[pos];
pos-=lowbit(pos);
}
return res;
};
}BIT;
bool cmp1(node a,node b){
if(a.a!=b.a) return a.a<b.a;
if(a.b!=b.b) return a.b<b.b;
return a.c<b.c;
}
bool cmp2(node a,node b){
if(a.b!=b.b) return a.b<b.b;
return a.c<b.c;
}
void cdq(int l,int r){
if(l==r) return;//i!=j 单个区间无法产生贡献
int mid=(l+r)/2;
cdq(l,mid);//递归求解子区间
cdq(mid+1,r);
sort(ue+l,ue+mid+1,cmp2);//按 b 排序，方便归并
sort(ue+mid+1,ue+r+1,cmp2);
int i=l,j=mid+1;//归并排序
//注意这里并不会真的排序，因为父区间会有 sort 的
while(j<=r){
while(i<=mid and ue[i].b<=ue[j].b){
//当前 i 更小，将会对 j 与 j 后方的位置产生贡献
BIT.add(ue[i].c,ue[i].cnt);
i++;
}
//后面的 i 值不再能够产生贡献了，此时暂时统计答案
ue[j].res+=BIT.ask(ue[j].c);
j++;
}
for(int k=l;k<=i-1;++k){
BIT.add(ue[k].c,-ue[k].cnt);
//清空 BIT，memset 也行就是有点慢
}
}
int main(){
scanf("%d %d",p n,p k);
for(int i=1;i<=n;++i){
scanf("%d %d %d",p e[i].a,p e[i].b,p e[i].c);
}
sort(e+1,e+n+1,cmp1);
for(int i=1;i<=n;++i){
t++;
if(e[i]!=e[i+1]){
//去重，防止相同的元素统计不到而漏答案
ue[++m]={e[i].a,e[i].b,e[i].c,t};
t=0;
}
}
cdq(1,m);
for(int i=1;i<=m;++i){
//去重在这里用到了
res[ue[i].res+ue[i].cnt-1]+=ue[i].cnt;
}
for(int i=0;i<=n-1;++i){
printf("%d\n",res[i]);
}
}
数据结构+数据结构
众所周知，三维偏序可以用树套树来解决.
我并不是非常喜欢写树套树，因此就写了一个树套树
我说怎么没人线段树套线段树，原来是会 TLE 啊，哈哈哈
标签：偏序,node,return,val,OI,int,mid,now From： https://www.cnblogs.com/HaneDaCafe/p/18351138