1195E-OpenStreetMap

1195E-OpenStreetMap

给一个 的矩阵,求所有子矩阵 中最小值的和.

单调队列,先处理每一行大小为 的最小值,最后处理每一列大小为 的最小值.

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=2e7;
const long long mod=1e9+7;
const long long mod2=998244353;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
ll g[N];
int n,m,a,b;
int x,y,z;
int p[3005][3005];
int w[3005][3004];
ll ans=0;
void getmix(int Index){
    deque<pair<int,int> >Q;
    int tw=0;
    for(int i=1;i<=m;i++){
        while(!Q.empty()&&Q.back().first>=p[Index][i])Q.pop_back();
        Q.push_back({p[Index][i],i});
        if(i>=b){
            while(!Q.empty()&&Q.front().second<i-b+1)Q.pop_front();
            w[Index][++tw]=Q.front().first;
        }
    }
}
void mix(int Index){
    deque<pair<int,int> >Q;
    for(int i=1;i<=n;i++){
        while(!Q.empty()&&Q.back().first>=w[i][Index])Q.pop_back();
        Q.push_back({w[i][Index],i});
        if(i>=a){
            while(!Q.empty()&&Q.front().second<i-a+1)Q.pop_front();
            ans+=Q.front().first;
        }
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    cin>>n>>m>>a>>b;
    cin>>g[0]>>x>>y>>z;
    for(int i=1;i<=(n+1)*(m+1);i++)g[i]=(g[i-1]*x+y)%z;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    p[i][j]=g[(i-1)*m+j-1];
    for(int i=1;i<=n;i++)getmix(i);
    for(int i=1;i<=m-b+1;i++)mix(i);
    o(ans);
}