HDU_5517_TripleHDU_5517_Triple

Triple

Time Limit: 12000/6000
MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1004    Accepted Submission(s): 356

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

 

 

Source

2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

 

  • 集合凸点
  • 困难在于是否快速判定比当下老三维数据(ai,ci,di)更可怜之接触是否在
  • 第一会无克针对原数据做一样不好缩减也?
  • 扣押数据范围发现a,b,e的限制一致,c,d的限量一致,而c,d的限定只出1e3,是好领之
  • 那我们得以先行对有效点集P做相同次于排序,从那个到小排,优先度分别是a,c,d,那么我们到底对第一维a的数码开展同样软罗,剩下的即是对于c和d这有限维数据的判定
  • 每当一维数据中我们可以用线段树要树状数组的艺术对于个别数量范围的数目开展RMQ操作,快速搜索来区间内max,min,sum。。。。
  • 那么我们这边的竟一维RMQ之一个扩展
  • 假定我们得寻找有比目前结点大的接触之个数就可将书解决
  • 那么这里就是是一个二维数据的RMQ问题,询问区间内点点的多少
  • 可透过二维树状数组来促成
  • 这边用注意的少数是,普通二维树状数组在update的上是起小到充分保安自[0][0]点至[x][y]接触完矩阵的多寡,因此update(x,y)应该分别对大于x和y的坐标点进行翻新,意思是update的(x,y)这个点之音于过量等于当前矩阵所保障的音信享有影响作用,但对小的点所维护的消息并未效果
  • 立道题却和常见思想完全相反,update的点(x,y)对于比较这个点小之点具有效用,因此更新方向及原始方向正好相反,对应之quary过程为是相反的
  • 终极还要对点集去又,记录对应点出现次数

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 struct node{
25     int a, c, d, cnt;
26     bool operator < (const node &r)const{
27         if(a!=r.a) return a>r.a;
28         else if(c!=r.c) return c>r.c;
29         else return d>r.d;
30     }
31     bool operator == (const node &r)const{
32         return (a==r.a)&&(c==r.c)&&(d==r.d);
33     }
34 };
35 node e[maxn];
36 int T, n, m, u, v, w, cnt, tot;
37 int a[maxn], c[maxn], d[1000+5][1000+5];
38 int lowbit(int x){
39     return x&(-x);
40 }
41 void update(int x, int y, int z){
42     for(int i=x;i>0;i-=lowbit(i))
43         for(int j=y;j>0;j-=lowbit(j))
44             d[i][j]+=z;
45 }
46 int quary(int x, int y){
47     int res=0;
48     for(int i=x;i<=1e3;i+=lowbit(i))
49         for(int j=y;j<=1e3;j+=lowbit(j))
50             res+=d[i][j];
51     return res;
52 }
53 int main(){
54     // freopen("in.txt","r",stdin);
55     // freopen("out.txt","w",stdout);
56     while(~scanf("%d",&T)){
57         for(int kase=1;kase<=T;kase++){
58             cnt=0;
59             tot=0;
60             memset(a,0,sizeof(a));
61             memset(c,0,sizeof(c));
62             memset(d,0,sizeof(d));
63             scanf("%d %d",&n,&m);
64             for(int i=1;i<=n;i++){
65                 scanf("%d %d",&u,&v);
66                 if(a[v]<u)
67                     a[v]=u, c[v]=1;
68                 else if(a[v]==u)
69                     c[v]++;
70             }
71             for(int i=1;i<=m;i++){
72                 scanf("%d %d %d",&u,&v,&w);
73                 if(a[w])
74                     e[cnt++]=(node){a[w],u,v,c[w]};
75             }
76             sort(e,e+cnt);
77             for(int i=1;i<cnt;i++)
78                 if(e[tot]==e[i])
79                     e[tot].cnt+=e[i].cnt;
80                 else
81                     e[++tot]=e[i];
82             LL ans=0LL;
83             for(int i=0;i<=tot;i++){
84                 if(!quary(e[i].c,e[i].d))
85                     ans+=e[i].cnt;
86                 update(e[i].c,e[i].d,1);
87             }
88             printf("Case #%d: %lld\n",kase,ans);
89         }
90     }
91     return 0;
92 }

 

 

 

