HDU 4941 Magical Forest（map映射+二分查找）杭电多校训练赛第七场1007

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<map>
 6 using namespace std;
 7 #define maxn 100005
 8 struct node
 9 {
10     int x,y,c;
11 }mat[maxn];
12 map<int,int> hang,lie;
13 bool cmp(node a,node b)
14 {
15     if(a.x == b.x) return a.y < b.y;
16     return a.x < b.x;
17 }
18 int query(int k,int x,int y)
19 {
20     int l = 1,r = k,d = x,m;
21     while(l < r)
22     {
23         m = (l + r) >> 1;
24         if(d <= mat[m].x) r = m;
25         else l = m + 1;
26     }
27     int s1 = l;
28     if(mat[s1].x != x) return 0;   //没找到一个符合的x，说明没有这一行 
29     l = 1,r = k,d = x + 1;
30     while(l < r)
31     {
32         m = (l + r) >> 1;
33         if(d <= mat[m].x) r = m;
34         else l = m + 1;
35     }
36     int s2 = l;
37     if(mat[s2].x != x) s2--;
38     l = s1,r = s2;
39     while(l < r)
40     {
41         m = (l + r) / 2;
42         if(y <= mat[m].y) r = m;
43         else l = m + 1;
44     }
45     if(mat[l].y != y) return 0;   //没找到符合的y，说明这一行的这一列没有 
46     return mat[l].c;
47 }
48 int main()
49 {
50     int T,n,m,k,q,kase = 1;
51     scanf("%d",&T);
52     while(T--)
53     {
54         scanf("%d%d%d",&n,&m,&k);
55         hang.clear();
56         lie.clear();
57         for(int i = 1;i <= k;++i)
58         {
59             scanf("%d%d%d",&mat[i].x,&mat[i].y,&mat[i].c);
60             hang[mat[i].x] = mat[i].x;
61             lie[mat[i].y] = mat[i].y;
62         }
63         sort(mat+1,mat+k+1,cmp);
64         printf("Case #%d:\n",kase++);
65         scanf("%d",&q);
66         int op,a,b;
67         while(q--)
68         {
69             scanf("%d%d%d",&op,&a,&b);
70             if(op == 1)
71             {
72                 swap(hang[a],hang[b]);
73             }
74             else if(op == 2)
75             {
76                 swap(lie[a],lie[b]);
77             }
78             else if(op == 3)
79             {
80                 a = hang[a];
81                 b = lie[b];
82                 printf("%d\n",query(k,a,b));
83             }
84         }
85     }
86     return 0;
87 }        
88 /*
89 5
90 4 4 4dlsdfflsfls
91 1 1 1
92 2 4 4
93 3 2 2
94 4 4 3
95 */