1 #include
     
        2 #define MAXN 300  3 struct node  4 {  5     int big[MAXN<<2],small[MAXN<<2];  6 };  7 node tree[MAXN<<2];  8 int n,b;  9 inline int MAX(int x,int y) 10 { 11     return x>y?x:y; 12 } 13 inline int MIN(int x,int y) 14 { 15     return x>y?y:x; 16 } 17 void SubBuild(int t,int L,int R,int rt) 18 { 19     tree[t].big[rt]=0; 20     tree[t].small[rt]=MAXN; 21     if(L!=R) 22     { 23         int mid=(L+R)>>1; 24         SubBuild(t,L,mid,rt<<1); 25         SubBuild(t,mid+1,R,rt<<1|1); 26     } 27 } 28 void Build(int L,int R,int rt) 29 { 30     SubBuild(rt,1,n,1); 31     if(L!=R) 32     { 33         int mid=(L+R)>>1; 34         Build(L,mid,rt<<1); 35         Build(mid+1,R,rt<<1|1); 36     } 37 } 38 void SubUpdate(int t,int x,int val,int L,int R,int rt) 39 { 40     if(L==R) 41     { 42         tree[t].big[rt]=MAX(tree[t].big[rt],val); 43         tree[t].small[rt]=MIN(tree[t].small[rt],val); 44     } 45     else 46     { 47         int mid=(L+R)>>1; 48         if(x<=mid) 49             SubUpdate(t,x,val,L,mid,rt<<1); 50         else 51             SubUpdate(t,x,val,mid+1,R,rt<<1|1); 52         tree[t].big[rt]=MAX(tree[t].big[rt<<1],tree[t].big[rt<<1|1]); 53         tree[t].small[rt]=MIN(tree[t].small[rt<<1],tree[t].small[rt<<1|1]); 54     } 55 } 56 void Update(int x,int y,int val,int L,int R,int rt) 57 { 58     SubUpdate(rt,y,val,1,n,1); 59     if(L!=R) 60     { 61         int mid=(L+R)>>1; 62         if(x<=mid) 63             Update(x,y,val,L,mid,rt<<1); 64         else 65             Update(x,y,val,mid+1,R,rt<<1|1); 66     } 67 } 68 int SubQueryB(int t,int x,int y,int L,int R,int rt) 69 { 70     if(x<=L&&R<=y) 71         return tree[t].big[rt]; 72     int mid=(L+R)>>1,ans=0; 73     if(x<=mid) 74         ans=MAX(ans,SubQueryB(t,x,y,L,mid,rt<<1)); 75     if(y>mid) 76         ans=MAX(ans,SubQueryB(t,x,y,mid+1,R,rt<<1|1)); 77     return ans; 78 } 79 int QueryB(int x1,int x2,int y1,int y2,int L,int R,int rt) 80 { 81     if(x1<=L&&R<=x2) 82         return SubQueryB(rt,y1,y2,1,n,1); 83     int mid=(L+R)>>1,ans=0; 84     if(x1<=mid) 85         ans=MAX(ans,QueryB(x1,x2,y1,y2,L,mid,rt<<1)); 86     if(x2>mid) 87         ans=MAX(ans,QueryB(x1,x2,y1,y2,mid+1,R,rt<<1|1)); 88     return ans; 89 } 90 int SubQueryS(int t,int x,int y,int L,int R,int rt) 91 { 92     if(x<=L&&R<=y) 93         return tree[t].small[rt]; 94     int mid=(L+R)>>1,ans=MAXN; 95     if(x<=mid) 96         ans=MIN(ans,SubQueryS(t,x,y,L,mid,rt<<1)); 97     if(y>mid) 98         ans=MIN(ans,SubQueryS(t,x,y,mid+1,R,rt<<1|1)); 99     return ans;100 }101 int QueryS(int x1,int x2,int y1,int y2,int L,int R,int rt)102 {103     if(x1<=L&&R<=x2)104         return SubQueryS(rt,y1,y2,1,n,1);105     int mid=(L+R)>>1,ans=MAXN;106     if(x1<=mid)107         ans=MIN(ans,QueryS(x1,x2,y1,y2,L,mid,rt<<1));108     if(x2>mid)109         ans=MIN(ans,QueryS(x1,x2,y1,y2,mid+1,R,rt<<1|1));110     return ans;111 }112 int main()113 {114     int q,x,i,j,big,small;115     while(~scanf("%d%d%d",&n,&b,&q))116     {117         Build(1,n,1);118         for(i=1;i<=n;i++)119         {120             for(j=1;j<=n;j++)121             {122                 scanf("%d",&x);123                 Update(i,j,x,1,n,1);124             }125         }126         while(q--)127         {128             scanf("%d%d",&i,&j);129             big=QueryB(i,i+b-1,j,j+b-1,1,n,1);130             small=QueryS(i,i+b-1,j,j+b-1,1,n,1);131             printf("%d\n",big-small);132         }133     }134     return 0;135 }