題目鏈接 Problem Description Given the finite multi-set A of n pairs of integers, an another finite multi-set B of m triples of integers, we define the pr ...
Problem Description Given the finite multi-set A of n pairs of integers, an another finite multi-set B of m triples of integers, we define the product of A and B as a multi-set
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). Input The input contains several test cases. The first line of the input is a single integer t (1≤t≤10) which is the number of test case. Then t test cases follow.
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
a1,b1,a2,b2,⋯,an,bn
which describe the multi-set A, where 1≤ai,bi≤105.
The third line contains 3×m nonnegative integers
c1,d1,e1,c2,d2,e3,⋯,cm,dm,em
corresponding to the m triples of integers in B, where 1≤ci,di≤103 and 1≤ei≤105. Output For each test case, you should output the size of set 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 m ，第二行輸入a1 b1 a2 b2......an bn,第三行輸入c1 d1 e1......cm dm em 現在定義C=A*B 即{<a,c,d>|<a,b>屬於A & <c,d,e>屬於B & b==e} 然後基於C有這樣一個運算TOP（C）={<a,c,d>|<a,c,d>屬於C & C中不存在<u,v,w>使得 u>=a,v>=c,w>=d,<u,v,w>!=<a,c,d> } 現在求 TOP(C)中有幾個元素？ 思路：
上面是從論壇上截圖下來的，我覺得優化的時候，只需要用第一條即可，即：對於二元組（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+5; int a1[N],cnt[N]; int c[1005][1005]; 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=0; int i=tr[x].c; while(i<1005) { int j=tr[x].d; while(j<1005) { ans+=c[i][j]; j+=lowbit(j); } i+=lowbit(i); } return ans; } void update(int x) { int i=tr[x].c; while(i>0) { int j=tr[x].d; while(j>0) { 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,-1,sizeof(a1)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); if(a1[b]<a){ a1[b]=a; cnt[b]=1; } else if(a1[b]==a) cnt[b]++; } int num=0; for(int i=1;i<=m;i++) { int c,d,e; scanf("%d%d%d",&c,&d,&e); if(a1[e]==-1) 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=0; int k=0; for(int i=1;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=1; 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=0; if(flag) ///防止 1 1 （1，1） （1，1，2） 這樣的數據(但是HDU上沒這樣的數據); for(int i=k;i>=0;i--) { if(!query(i)) ans+=(long long)tr[i].v; update(i); } printf("Case #%d: %lld\n",Case++,ans); } return 0; }
