C=A∗B={⟨a,c,d⟩∣⟨a,b⟩∈A, ⟨c,d,e⟩∈B and b=e}
For each ⟨a,b,c⟩∈C, its BETTER set is defined as
BETTERC(⟨a,b,c⟩)={⟨u,v,w⟩∈C∣⟨u,v,w⟩≠⟨a,b,c⟩, u≥a, v≥b, w≥c}
As a \textbf{multi-set} of triples, we define the TOP subset (as a multi-set as well) of C, denoted by TOP(C), as
TOP(C)={⟨a,b,c⟩∈C∣BETTERC(⟨a,b,c⟩)=∅}
You need to compute the size of TOP(C).
Each test case contains three lines. The first line contains two integers n (1≤n≤105) and m (1≤m≤105) corresponding to the size of A and B respectively.
The second line contains 2×n nonnegative integers
which describe the multi-set A, where 1≤ai,bi≤105.
The third line contains 3×m nonnegative integers
corresponding to the m triples of integers in B, where 1≤ci,di≤103 and 1≤ei≤105.
上面是从论坛上截图下来的，我觉得优化的时候，只需要用第一条即可，即：对于二元组（a，b） ，b相同的话只有最大的a值有效，所以对相同的b记录一下最大值的个数
第二条不一定能优化，在极端的数据上，一点都不会优化。经过第一条的优化后，C的大小为1e5,然后用二维树状数组处理O(n)=1e5*log2(1000)*log2(1000)=1e7
实际的数据肯定会比这个复杂度要小。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+;
int a1[N],cnt[N];
int c[][]; struct Node
{
int a,c,d;
int v;
}tr[N];
int cmp(const Node s1,const Node s2)
{
if(s1.a!=s2.a) return s1.a<s2.a;
if(s1.c!=s2.c) return s1.c<s2.c;
return s1.d<s2.d;
}
int lowbit(int x)
{
return x&(-x);
}
int query(int x)
{
int ans=;
int i=tr[x].c;
while(i<)
{
int j=tr[x].d;
while(j<)
{
ans+=c[i][j];
j+=lowbit(j);
}
i+=lowbit(i);
}
return ans;
}
void update(int x)
{
int i=tr[x].c;
while(i>)
{
int j=tr[x].d;
while(j>)
{
c[i][j]++;
j-=lowbit(j);
}
i-=lowbit(i);
}
}
int main()
{
///cout << "Hello world!" << endl;
int t,Case=1;
cin>>t;
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(a1,-,sizeof(a1));
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(a1[b]<a){
a1[b]=a;
cnt[b]=;
}
else if(a1[b]==a) cnt[b]++;
}
int num=;
for(int i=;i<=m;i++)
{
int c,d,e;
scanf("%d%d%d",&c,&d,&e);
if(a1[e]==-) continue;
tr[num].a=a1[e];
tr[num].c=c;
tr[num].d=d;
tr[num++].v=cnt[e];
}
sort(tr,tr+num,cmp);
int flag=;
int k=;
for(int i=;i<num;i++)
{
if(tr[i].a==tr[k].a&&tr[i].c==tr[k].c&&tr[i].d==tr[k].d)
{
tr[k].v+=tr[i].v;
}
else{
k++;
flag=;
tr[k].a=tr[i].a;
tr[k].c=tr[i].c;
tr[k].d=tr[i].d;
tr[k].v=tr[i].v;
}
}
long long ans=;
if(flag) ///防止 1 1 （1，1） （1，1，2） 这样的数据(但是HDU上没这样的数据);
for(int i=k;i>=;i--)
{
if(!query(i)) ans+=(long long)tr[i].v;
update(i);
}
printf("Case #%d: %lld\n",Case++,ans);
}
return ;
}