传送门

描述

给出一个N*N （N<=250）的方阵，以及K（<=100000）个询问。每次询问如下：以（Xi,Yi）为左上角，边长为B的子方阵中，最大值和最小值的差是多少？
注意对于所有的询问，B都是一个定值。

输入

第一行N，B（<=N），K。含义如上。
接下来N行N列的一个矩阵，每个数<=250。
接下来K行表示询问，每行两个数Xi, Yi 表示询问的方阵的左上角。

输出

一行一个正整数，含义如上。

样例

输入
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2

输出
5

思路

二维ST表。用st[i][j][k]表示第i行区间[j,j+(1<<k)]的最值。

O(n^2lgn)预处理，O(n)查询

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long int using namespace std; const int MAX=0x7fffffff; const int MIN=-0x7fffffff; const int INF=0x3f3f3f3f; const int Mod=1e9+7; const int maxn=300; int n,b,k; int a[maxn][maxn],st1[maxn][maxn][30],st2[maxn][maxn][30];; void Init(){
            for(int i=1;i<=n;i++)         for(int k=1;(1<
              
               <=n;k++) for(int j=1;j+(1<
               
                <=n;j++){ st1[i][j][k]=max(st1[i][j][k-1],st1[i][j+(1<

转载地址：https://blog.csdn.net/cpongo3/article/details/89334359 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

传送门

描述

输入

输出

样例

思路

Code

发表评论

最新留言

关于作者

推荐文章