HDU 5126

灰太狼 2022-01-25 23:43 101阅读 0赞

## 题意：一共有Q(1<=Q<=50000)组操作，操作分为两种：1.在x,y,z处添加一颗星星，2.询问以(x1,y1,z1)与(x2,y2,z2)为左上和右下顶点的矩形之间的星星数，所有坐标取值范围均为\[1,1e9\]。 ##

## 思路：CDQ分治模板题，x，y，z和时间四维，是个四维带修改的偏序问题，所有操作按默认时间排序，将每个查询操作拆分为8个(容斥)，再进行两次分治。第一次分治：将q中每个子区间按x坐标从小到大排序，将左区间元素与右区间查询放入q2中，第二次分治(嵌套在第一次分治中)：将q2中每个子区间按y坐标从小到大排序，统计左区间元素对右区间查询的贡献(利用树状数组记录z值)，注意每次分治结束后，需将左右区间的所有元素按相应坐标大小归并排好序。这里用的是快排，离散化的时候注意下标要从1开始而不是从0开始，否则树状数组可能会陷入死循环。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int M = 5e5+10;
    
    int ans[M],c[M];
    ///默认对时间（id）排序
    struct node
    {
        int x,y,z;
        int kind,id;
        node(){}
        node(int x1,int y1,int z1,int k,int i):x(x1),y(y1),z(z1),kind(k),id(i){}
    };
    
    vector<node>q,q1,q2;
    vector<int>v;
    void init(){
        q.clear();
        v.clear();
        memset(c,0,sizeof(c));
    }
    ///对x排序
    bool cmp(node a,node b){
        if(a.x == b.x) return a.id < b.id;
        return a.x < b.x;
    }
    ///对y排序
    bool cmp1(node a,node b){
        if(a.y == b.y) return a.id < b.id;
        return a.y < b.y;
    }
    
    int lowbit(int x){
        return x&-x;
    }
    
    void add(int x,int val){
        while(x <= v.size()){
            c[x] += val;
            x += lowbit(x);
        }
    }
    
    int getsum(int x){
        int sum = 0;
        while(x > 0){
            sum += c[x];
            x -= lowbit(x);
        }
        return sum;
    }
    
    void countstar(){
        for(int i = 0;i < q2.size();i ++){
            if(q2[i].kind == 0) add(q2[i].z,1);
            else ans[q2[i].id] += q2[i].kind*getsum(q2[i].z);
        }
        ///每次统计完后清空树状数组 
        for(int i = 0;i < q2.size();i ++)
            if(q2[i].kind == 0) add(q2[i].z,-1);
    }
    
    void cdq1(int l,int r){
        if(l >= r) return ;
        int mid = (l + r) >> 1;
        cdq1(l,mid); cdq1(mid+1,r);
        q2.clear();
        ///只有[l,mid]中的修改会对[mid+1,r]的询问产生影响
        for(int i = l;i <= mid;i ++)
            if(q1[i].kind == 0) q2.push_back(q1[i]);
        for(int i = mid+1;i <= r;i ++)
            if(q1[i].kind) q2.push_back(q1[i]);
        sort(q2.begin(),q2.end(),cmp1);
        countstar();
    }
    
    void cdq(int l,int r){
        if(l >= r) return ;
        int mid = (l + r) >> 1;
        cdq(l,mid); cdq(mid+1,r);
        q1.clear();
        for(int i = l;i <= mid;i ++)
            if(q[i].kind == 0) q1.push_back(q[i]);
        for(int i = mid+1;i <= r;i ++)
            if(q[i].kind) q1.push_back(q[i]);
        sort(q1.begin(),q1.end(),cmp);
        cdq1(0,q1.size()-1);
    }
    
    
    int main()
    {
        int t,n,op,x,y,z,x1,y1,z1,x2,y2,z2;
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            init();
            for(int i = 0;i < n;i ++){
                scanf("%d",&op);
                if(op == 1){
                    scanf("%d%d%d",&x,&y,&z);
                    q.push_back(node(x,y,z,0,i));
                    v.push_back(z);
                    ans[i] = -1;
                }
                else{
                    scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
                    x1--; y1--; z1--;
                    ///容斥 加加减减
                    q.push_back(node(x1,y1,z1,-1,i));
                    q.push_back(node(x2,y2,z2,1,i));
                    q.push_back(node(x1,y2,z2,-1,i));
                    q.push_back(node(x2,y1,z2,-1,i));
                    q.push_back(node(x2,y2,z1,-1,i));
                    q.push_back(node(x2,y1,z1,1,i));
                    q.push_back(node(x1,y2,z1,1,i));
                    q.push_back(node(x1,y1,z2,1,i));
                    v.push_back(z1); v.push_back(z2);
                    ans[i] = 0;
                }
            }
            ///离散化
            sort(v.begin(),v.end());
            ///v.erase(unique(v.begin(),v.end()),v.end());
            ///树状数组下标从一开始
            for(int i = 0;i < q.size();i ++)
                q[i].z = (lower_bound(v.begin(),v.end(),q[i].z)-v.begin())+1;
            cdq(0,q.size()-1);
            for(int i = 0;i < n;i ++)
                if(ans[i] != -1) printf("%d\n",ans[i]);
        }
        return 0;
    }