hdu5517 二维树状数组

题意是给了 n个二元组 m个三元组， 二元组可以和三元组 合并生成3元组，合并条件是<a,b> 与<c,d,e>合并成 <a,c,d> 前提是 b==e，

如果存在组合 uwv 使得u>=a w>=c v>=d 并且uwv和acd不等  就说abc 不是最优的，求问最后又多少个组合是最优的 ， 这个组合中是允许重复的

我们对于每个b只取最大的a，然后让这个最大的a去和相应的b,c进行组合，然后对于这样的三元组 为了省去判断和他相等的个数，我们直接将相同的元组合并到一起去，

然后枚举a求在 在矩阵C[b][c]右下边是否存在值如果存在显然这个就不是最优的，用二维树状数组解决这个问题

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <string.h>

using namespace std;

const int maxn=;

struct point{

  int a,c,d,nu;

  bool operator <(const point &rhs)const{

      if(a!=rhs.a)return a<rhs.a;

      if(c!=rhs.c)return c<rhs.c;

      return d<rhs.d;

  }

  bool operator ==(const point &rhs)const{

     return a==rhs.a&&c==rhs.c&&d==rhs.d;

  }

}P[maxn];

int B[maxn];

int nu[maxn];

int C[][];

int Nc,Nd,numofC;

void init()

{

    numofC=Nc=Nd=;

    memset(B,,sizeof(B));

    memset(nu,,sizeof(nu));

    memset(C,,sizeof(C));

}

int lowbit(int x)

{

    return x&(-x);

}

void add(int c,int d,int val)

{

    for(int i=c; i<=Nc; i+=lowbit(i))

        for(int j=d; j<=Nd; j+=lowbit(j))

           C[i][j]+=val;

}

int sum(int c, int d)

{

    int ans=;

    for(int i=c; i>; i-=lowbit(i))

        for(int j=d; j>; j-=lowbit(j))

          ans+=C[i][j];

    return ans;

}

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; cc++)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        init();

        for(int i=; i<n; i++)

        {

             int a,b;

             scanf("%d%d",&a,&b);

             if(B[b]<a){ B[b]=a; nu[b]=;}

             else if(B[b]==a) nu[b]++;

        }

        for(int i=; i<m; i++)

        {

            int c,d,e;

            scanf("%d%d%d",&c,&d,&e);

            if(nu[e]>)

            {

                point t;

                t.a=B[e]; t.c=c; t.d=d; t.nu=nu[e];

                P[numofC++]=t;

            }

            Nc=max(c,Nc); Nd=max(Nd,d);

        }

        sort(P,P+numofC);

        int ge=;

        for(int i=; i<numofC; i++)

            if(P[i]==P[ge-])P[ge-].nu+=P[i].nu;

            else P[ge++]=P[i];

        numofC=ge;

        int ans=;

        ge=;

        for(int i=numofC-; i>=; i--)

        {

            point t=P[i];

            int s2=sum(t.c-,Nd);

            int s3=sum(Nc,t.d-);

            int s4=sum(t.c-,t.d-);

            if(ge-s2-s3+s4 == ){

                ans+=t.nu;

            }

            ge++;

            add(t.c,t.d,);

        }

        printf("Case #%d: %d\n",cc,ans);

    }

    return ;

}