最近，亮亮和小W都对苹果很感兴趣！在研究了“最大苹果矩阵”和“给苹果树施肥”的问题后，他们又遇到了一个新的问题：
有一块长n米、宽m米的地，现在小W把地划分成边长1米的小正方形块，共n*m个块。每个块中可能种有一棵苹果树，或放有一个iPhone，也可以什么也没有。然而，亮亮拥有一种超能力，可以将2个宽1米、长度相同的矩形块在空间中直接交换。
亮亮经常对着农场施展超能力，为了不把自己搞晕，他每次总是选择两整行（长度均为m米）或两整列（长度均为n米）进行交换。小W对此十分恼火——当他想拿iPhone打游戏时，却莫名其妙地撞在了苹果树上。小W要求你写一个程序，帮助他确定某一正方形块中放了什么东西。
输入包含多组数据，请处理到文件结束。
每组数据，第一行2个整数n、m，表示地的尺寸。
之后n行，每行m个英文字母，大写的T表示这里种有苹果树，小写的i表示这里放有iPhone，其他字符表示这里什么也没有。
之后1行，一个整数Q，表示小W询问的次数。
之后Q行，包含3个整数，可能有以下情况：
1 i1 j1 表示小W想知道第i1行第j1列的方块中有什么东西。
2 i1 i2 表示亮亮交换了第i1行与第i2行。
3 j1 j2 表示亮亮交换了第j1列与第j2列。
对于100%的数据，有1<=n*m<=106，1<=Q<=105，1<=i1, i2<=n，1<=j1, j2<=m。
对于每组数据，输出以一行“Case #x:”开头，x表示数据的编号，从1开始。
对于小W的每次格式为“1 i j”的询问，输出一行。若方块中是苹果树，输出"Tree"。若方块中是iPhone，输出“Phone”。若方块中什么也没有，输出“Empty”。
--正文
虽然是区间修改，求1点，不过由于每次只是交换两行或两列，并不需要什么树状数组。
考虑一下，每次交换i1和i2行的时候
实际上就是原来的i1行变成了i2行(交换列同理)
所以只需要通过建立映射(大概吧，也不知道怎么形容)即可
每次交换的时候，改变一下映射值
#include <stdio.h> int main(){ int m,n; int total = 0; while (scanf("%d %d",&n,&m) != EOF) { total ++; printf("Case #%d:\n",total); char field[n+1][m+1]; int nown[n+1],nowm[m+1]; int i,j; for (i=1;i<=m;i++) nowm[i] = i; for (i=1;i<=n;i++){ char row[1000001]; nown[i] = i; scanf("%s",row); for (j=1;j<=m;j++){ field[i][j] = row[j-1]; } } int q; scanf("%d",&q); for (i=1;i<=q;i++){ int order,i1,i2; scanf("%d %d %d",&order,&i1,&i2); if (order == 1){ char now = field[nown[i1]][nowm[i2]]; if (now == ‘T‘){ printf("Tree\n"); } else if (now == ‘i‘){ printf("Phone\n"); } else printf("Empty\n"); } if (order == 2){ int temp = nown[i1]; nown[i1] = nown[i2]; nown[i2] = temp; } if (order == 3){ int temp = nowm[i1]; nowm[i1] = nowm[i2]; nowm[i2] = temp; } } } return 0; }
原文：http://www.cnblogs.com/ToTOrz/p/6057659.html