作者：永不言败LM | 来源：互联网 | 2023-05-24 13:56
Giventhefinitemulti-setAAofnnpairsofintegers,ananotherfinitemulti-setBBofmmtriplesofintege
Given the finite multi-set AA of nn pairs of integers, an another finite multi-set BBof mm triples of integers, we define the product of AA and BB as a multi-set
C&＃61;A∗B&＃61;{⟨a,c,d⟩∣⟨a,b⟩∈A, ⟨c,d,e⟩∈B and b&＃61;e}C&＃61;A∗B&＃61;{⟨a,c,d⟩∣⟨a,b⟩∈A, ⟨c,d,e⟩∈B and b&＃61;e}
For each ⟨a,b,c⟩∈C⟨a,b,c⟩∈C, its BETTER set is defined as
BETTERC(⟨a,b,c⟩)&＃61;{⟨u,v,w⟩∈C∣⟨u,v,w⟩≠⟨a,b,c⟩, u≥a, v≥b, w≥c}BETTERC(⟨a,b,c⟩)&＃61;{⟨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 CC, denoted by TOP(C)TOP(C), as
TOP(C)&＃61;{⟨a,b,c⟩∈C∣BETTERC(⟨a,b,c⟩)&＃61;∅}TOP(C)&＃61;{⟨a,b,c⟩∈C∣BETTERC(⟨a,b,c⟩)&＃61;∅}
You need to compute the size of TOP(C)TOP(C).
Input
The input contains several test cases. The first line of the input is a single integer t (1≤t≤10)t (1≤t≤10) which is the number of test case. Then tt test cases follow.
Each test case contains three lines. The first line contains two integers n (1≤n≤105)n (1≤n≤105) and m (1≤m≤105)m (1≤m≤105) corresponding to the size of AA and BBrespectively.
The second line contains 2×n2×n nonnegative integers
a1,b1,a2,b2,⋯,an,bna1,b1,a2,b2,⋯,an,bn
which describe the multi-set AA, where 1≤ai,bi≤1051≤ai,bi≤105.
The third line contains 3×m3×m nonnegative integers
c1,d1,e1,c2,d2,e3,⋯,cm,dm,emc1,d1,e1,c2,d2,e3,⋯,cm,dm,em
corresponding to the mm triples of integers in BB, where 1≤ci,di≤1031≤ci,di≤103 and 1≤ei≤1051≤ei≤105.
Output
For each test case, you should output the size of set TOP(C)TOP(C).
Sample Input
2
5 9
1 1 2 2 3 3 3 3 4 2
1 4 1 2 2 1 4 1 1 1 3 2 3 2 2 4 1 2 2 4 3 3 2 3 4 1 3
3 4
2 7 2 7 2 7
1 4 7 2 3 7 3 2 7 4 1 7
Sample Output
Case #1: 5
Case #2: 12
题意是给你n个二元组a,b m个三元组c,d,e&＃xff0c;让你找B&＃61;&＃61;e的组成集合c(a,c,d)问这个集合中 a,c,d不全部大于等于其他的有几个。
要是就按b&＃61;&＃61;e的全加进去&＃xff0c;然后在二重循环比较肯定要超时的。
所以我们可以先处理a,b b相等时就选大的a,因为小的a最后肯定要被去掉的。
然后我们就按是否be相等建好集合。按a排序从小到大&＃xff0c;从后往前找。
这样后面的a肯定大于前面的a 要是后面的c,d也大于等于前面的&＃xff0c;那就肯定不符合了。所以就想到了二维树状数组。
#include
#include
#include
#include
using namespace std;
const int maxn&＃61;100005;
int a[100005];
int num[100005];
int c[1005][1005];
struct node
{int a,c,d;int num;
}y[maxn];
int cmp(node q,node w)
{if(q.a!&＃61;w.a)return q.a}
int lowbit(int i)
{return i&(-i);
}
int query(int x)
{int sum&＃61;0;int i&＃61;y[x].c;while(i<1004){int j&＃61;y[x].d;while(j<1004){sum&＃43;&＃61;c[i][j];j&＃43;&＃61;lowbit(j);//cout<}
void update(int x)
{int i&＃61;y[x].c;while(i>0){int j&＃61;y[x].d;while(j>0){c[i][j]&＃43;&＃43;;j-&＃61;lowbit(j);}i-&＃61;lowbit(i);}
}
int main()
{int t;cin>>t;int cc&＃61;1;while(t--){int n,m;memset(c,0,sizeof(c));memset(a,-1,sizeof(a));//memset(num,0,sizeof(num));scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int a1,b;scanf("%d%d",&a1,&b);if(a[b]&＃61;1;i--){if(!query(i))ans&＃43;&＃61;(long long) y[i].num;update(i);}printf("Case #%d: %d\n",cc&＃43;&＃43;,ans);}return 0;
}
京公网安备 11010802041100号