HDU 5517 三维偏序二维树状数组

爱被打了一巴掌 2022-05-08 08:28 240阅读 0赞

题意：已知A集合（a，b），B集合（c，d，e）C=A\*B=(a, c, d)在b和e相等的情况下才可以，问题是求出C中有几个元素，该元素除了自己没有比他大的，'>'的定义是当 a>=a' && b>=b' && c>=c'时，才成立。

思路：三位偏序cdq可以解决，但是如果抓住c，d的范围是1000的话，可以直接用二维树状数组代替。

由于A集合大小是1e5，B集合大小也是1e5，直接运算c集合能爆，对于A集合，同一个b只要取a最大的保留就可以，

这样出题人给出最大数据C集合只能到1e5的大小。

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    
    struct PAIR{
        int a, b;
        bool operator <(PAIR t) const{
            return b<t.b || b==t.b && a>t.a;
        }
    }p[N];
    struct Triple{
        int a, b, c, cnt;
        bool operator < (Triple t) const{
            return c<t.c;
        }
    }tr[N], C[N];
    int n, m, num[N];
    
    bool cmp(Triple a, Triple b){
        return a.a>b.a||a.a==b.a&&a.b>b.b||a.a==b.a&&a.b==b.b&&a.c>b.c;
    }
    
    int s[1010][1010];
    
    void upd(int a, int b, int v){
        for(int x=a;x>0;x-=x&-x)
            for(int y=b; y>0; y-=y&-y)
                s[x][y]+=v;
    }
    
    int query(int a, int b){
        int ret=0;
        for(int x=a;x<1010;x+=x&-x)
            for(int y=b;y<1010;y+=y&-y)
                ret+=s[x][y];
        return ret;
    }
    
    void ss(struct PAIR q[], int nn){
    
        for(int i=1; i<=nn; i++)
            printf("(%d, %d) ", q[i].a, q[i].b);
        puts("");
    
    }
    
    
    void show(struct Triple q[], int nn){
    
        for(int i=1; i<=nn; i++)
            printf("(%d, %d, %d) ", q[i].a, q[i].b, q[i].c);
        puts("");
    
    }
    
    int main(){
        /*upd(2, 4, 3);
        printf("%d\n", query(1, 4));*/
        int T, cas=0;
        scanf("%d", &T);
        while(T--){
            memset(num, 0, sizeof num);
            memset(s, 0, sizeof s);
            scanf("%d%d", &n, &m);
    
            for(int i=1; i<=n; i++)
                scanf("%d%d", &p[i].a, &p[i].b);
            for(int i=1; i<=m; i++)
                scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
            sort(p+1, p+1+n);
    
            int tot=0, a=-1, b=-1, c=-1;
            for(int i=1; i<=n; i++){
                if(p[i].b==b){
                    if(p[i].a==a)
                        num[tot]++;
                    //cout<<"***"<<endl;
                }
                else{
                    b=p[++tot].b=p[i].b;
                    a=p[tot].a=p[i].a;
                    num[tot]=1;
    
                }
            }
    
            int n1=0;
            for(int i=1; i<=tot; i++){
                for(int j=1; j<=m; j++){
                    if(p[i].b==tr[j].c){
                        C[++n1].a=p[i].a;
                        C[n1].b=tr[j].a;
                        C[n1].c=tr[j].b;
                        C[n1].cnt=num[i];
                    }
                }
            }
           // ss(p, tot);
           /*show(tr, m);
            show(C, n1);*/
            sort(C+1, C+1+n1, cmp);
            a=-1, b=-1, c=-1;
            int n2=0;
            for(int i=1; i<=n1; i++){
                if(C[i].a==a && C[i].b==b && C[i].c==c)
                    C[n2].cnt+=C[i].cnt;
                else{
                    C[++n2]=C[i];
                    a=C[i].a; b=C[i].b; c=C[i].c;
                }
            }
    
            int ans=0;
            for(int i=1; i<=n2; i++){
    
                if(query(C[i].b, C[i].c)==0){
                    ans+=C[i].cnt;
                   // printf("(%d, %d, %d): %d\n", C[i].a, C[i].b, C[i].c, C[i].cnt);
                }
                upd(C[i].b, C[i].c, 1);
            }
    
            printf("Case #%d: %d\n", ++cas, ans);
    
        }
        return 0;
    }