题目链接:2015 ACM-ICPC 沈阳区域赛 I:Triple
Description
给定一个N个元素的二元组集合A和M个元素的三元组集合B。
定义：C=A∗B={⟨a,c,d⟩∣⟨a,b⟩∈A, ⟨c,d,e⟩∈B and b=e}
BETTERC(⟨a,b,c⟩)={⟨u,v,w⟩∈C∣⟨u,v,w⟩≠⟨a,b,c⟩, u≥a, v≥b, w≥c}，
TOP(C)={⟨a,b,c⟩∈C∣BETTERC(⟨a,b,c⟩)=∅}
求TOP(C)集合的大小
1≤n,m,ai,bi,ei≤10^5, 1≤ci,di≤10^3
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
Solution
有可能最优且本质不同的三元组C只有不超过M个,所以先处理二元组集合A，对于每个元素(a,b),我们只保留b相同中的a最大的，然后直接预处理出可能的TOP(C)集合。
注意到1≤ci,di≤10^3,这提示我们可以先按a排序,然后对c,d用二维树状数组统计答案。
%%%pps
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define Judge
#define Online
#define maxm 1100
#define maxn 100100
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
#define S 1000000
int wpos,len,pos;char wbuf[S],buf[S];
FastIO(){wpos=0,len=0,pos=0;}
inline char gc(){
if (pos==len) pos=0,len=fread(buf,1,S,in);
if (pos==len) return 0; return buf[pos++];
}
inline void wchar(int x) {
if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
wbuf[wpos++]=x;
}
inline void put(const char*s) {for(; *s; ) wchar(*s++);}
~FastIO() {
if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
}
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,m,ba[maxn],cntba[maxn],tr[maxm][maxm],cnt,cnt1,ans;
struct node {
int a,c,d,cnt;node():a(0),c(0),d(0),cnt(0){}
node(int _a,int _c,int _d,int _cnt):a(_a),c(_c),d(_d),cnt(_cnt){}
inline int operator <(const node&oth)const{
return a!=oth.a?a>oth.a:c!=oth.c?c>oth.c:d>oth.d;
}
inline int operator ==(const node&oth)const{
return a==oth.a&&c==oth.c&&d==oth.d;
}
} trpC[maxn],tpc[maxn];
inline int query(int x,int y) {
for (int i=x; i; i-=lowbit(i)) for (int j=y; j; j-=lowbit(j))
if(tr[i][j]) return 1; return 0;
}
inline void update(int x,int y){
for (int i=x; i<maxm; i+=lowbit(i)) for (int j=y; j<maxm; j+=lowbit(j))
if (!tr[i][j]) tr[i][j]=1;
}
int main(int argv,char*argc[]){
int T;read(T);
for (int a,b,c,d,e,cas=1; cas<=T; ++cas){
read(n),read(m),cnt=cnt1=0;
memset(ba,0,sizeof ba),memset(cntba,0,sizeof cntba);
for (int i=1; i<=n; ++i){read(a),read(b);
if (ba[b]<a) ba[b]=a,cntba[b]=1;
else if (ba[b]==a) cntba[b]++;
}
for (int i=1; i<=m; ++i){
read(c),read(d),read(e);
if (ba[e]) trpC[++cnt]=node(ba[e],c,d,cntba[e]);
}
sort(trpC+1,trpC+cnt+1);tpc[1]=trpC[1];
for (int i=1; i<=cnt; ++i)
if (tpc[cnt1]==trpC[i]) tpc[cnt1].cnt+=trpC[i].cnt;
else tpc[++cnt1]=trpC[i];
memset(tr,0,sizeof tr);ans=0;
for (int i=1; i<=cnt1; ++i) {
if (!query(1001-tpc[i].c,1001-tpc[i].d)) ans+=tpc[i].cnt;
update(1001-tpc[i].c,1001-tpc[i].d);
}
printf("Case #%d: %d\n",cas,ans);
}
return 0;
}
