陌上花开 CDQ分治

传送门：

题意：

\[ 有n 个元素，第 i 个元素有 a_i、 b_i、 c_i 三个属性，设 f(i) 表示满足 a_j\leq a_i 且 b_j \leq b_i且 c_j \leq c_i的 j 的数量。\\ 对于 d \in [0, n]，求 f(i) = d 的数量 \]

题解：

CDQ分治模板题，

我们将第一维在主函数排序后，cdq分治里面，每次将左半边和右半边按照y排序，因为一开始的x是已经排序过了的，所以分治将其分为左半边和右半边时，左半边的x还是小于右半边的x，因此维护右半边的位置i和左半边的位置j，如果y[j]<y[i]的话，我们就可以将z[j]丢进树状数组中，直到y[j]>=y[i]时，不满足偏序关系的时候，我们就可以直接树状数组查询小于z[i]的前半部分的j的个数，这样，这么多个数就满足三维的偏序关系。

1.x的偏序关系已经在主函数里面处理，所以分治分了后前一半的x小于后一半的x

2.y的偏序关系是两个指针对着扫了，一遍，将满足y[j]<y[i]的z[j]丢进了树状数组统计个数

3.z的偏序关系是从树状数组中查的小于z[i]的z[j]有多少个

一直这样分治下去，我们就可以得到最终的答案

这个题有一个坑点就是，当x,y,z都相同时，在分治的时候，本来它们相互之间都有贡献，可是cdq的过程中只有左边的能贡献右边的。这可怎么办呢？我们直接离散化后，给定一个权值，这样算贡献就不会算错了

代码：

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;typedef long long LL;typedef pair
             
               pii;typedef unsigned long long uLL;#define ls rt<<1#define rs rt<<1|1#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define bug printf("*********\n")#define FIN freopen("input.txt","r",stdin);#define FON freopen("output.txt","w+",stdout);#define IO ios::sync_with_stdio(false),cin.tie(0)#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<
              
               <<"]\n"const int maxn = 3e5 + 5;const int INF = 0x3f3f3f3f;struct node { int x, y, z; int cnt; int ans;} a[maxn];bool cmpx(node a, node b) { if(a.x == b.x && a.y == b.y) return a.z < b.z; if(a.x == b.x) return a.y < b.y; return a.x < b.x;}bool cmpy(node a, node b) { if(a.y == b.y && a.z == b.z) return a.x < b.x; if(a.y == b.y) return a.z < b.z; return a.y < b.y;}int lowbit(int x) { return x & (-x);}int bit[maxn];void add(int pos, int val) { while(pos < maxn) { bit[pos] += val; pos += lowbit(pos); }}int sum(int pos) { int res = 0; while(pos) { res += bit[pos]; pos -= lowbit(pos); } return res;}int num[maxn];void CDQ(int l, int r) { if(l == r) { a[l].ans += a[l].cnt - 1; return; } int mid = (l + r) >> 1; CDQ(l, mid); CDQ(mid + 1, r); sort(a + l, a + mid + 1, cmpy); sort(a + mid + 1, a + r + 1, cmpy); int j = l; for(int i = mid + 1; i <= r; i++) { while(j <= mid && a[j].y <= a[i].y) { add(a[j].z, a[j].cnt); j++; } a[i].ans += sum(a[i].z); } for(int i = l; i < j; i++) { add(a[i].z, -a[i].cnt); }}int main() {#ifndef ONLINE_JUDGE FIN#endif int n, k; scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) { scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z); a[i].ans = 1; } sort(a + 1, a + n + 1, cmpx); int tot = 0; for(int i = 1; i <= n; ++i) { if(i != 1 && a[i].x == a[i - 1].x && a[i].y == a[i - 1].y && a[i].z == a[i - 1].z) a[tot].cnt++; else a[++tot] = a[i], a[tot].cnt = 1; } CDQ(1, tot); sort(a + 1, a + tot + 1, cmpx); for(int i = 1; i <= tot; i++) { num[a[i].ans] += a[i].cnt; } for(int i = 1; i <= n; i++) { printf("%d\n", num[i]); } return 0;}

转载于:https://www.cnblogs.com/buerdepepeqi/p/11182571.html

你可能感兴趣的文章