题意是给了 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=100005; 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[1005][1005]; int Nc,Nd,numofC; void init() { numofC=Nc=Nd=0; memset(B,0,sizeof(B)); memset(nu,0,sizeof(nu)); memset(C,0,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=0; for(int i=c; i>0; i-=lowbit(i)) for(int j=d; j>0; j-=lowbit(j)) ans+=C[i][j]; return ans; } int main() { int cas; scanf("%d",&cas); for(int cc=1; cc<=cas; cc++) { int n,m; scanf("%d%d",&n,&m); init(); for(int i=0; i<n; i++) { int a,b; scanf("%d%d",&a,&b); if(B[b]<a){ B[b]=a; nu[b]=1;} else if(B[b]==a) nu[b]++; } for(int i=0; i<m; i++) { int c,d,e; scanf("%d%d%d",&c,&d,&e); if(nu[e]>0) { 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=1; for(int i=1; i<numofC; i++) if(P[i]==P[ge-1])P[ge-1].nu+=P[i].nu; else P[ge++]=P[i]; numofC=ge; int ans=0; ge=0; for(int i=numofC-1; i>=0; i--) { point t=P[i]; int s2=sum(t.c-1,Nd); int s3=sum(Nc,t.d-1); int s4=sum(t.c-1,t.d-1); if(ge-s2-s3+s4 == 0){ ans+=t.nu; } ge++; add(t.c,t.d,1); } printf("Case #%d: %d ",cc,ans); } return 0; }