【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，用二维数组维护，前缀和改成后缀和即可

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

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second 
 19 #define MP make_pair
 20 #define N  110000
 21 #define M  1100
 22 #define MOD 2147493647
 23 #define eps 1e-8 
 24 #define pi acos(-1)
 25 #define oo 1100000000
 26 
 27 struct node
 28 {
 29     int x,y;
 30     node() {}
 31     node(int x,int y):x(x),y(y) {}
 32 };
 33 vector<node>c[N];
 34 
 35 struct arr
 36 {
 37     int x,y,z,num;
 38 }a[N];
 39 
 40 ll t[M][M];
 41 int mx[N],num[N];
 42 
 43 
 44 bool cmp(arr a,arr b)
 45 {
 46     if(a.x!=b.x) return a.x>b.x;
 47     if(a.y!=b.y) return a.y>b.y;
 48     return a.z>b.z;
 49 }
 50 
 51 int lowbit(int x)
 52 {
 53     return x&(-x);
 54 }
 55 
 56 ll query(int X,int Y)
 57 {
 58     ll ans=0;
 59     int x=X;
 60     while(x<=M-1)
 61     {
 62         int y=Y;
 63         while(y<=M-1)
 64         {
 65             ans+=t[x][y];
 66             y+=lowbit(y);
 67         }
 68         x+=lowbit(x);
 69     }
 70     return ans;
 71 }
 72 
 73 void add(int X,int Y)
 74 {
 75     int x=X;
 76     while(x)
 77     {
 78         int y=Y;
 79         while(y)
 80         {
 81             t[x][y]++;
 82             y-=lowbit(y);
 83         }
 84         x-=lowbit(x);
 85     }
 86 }
 87 
 88 int main()
 89 { 
 90     freopen("hdoj5517.in","r",stdin);
 91     freopen("hdoj5517.out","w",stdout);
 92      int cas;
 93      scanf("%d",&cas);
 94      for(int v=1;v<=cas;v++)
 95      {
 96          int n,m;
 97          scanf("%d%d",&n,&m);
 98          memset(t,0,sizeof(t));
 99          for(int i=1;i<N;i++) 
100          {
101              mx[i]=-oo; num[i]=0;
102          }
103          for(int i=1;i<=n;i++)
104         {
105             int x,y;
106             scanf("%d%d",&x,&y);
107             if(x>mx[y])
108             {
109                 mx[y]=x; num[y]=0;
110             }
111             if(x==mx[y]) num[y]++;
112         }
113     
114         for(int i=1;i<N;i++) c[i].clear();
115         for(int i=1;i<=m;i++)
116         {
117             int x,y,z;
118             scanf("%d%d%d",&x,&y,&z);
119             c[z].push_back(node(x,y));
120         }    
121         n=0;
122         for(int i=1;i<N;i++)
123         {
124             for(int j=0;j<=(int)c[i].size()-1;j++)
125             {
126                 a[++n].x=mx[i];
127                 a[n].y=c[i][j].x;
128                 a[n].z=c[i][j].y;
129                 a[n].num=num[i];
130             }
131         }
132         sort(a+1,a+n+1,cmp);
133     
134         int n1=n;
135         n=0;
136         for(int i=1;i<=n1;i++)
137          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;
138           else a[++n]=a[i];    
139         ll ans=0;
140         for(int i=1;i<=n;i++)
141         {
142             int y=a[i].y;
143             int z=a[i].z;
144             if(!query(y,z)) ans+=a[i].num;
145             add(y,z);
146         }
147         printf("Case #%d: %I64d
",v,ans);
148     }
149     return 0;
150 }
151