P3810 【模板】三维偏序（陌上花开） 题解

lao_wang · 2024-06-15 16:53:00 · 题解

修改

2025.7.1 改了一些东西。

使用算法

整体二分、树状数组、排序。

正文

写过线段树的都知道，线段树查区间和的时候是由几段具有可加性的贡献合并得出的，这会给降维带来什么启示？

一次三维偏序的询问是否能拆成（一定条件下的三维偏序，即只要满足二维偏序条件则满足三维偏序条件）若干个具有可加性的二维偏序的贡献加起来呢？

这显然是可以的，但是这个条件该怎么找才能使得复杂度没有问题呢？

在上线段树看看。（暂时将整体二分理解为权值线段树）

在线段树上的父节点连向的两个子节点为：一段区间由 mid 划分为 2 个区间：小于等于 mid 的左区间；大于 mid 的右区间。

那么对于任意一维条件通过与 mid 的大小关系划分使得左区间的三元组该条件小于等于 mid，右区间的三元组该条件大于 mid。（之后默认划分的第一维条件）

这样划分后可以发现：

这就消去了第一维。

再将左区间的所有三元组视为数值，右区间的左右三元组视为询问，去求解右区间在左区间中满足后两维偏序条件的贡献，直接上个二维偏序求解即可求出右区间三元组的部分答案（排序 + 树状数组）。

因为对于自己区间的三元组并没有进行贡献的转换，所以左右区间需要继续划分直至没有三元组可以视为数值（或区间左右端点重合）。（整个过程中所作为划分依据的那一维不能在途中改成其他维。）

这满足使用整体二分需要满足的性质：

1. 询问的答案具有可二分性。

2. 修改对判定答案的贡献互相独立，修改之间互不影响效果。

3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值。

4. 贡献满足交换律，结合律，具有可加性。

5. 题目允许使用离线算法。

   —— 许昊然《浅谈数据结构题几个非经典解法》

伪代码

void solve(int l,int r,int L,int R){  //l、r表示当前需要划分值域，L、R表示当前需要划分的三元组下标
    if(边界) return ;
    int mid=(l+r)>>1 ;
    for(int i=L;i<=R;i++){
        if(操作1){
             if(跟mid的关系) 划分区间;
             else 划分区间; 
        }else if(……)…… 
    }
    划分给左区间
    划分给右区间
    递归左区间 
    递归右区间 
}

将刚刚的思路整理一下就可以得到整体二分的写法了。

正确性

是否会算漏？

对于第一维（二三维因为是直接套用的二维偏序故不在赘述），当 a_i \leq a_j 时而三元组 i 并没有参与过三元组 j 的贡献计算即在递归过程中 i 所划分到的区间始终在右区间或与 j 同侧。

此时 a_i 在左区间，a_j 在右区间。

故对于 \forall a_i \leq a_j，均存在 a_i 在左区间，a_j 在右区间。

是否会算重？

当 a_i \leq a_j 且 i 对 j 计算过贡献时，i、j 在同一大区间（当前递归的值域），i 一定在左区间，j 一定在右区间。

而此后的递归不涉及区间合并所以 i、j 不会再次在同一大区间。

复杂度

对于一个询问需要的操作数等价于在权值线段树上查找某数值所在叶子节点，所以操作数为 N\log V。

又因为在每个三元组在每次操作需要调用一次数据结构（树状数组）。

所以复杂度为 O(N\log^2V)

做法说明

对于一个三元组，我们需要将其拆分为两个操作（偏序条件均为这个三元组）：插入和查询。

因为此题含有等于，所以在初始排序时（提前处理一维）需要在当前数值相等的情况下插入排在前面查询排在后面。

代码

#include<bits/stdc++.h>
#define N 412345
#define lowbit(x) ((x)&(-x))
#define inf 212345
using namespace std ;
int n , K , tr[N] , cnt=0 , ans[N] , real_ans[N] , q , num[N] , chong=0 ;
void change(int x,int k) {
    while(x<=K) {
        tr[x] += k ;
        x += lowbit(x) ;
    }
}
int ask(int x) {
    int ans=0 ;
    while(x) {
        ans += tr[x] ;
        x -= lowbit(x) ;
    }
    return ans ;
}
struct node {
    int x , y , z , opt , i , k ;
} a[N],q1[N],q2[N];
bool cmp(node a,node b){
    return a.x==b.x?(a.y==b.y?(a.z==b.z?a.opt<b.opt:a.z<b.z):a.y<b.y):a.x<b.x ;
}
void solve(int l,int r,int L,int R) {
    if(L>=R||l>r) return ;
    int mid=(l+r)>>1 , tot1=0 , tot2=0 ;
    for(int i=L; i<=R; i++) {
        if(a[i].opt==1){//在此处进行上述划分的左区间数值
            if(a[i].y<=mid) change(a[i].z,a[i].k) , q1[++tot1] = a[i] ;
            else q2[++tot2] = a[i] ;
        }else{//在此处进行上述划分的右区间询问
            if(a[i].y>=mid) ans[a[i].i] += ask(a[i].z) , q2[++tot2] = a[i] ;
            else q1[++tot1] = a[i] ;
        }
    }
    for(int i=1; i<=tot1; i++) {
        a[i+L-1] = q1[i] ;
        if(q1[i].opt==1) change(q1[i].z,-q1[i].k) ;
    }
    for(int i=1; i<=tot2; i++) a[i+L+tot1-1] = q2[i] ;
    if(l!=r) solve(l,mid,L,L+tot1-1) ;
    solve(mid+1,r,L+tot1,R) ;
}
signed main() {
    cin >> n >> K ;
    for(int i=1; i<=n; i++){
        int x , y , z ;
        scanf("%d%d%d",&x,&y,&z) ;
        a[i] = node{x,y,z,1,i,1} ;
        a[i+n] = node{x,y,z,2,i,1} ;
    }
    sort(a+1,a+1+n+n,cmp) ;
    solve(1,inf,1,n+n) ;
    for(int i=1;i<=n;i++) real_ans[ans[i]-1]++ ;
    for(int i=0;i<n;i++) printf("%d\n",real_ans[i]) ;
    return 0 ;
}