HDU 5517 三维偏序二维树状数组-蒲公英云

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

题意：已知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;
}