有一个n*m的地毯，a_ij表示地毯每格的元素，b_ij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。

先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下循环节长度用map记录，取出现次数为m并且循环节长度最小的；这样就得到了最小的循环节子矩阵。然后问题就变成了求一个p*q的子矩阵最大值的最小值，可以参考这个题 Fake Maxpooling （求得是k*k子矩阵的最大值的和）稍加修改变成求p*q子矩阵的最大值的最小值就好了。这里用到单调队列，先横着算一下每个长度为p的区间的最大值记录下来，然后再把记录下来的数组竖着同样算一下长度为q的区间，将每次求到的最大值取最小值。

 

ps：谨记像这种横着求一遍竖着求一遍的一定不能求第二遍的时候直接copy第一遍的代码改，会把自己坑死的！！！不要手懒！！！

  1 #include<bits/stdc++.h>

  2 #define ll long long

  3 using namespace std;

  4

  5 const int maxn=1e6+10;

  6 int nt1[maxn];

  7 int nt2[maxn];

  8 string s[maxn];

  9 unordered_map<int,int> mp;

 10 deque<int> dq;

 11 int val[maxn],v[maxn];

 12

 13 void getnt1(string s)

 14 {

 15     int i=0,j=-1;

 16     nt1[0]=-1;

 17     while(i<s.size()){

 18         if(j==-1||s[i]==s[j]) i++,j++,nt1[i]=j;

 19         else j=nt1[j];

 20     }

 21 }

 22

 23 void getnt2(string s)

 24 {

 25     int i=0,j=-1;

 26     nt2[0]=-1;

 27     while(i<s.size()){

 28         if(j==-1||s[i]==s[j]) i++,j++,nt2[i]=j;

 29         else j=nt2[j];

 30     }

 31 }

 32

 33 int main()

 34 {

 35     ios::sync_with_stdio(false);

 36     cin.tie(0);

 37     cout.tie(0);

 38

 39     int n,m;

 40     cin>>n>>m;

 41     for(int i=0;i<n;i++) cin>>s[i];

 42     for(int i=0;i<n;i++){

 43         for(int j=0;j<m;j++){

 44             cin>>v[i*m+j];

 45         }

 46     }

 47

 48     int pp=m,qq=n;

 49     for(int i=0;i<n;i++){

 50         getnt1(s[i]);

 51         int p=nt1[m];

 52         while(p!=-1){

 53             mp[m-p]++;

 54             if(mp[m-p]==n) pp=min(pp,m-p);

 55             p=nt1[p];

 56         }

 57     }

 58     mp.clear();

 59     for(int i=0;i<m;i++){

 60         string t;

 61         for(int j=0;j<n;j++){

 62             t+=s[j][i];

 63         }

 64         getnt2(t);

 65         int p=nt2[n];

 66         while(p!=-1){

 67             mp[n-p]++;

 68             if(mp[n-p]==m) qq=min(qq,n-p);

 69             p=nt2[p];

 70         }

 71     }

 72

 73     int ans=1e9;

 74     for(int i=0;i<n;i++){

 75         while(dq.size()) dq.pop_back();

 76         for(int j=0;j<pp-1;j++){

 77             while(dq.size()&&v[i*m+dq.back()]<=v[i*m+j]) dq.pop_back();

 78             dq.push_back(j);

 79         }

 80         for(int j=pp-1;j<m;j++){

 81             while(dq.size()&&dq.front()+pp<=j) dq.pop_front();

 82             while(dq.size()&&v[i*m+dq.back()]<=v[i*m+j]) dq.pop_back();

 83             dq.push_back(j);

 84             val[i*m+j]=v[i*m+dq.front()];

 85         }

 86     }

 87     for(int i=pp-1;i<m;i++){

 88         while(dq.size()) dq.pop_back();

 89         for(int j=0;j<qq-1;j++){

 90             while(dq.size()&&val[dq.back()*m+i]<=val[j*m+i]) dq.pop_back();

 91             dq.push_back(j);

 92         }

 93         for(int j=qq-1;j<n;j++){

 94             while(dq.size()&&dq.front()+qq<=j) dq.pop_front();

 95             while(dq.size()&&val[dq.back()*m+i]<=val[j*m+i]) dq.pop_back();

 96             dq.push_back(j);

 97             ans=min(ans,val[dq.front()*m+i]);

 98         }

 99     }

100     ll res=(ll)ans*(ll)(pp+1)*(ll)(qq+1);

101     cout<<res<<endl;

102     return 0;

103 }