【HDOJ5517】Triple（二维BIT）

题意：给你n个二元组<a,b>, m个三元组<c,d,e>. 如果d = e,那么<a,c,d>会组成一个新的三元组集合G.

问G中有多少个三元组在凸点.(没有其它三元组比它大)

定义大为一个三维偏序的关系，若(x,y,z)与(a,b,c)不完全相同并且x>=y,y>=b,z>=c则描述为(x,y,z)比(a,b,c)大

n,m<=1e5，1<=a[i],b[i],e[i]<=1e5，1<=c[i],d[i]<=1e3

思路：对于一个b只保留最大的a，记录最值与出现的次数

用vector存对于每一个e来说的所有(c,d)，生成所有(a,c,d)后按a从大到小排序，相同的数对合并，剩下的两维就转化为单点修改，询问右下矩形有没有点

因为1<=c[i],d[i]<=1e3，用二维数组维护，前缀和改成后缀和即可

这轮补题补完把陌上花开补一下吧……都搁了不知道多久了

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N  110000

 #define M  1100

 #define MOD 2147493647

 #define eps 1e-8

 #define pi acos(-1)

 #define oo 1100000000

 struct node

 {

     int x,y;

     node() {}

     node(int x,int y):x(x),y(y) {}

 };

 vector<node>c[N];

 struct arr

 {

     int x,y,z,num;

 }a[N];

 ll t[M][M];

 int mx[N],num[N];

 bool cmp(arr a,arr b)

 {

     if(a.x!=b.x) return a.x>b.x;

     if(a.y!=b.y) return a.y>b.y;

     return a.z>b.z;

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 ll query(int X,int Y)

 {

     ll ans=;

     int x=X;

     while(x<=M-)

     {

         int y=Y;

         while(y<=M-)

         {

             ans+=t[x][y];

             y+=lowbit(y);

         }

         x+=lowbit(x);

     }

     return ans;

 }

 void add(int X,int Y)

 {

     int x=X;

     while(x)

     {

         int y=Y;

         while(y)

         {

             t[x][y]++;

             y-=lowbit(y);

         }

         x-=lowbit(x);

     }

 }

 int main()

 {

     freopen("hdoj5517.in","r",stdin);

     freopen("hdoj5517.out","w",stdout);

      int cas;

      scanf("%d",&cas);

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

      {

          int n,m;

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

          memset(t,,sizeof(t));

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

          {

              mx[i]=-oo; num[i]=;

          }

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

         {

             int x,y;

             scanf("%d%d",&x,&y);

             if(x>mx[y])

             {

                 mx[y]=x; num[y]=;

             }

             if(x==mx[y]) num[y]++;

         }

         for(int i=;i<N;i++) c[i].clear();

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

         {

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             c[z].push_back(node(x,y));

         }

         n=;

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

         {

             for(int j=;j<=(int)c[i].size()-;j++)

             {

                 a[++n].x=mx[i];

                 a[n].y=c[i][j].x;

                 a[n].z=c[i][j].y;

                 a[n].num=num[i];

             }

         }

         sort(a+,a+n+,cmp);

         int n1=n;

         n=;

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

          if(a[i].x==a[n].x&&a[i].y==a[n].y&&a[i].z==a[n].z) a[n].num+=a[i].num;

           else a[++n]=a[i];

         ll ans=;

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

         {

             int y=a[i].y;

             int z=a[i].z;

             if(!query(y,z)) ans+=a[i].num;

             add(y,z);

         }

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

     }

     return ;

 }