HDU5517(Triple)

链接：https://vjudge.net/problem/HDU-5517
思路：之前没写过二维树状数组啊，不过大概知道原理，这个题也是，比较三维的话，我们可以先把一维排好序，然后变为剩下二维，正好这二维数据范围较小，可以用前缀来维护，只要前面的和等于0，就说明前面没有完全被覆盖的(因为a是按排序大小来的)，此时把当前加入集合中。注意有几个优化，首先当原来b相同的二元组时，我们只需要取最大的a即可，因为此时小的a合并后一定会被大的a囊括，不会属于新的集合，那么对于相同最大b对应的最大a我们记录下他的个数，合并成新的三元组也对应这么多个数，最后可能不同b会产生相同三元组，我们先对新集合按a，b，c排序，如果相邻项相等的话则我们把它合并，然后最后用二维树状数组维护b，c，当前缀和为0满足的元素加1，求出答案即可。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1010;

long long csum[maxn][maxn];

struct tri{//三元组
    int a,b,c;
    long long num;
    bool operator<(const tri & r)const{
        if(a!=r.a) return a<r.a;
        if(b!=r.b)return b<r.b;
        if(c!=r.c)return c<r.c;
        return num<r.num;
    }
    bool operator==(const tri &r)const{//比较
        return a == r.a && b == r.b && c == r.c;
    }
}ss[100010];

int lowbit(int x){
    return x&(-x);
}

void add(int x,int y,long long d){
    for(int i=x;i<=1000;i+=lowbit(i)){
        for(int j=y;j<=1000;j+=lowbit(j)){
            csum[i][j]+=d;
        }
    }
}

long long s(int x,int y){
    long long ret = 0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            ret+=csum[i][j];
        }
    }
    return ret;
}

long long sum(int x1,int y1,int x2,int y2){
    return s(x2,y2) - s(x1-1,y2) - s(x2,y1-1) + s(x1-1,y1-1);
}

int maxv[100010];
int cnt[100010];

int t,n,m;

int main(){
    int kase = 0;
    scanf("%d",&t);
    while(t--){
        memset(csum,0,sizeof(csum));
        memset(maxv,0,sizeof(maxv));
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){//统计相同b中的最大的a的值
            int a,b;
            scanf("%d%d",&a,&b);
            if(maxv[b]<a){
                maxv[b] = a;
                cnt[b] = 1;
            }
            else if(maxv[b]==a)cnt[b]++;
        }
        for(int i=1;i<=m;i++){
            int c,d,e;
            scanf("%d%d%d",&c,&d,&e);
            ss[i] = {maxv[e],c,d,cnt[e]};//生成新的三元组
        }
        sort(ss+1,ss+m+1);
        int tot = 0;
        for(int i=1;i<=m;i++){
            if(!ss[i].num)continue;
            if(ss[i]==ss[tot])ss[tot].num+=ss[i].num;//合并相邻的相同项
            else ss[++tot] = ss[i];
        }
        long long ans = 0;
        for(int i = tot;i>=1;i--){
            if(!sum(ss[i].b,ss[i].c,1000,1000))ans+=ss[i].num;
            add(ss[i].b,ss[i].c,ss[i].num);
        }
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return 0;
}