题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4941

题目大意：给你10^5个点。每一个点有一个数值。点的xy坐标是0~10^9。点存在于矩阵中。然后给出10^5个操作。1代表交换行。2代表交换列，3代表查询坐标为xy点的数值。

数据量非常大........ 所以一直没有思路

后来赛后看了题解是先用离散化然后存在线性map里面。

用hx，hy来存放离散化后的点的坐标，用linkx，linky来存放点离散化之后的点的坐标的行与列。

还是对于STL里面的基础运用掌握不牢。

#include

#include

#include

#include

using namespace std;

#define maxn 100010

struct node {

     int u,v,w;

} point[maxn];

//其基本的原理是用一个线性的map存放。

//map里面的是map一个特征。最后其所占的空间还是maxn这么多

map p_w[maxn];

map hx,hy;

bool  cmpx(node A,node B)

{

     return A.u

}

bool cmpy(node A,node B)

{

     return A.v

}

int main ()

{

     int W;

     scanf("%d",&W);

     for(int w=1; w<=W; w++) {

          ///初始化

          for(int i=0; i

          hx.clear();

          hy.clear();

          int N,M,K;

          scanf("%d%d%d",&N,&M,&K);

          for(int i=0; i

               scanf("%d%d%d",&point[i].u,&point[i].v,&point[i].w);

          int tx=1;

          sort(point,point+K,cmpx);

          for(int i=0; i

          int ty=1;

          sort(point,point+K,cmpy);

          for(int i=0; i

               if(!hy[point[i].v]) hy[point[i].v]=ty++;

               p_w[hx[point[i].u]][hy[point[i].v]]=point[i].w;

          }

          int linkx[maxn];

          int linky[maxn];

          for(int i=0; i

          printf("Case #%d:\n",w);

          int T;

          int Q,A,B;

          scanf("%d",&T);

          while(T--) {

               scanf("%d%d%d",&Q,&A,&B);

               if(Q==1) {

                    int tem=linkx[hx[A]];

                    linkx[hx[A]]=linkx[hx[B]];

                    linkx[hx[B]]=tem;

               }

               if(Q==2) {

                    int tem=linky[hy[A]];

                    linky[hy[A]]=linky[hy[B]];

                    linky[hy[B]]=tem;

               }

               if(Q==3)

                    printf("%d\n",p_w[linkx[hx[A]]][linky[hy[B]]]);

          }

     }

}

查看原文