【模板】三维偏序

题目背景

这是一道模板题

可以使用bitset，CDQ分治，K-DTree等方式解决。

题目描述

有 nn 个元素，第 ii 个元素有 a_ia​i​​、b_ib​i​​、c_ic​i​​ 三个属性，设 f(i)f(i) 表示满足 a_j \leq a_ia​j​​≤a​i​​ 且 b_j \leq b_ib​j​​≤b​i​​ 且 c_j \leq c_ic​j​​≤c​i​​ 的 jj 的数量。

对于 d \in [0, n)d∈[0,n)，求 f(i) = df(i)=d 的数量

输入输出格式

输入格式：

 

第一行两个整数 nn、kk，分别表示元素数量和最大属性值。

之后 nn 行，每行三个整数 a_ia​i​​、b_ib​i​​、c_ic​i​​，分别表示三个属性值。

 

输出格式：

 

输出 nn 行，第 d + 1d+1 行表示 f(i) = df(i)=d 的 ii 的数量。

 

输入输出样例

输入样例#1：

10 33 3 32 3 32 3 13 1 13 1 21 3 11 1 21 2 21 3 21 2 1

输出样例#1：

3130101001

说明

1 \leq n \leq 100000, 1 \leq k \leq 2000001≤n≤100000,1≤k≤200000

题解：

CDQ分治。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,num,c[200001],ans[200001];struct node{ int a,b,c,cnt,ans;}s[100001];bool cmp2(node x,node y){ if(x.b==y.b) return x.c
           
            =r)return; int mid=(l+r)>>1; CDQ(l,mid); CDQ(mid+1,r); sort(s+l,s+mid+1,cmp2); sort(s+mid+1,s+r+1,cmp2); int left=l,right=mid+1; while(right<=r) { while(left<=mid&&s[left].b<=s[right].b) { add(s[left].c,s[left].cnt); left++; } s[right].ans+=getsum(s[right].c); right++; } for(i=l;i<=left-1;i++)add(s[i].c,-s[i].cnt);}int main(){ int i,j; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c),s[i].cnt=1; sort(s+1,s+n+1,cmp); for(i=1;i<=n;i++) { int k=i+1; while(s[i].a==s[k].a&&s[i].b==s[k].b&&s[i].c==s[k].c)k++; num++;k--; s[i].cnt+=k-i; s[num]=s[i]; i=k; } CDQ(1,num); for(i=1;i<=num;i++) ans[s[i].ans+s[i].cnt-1]+=s[i].cnt; for(i=0;i<=n-1;i++)printf("%d\n",ans[i]); return 0;}