Triple

Time Limit: 12000/6000
MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1004    Accepted Submission(s): 356

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

 

 

Source

2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

 

  • 集凸点
  • 难点在是否快速判定比目前叔维数据(ai,ci,di)更不行之触发是否留存
  • 首先会无克对老数据做同样涂鸦缩减为?
  • 看数量范围发现a,b,e的限制一致,c,d的限量一致,而c,d的限量才生1e3,是足以承受之
  • 那我们可优先对有效点集P做一样破排序,从杀及小排,优先度分别是a,c,d,那么我们到底对第一维a的数目进行相同潮罗,剩下的虽是对此c和d这半维数据的判定
  • 当一维数量中我们好就此线段树要树状数组的方法对于片数量范围之数码开展RMQ操作,快速搜索有区间内max,min,sum。。。。
  • 这就是说我们这边的终究一维RMQ的一个扩展
  • 倘我们好查找来比较当下结点大的触及的个数就可以拿书解决
  • 这就是说这里虽是一个二维数据的RMQ问题,询问区间内点点的多寡
  • 足由此二维树状数组来促成
  • 这边要留意的一点是,普通二维树状数组在update的早晚是自从小至不可开交保安自[0][0]点至[x][y]接触完矩阵的数据,因此update(x,y)应该分别对此大于x和y的坐标点进行更新,意思是update的(x,y)这个点的信于过量等于当前矩阵所保障的音信有影响作用,但对小之点所维护的消息并未效益
  • 当时道题却和普通思想完全相反,update的点(x,y)对于比较是点多少的点具有效用,因此更新方向以及原有方向正好相反,对应的quary过程吧是倒转的
  • 说到底还要针对点集去还,记录对应点出现次数

 

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 struct node{
25     int a, c, d, cnt;
26     bool operator < (const node &r)const{
27         if(a!=r.a) return a>r.a;
28         else if(c!=r.c) return c>r.c;
29         else return d>r.d;
30     }
31     bool operator == (const node &r)const{
32         return (a==r.a)&&(c==r.c)&&(d==r.d);
33     }
34 };
35 node e[maxn];
36 int T, n, m, u, v, w, cnt, tot;
37 int a[maxn], c[maxn], d[1000+5][1000+5];
38 int lowbit(int x){
39     return x&(-x);
40 }
41 void update(int x, int y, int z){
42     for(int i=x;i>0;i-=lowbit(i))
43         for(int j=y;j>0;j-=lowbit(j))
44             d[i][j]+=z;
45 }
46 int quary(int x, int y){
47     int res=0;
48     for(int i=x;i<=1e3;i+=lowbit(i))
49         for(int j=y;j<=1e3;j+=lowbit(j))
50             res+=d[i][j];
51     return res;
52 }
53 int main(){
54     // freopen("in.txt","r",stdin);
55     // freopen("out.txt","w",stdout);
56     while(~scanf("%d",&T)){
57         for(int kase=1;kase<=T;kase++){
58             cnt=0;
59             tot=0;
60             memset(a,0,sizeof(a));
61             memset(c,0,sizeof(c));
62             memset(d,0,sizeof(d));
63             scanf("%d %d",&n,&m);
64             for(int i=1;i<=n;i++){
65                 scanf("%d %d",&u,&v);
66                 if(a[v]<u)
67                     a[v]=u, c[v]=1;
68                 else if(a[v]==u)
69                     c[v]++;
70             }
71             for(int i=1;i<=m;i++){
72                 scanf("%d %d %d",&u,&v,&w);
73                 if(a[w])
74                     e[cnt++]=(node){a[w],u,v,c[w]};
75             }
76             sort(e,e+cnt);
77             for(int i=1;i<cnt;i++)
78                 if(e[tot]==e[i])
79                     e[tot].cnt+=e[i].cnt;
80                 else
81                     e[++tot]=e[i];
82             LL ans=0LL;
83             for(int i=0;i<=tot;i++){
84                 if(!quary(e[i].c,e[i].d))
85                     ans+=e[i].cnt;
86                 update(e[i].c,e[i].d,1);
87             }
88             printf("Case #%d: %lld\n",kase,ans);
89         }
90     }
91     return 0;
92 }

 

 

 

相关文章