传送门
第一思路是和将军令挺像的,可以压成一维
但在一维上做这个问题只会 \(O(m^2)\) 的,所以整体就成了 \(O(n^2m^2)\)
仅对于这个题在一维上有 \(O(mlogm)\) 做法:
利用了「\(w_{i,j}\) 互不相同」的性质
对于一个固定的 \(r\),一个合法的 \(l\) 要满足 \(max(l, r)-min(l, r)=r-l\)
即 \(f(l)=max(l, r)-min(l,r)+l=r\)
因为 \(w_{i,j}\) 互不相同,所以 \(f(l)\geqslant r\)
所以可以在线段树上维护 \(f(l)\) 每次判断最小值是不是 \(f(r)\) 以及取到最小值的个数及这些位置的 \(\sum l\)
然后 \(r+1\) 时影响到的 \(min\) 及 \(max\) 的位置
可以维护一个普通单调栈,插入 \(r+1\) 时弹掉的位置就是需要修改的位置
然后考虑二维情况:
刚才那个东西直接放到二维上是 \(O(min(n, m)nmlogm)\) 的,不可过
发现题面还有一个性质是 \(w_{i,j}\) 形成一个排列
所以值域上的每个位置都在矩形里对应了恰好一个位置
发现题面里有个小提示:在样例解释那里很没必要的扯出了一个面积
那发现一个面积为 \(S\) 的矩形满足 \(max-min=i*j-1\) 实际上就是在说这个矩形是由 \(min\) 到 \(max\) 这些值对应的位置组成的
所以考虑在值域上像上面那样做
需要神仙转化一步(先把 \([l, r]\) 内的块染黑):
有了这个转化,令 \(f(l)\) 为 \([l,r]\) 内含1个或3个黑色块的矩形个数
有 \(f(l) \geqslant 4, f(r)=4\) 所以和上面一样统计答案
然后考虑 \(r+1\) 时的更新
发现给一个块染色只影响4个矩形,大力分情况讨论即可
其实情况并不多,具体看代码
复杂度 \(O(nmlognm)\)
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 200010 #define ll long long #define reg register int #define fir first #define sec second #define make make_pair //#define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n, m; int **mat, **w; pair<int, int> rk[N]; const ll mod=998244353; inline void md(ll& a, ll b) {a+=b; a=a>=mod?a-mod:a;} namespace force{ ll ans; void solve() { for (reg i=1; i<=n; ++i) { for (reg j=1; j<=m; ++j) { for (reg k=i; k<=n; ++k) { for (reg h=j; h<=m; ++h) { int maxn=0, minn=INF; for (reg x=i; x<=k; ++x) { for (reg y=j; y<=h; ++y) { maxn=max(maxn, w[x][y]); minn=min(minn, w[x][y]); } } if (maxn-minn == (k-i+1)*(h-j+1)-1) ans = (ans+(k-i+1)*(h-j+1)%mod)%mod; } } } } printf("%lld\n", ans); exit(0); } } namespace task1{ ll ans; int tem1[N], tem2[N]; #define max(a, b) ((a)>(b)?(a):(b)) #define min(a, b) ((a)<(b)?(a):(b)) void check(int len) { //cout<<"check: "<<len<<endl; for (reg i=m,maxn,minn; i; --i) { maxn=tem1[i], minn=tem2[i]; for (reg j=i; j; --j) { maxn=max(maxn, tem1[j]); minn=min(minn, tem2[j]); if (maxn-minn == len*(i-j+1)-1) md(ans, len*(i-j+1)%mod); //, cout<<"md: "<<len*(j-i+1)<<endl; } } } void solve() { for (reg i=1; i<=n; ++i) { for (reg j=i; j<=n; ++j) { for (reg k=1; k<=m; ++k) tem1[k]=0, tem2[k]=INF; for (reg k=i; k<=j; ++k) for (reg h=1; h<=m; ++h) { tem1[h]=max(tem1[h], w[k][h]); tem2[h]=min(tem2[h], w[k][h]); } check(j-i+1); //cout<<"ij: "<<i<<' '<<j<<' '<<ans<<endl; } } printf("%lld\n", ans); exit(0); } #undef max #undef min } namespace task2{ ll ans; #define max(a, b) ((a)>(b)?(a):(b)) #define min(a, b) ((a)<(b)?(a):(b)) struct que1{ int l=1, r=0; struct node{int val, pos; inline void build(int v, int p) {val=v; pos=p;}}; node* q; inline void set(int k) {l=1, r=0; q=new node[k];} inline void clear() {l=1; r=0;} inline void add(int val, int pos) { while (l<=r && q[r].val<=val) --r; q[++r].build(val, pos); } inline int query() {return q[l].val;} inline void upd(int deline) { while (l<=r && q[l].pos<deline) ++l; } }tem1[N]; struct que2{ int l=1, r=0; struct node{int val, pos; inline void build(int v, int p) {val=v; pos=p;}}; node* q; inline void set(int k) {l=1, r=0; q=new node[k];} inline void clear() {l=1; r=0;} inline void add(int val, int pos) { while (l<=r && q[r].val>=val) --r; q[++r].build(val, pos); } inline int query() {return q[l].val;} inline void upd(int deline) { while (l<=r && q[l].pos<deline) ++l; } }tem2[N]; void check(int len) { //cout<<"check: "<<len<<endl; for (reg i=m,maxn,minn; i; --i) { maxn=tem1[i].query(), minn=tem2[i].query(); for (reg j=i; j; --j) { maxn=max(maxn, tem1[j].query()); minn=min(minn, tem2[j].query()); if (maxn-minn == len*(i-j+1)-1) md(ans, len*(i-j+1)%mod); //, cout<<"md: "<<len*(j-i+1)<<endl; } } } void solve() { for (reg i=1; i<=m; ++i) tem1[i].set(n+10), tem2[i].set(n+10); for (reg len=1; len<=n; ++len) { for (reg i=1; i<=m; ++i) tem1[i].clear(), tem2[i].clear(); for (reg i=1; i<=len; ++i) for (reg j=1; j<=m; ++j) tem1[j].add(w[i][j], i), tem2[j].add(w[i][j], i); for (reg i=len; i<=n; ++i) { for (reg j=1; j<=m; ++j) tem1[j].upd(i-len+1), tem2[j].upd(i-len+1); check(len); if (i<n) { for (reg j=1; j<=m; ++j) tem1[j].add(w[i+1][j], i+1), tem2[j].add(w[i+1][j], i+1); } } } printf("%lld\n", ans); exit(0); } #undef max #undef min } namespace task{ ll mins[N<<2], ans; int tl[N<<2], tr[N<<2], minf[N<<2], minc[N<<2], tag[N<<2]; #define tl(p) tl[p] #define tr(p) tr[p] #define minf(p) minf[p] #define minc(p) minc[p] #define mins(p) mins[p] #define tag(p) tag[p] inline int max(int a, int b) {return a>b?a:b;} inline int min(int a, int b) {return a<b?a:b;} void pushup(int p) { minf(p)=min(minf(p<<1), minf(p<<1|1)); minc(p)=mins(p)=0; if (minf(p<<1)==minf(p)) { minc(p)+=minc(p<<1); md(mins(p), mins(p<<1)); } if (minf(p<<1|1)==minf(p)) { minc(p)+=minc(p<<1|1); md(mins(p), mins(p<<1|1)); } } void spread(int p) { minf(p<<1)+=tag(p); tag(p<<1)+=tag(p); minf(p<<1|1)+=tag(p); tag(p<<1|1)+=tag(p); tag(p)=0; } void build(int p, int l, int r) { tl(p)=l; tr(p)=r; minf(p)=INF; if (l==r) {minf(p)=INF; minc(p)=1; mins(p)=l-1; return ;} int mid=(l+r)>>1; build(p<<1, l, mid); build(p<<1|1, mid+1, r); } void upd(int p, int pos, int dat) { if (tl(p)==tr(p)) {minf(p)=dat; return ;} if (tag(p)) spread(p); int mid=(tl(p)+tr(p))>>1; if (pos<=mid) upd(p<<1, pos, dat); else upd(p<<1|1, pos, dat); pushup(p); } void upd(int p, int l, int r, int dat) { if (l<=tl(p) && r>=tr(p)) {minf(p)+=dat; tag(p)+=dat; return ;} if (tag(p)) spread(p); int mid=(tl(p)+tr(p))>>1; if (l<=mid) upd(p<<1, l, r, dat); if (r>mid) upd(p<<1|1, l, r, dat); pushup(p); } void query(int p) { if (tl(p)==tr(p)) {printf("%d ", minf(p)); return ;} if (tag(p)) spread(p); query(p<<1); query(p<<1|1); if (p==1) printf("\n"); } void calc(int r, int x1, int x2, int x3) { //if (r==4) cout<<"calc: "<<r<<' '<<x1<<' '<<x2<<' '<<x3<<endl; int t[5]={0, r, x1, x2, x3}; sort(t, t+5); //if (r==4) {cout<<"t: "; for (int i=0; i<4; ++i) cout<<t[i]<<' '; cout<<endl;} if (t[1]==r) {if (r>1) upd(1, 1, r-1, 1); return ;} int pos=1, base=1; while (t[pos]!=r) ++pos; --pos; //cout<<"pos: "<<pos<<endl; for (; pos; ++base,--pos) { if (base==1) { upd(1, t[pos-1]+1, t[pos], -1); //, cout<<"go cge: "<<t[pos-1]+1<<' '<<t[pos]<<' '<<-1<<endl; if (t[pos]+1<=t[pos+1]-1) upd(1, t[pos]+1, t[pos+1]-1, 1); } else if (base==2) upd(1, t[pos-1]+1, t[pos], 1); //, cout<<"go cge: "<<t[pos-1]+1<<' '<<t[pos]<<' '<<1<<endl; else if (base==3) upd(1, t[pos-1]+1, t[pos], -1); //, cout<<"go cge: "<<t[pos-1]+1<<' '<<t[pos]<<' '<<-1<<endl; else puts("error"); } //if (r==4) cout<<endl; } void solve() { //memset(minf, 127, sizeof(minf)); build(1, 1, n*m); for (reg i=1,x,y; i<=n*m; ++i) { //cout<<"i: "<<i<<endl; upd(1, i, 4); //query(1); x=rk[i].fir, y=rk[i].sec; calc(i, w[x-1][y], w[x][y-1], w[x-1][y-1]); calc(i, w[x-1][y], w[x][y+1], w[x-1][y+1]); calc(i, w[x+1][y], w[x][y-1], w[x+1][y-1]); calc(i, w[x+1][y], w[x][y+1], w[x+1][y+1]); ///query(1); //cout<<"minf: "<<minf(1)<<endl; if (minf(1)==4) { ans=(ans+1ll*i*minc(1)-mins(1))%mod; //cout<<"ans: "<<ans<<endl; //cout<<"minc: "<<minc(1)<<endl; //cout<<"mins: "<<mins(1)<<endl; } else ans=(ans+1)%mod; //cout<<endl; } printf("%lld\n", ans); exit(0); } } signed main() { freopen("pig.in", "r", stdin); freopen("pig.out", "w", stdout); n=read(); m=read(); if (n<=m) { w=new int*[n+5]; for (reg i=0; i<=n+1; ++i) {w[i]=new int[m+5]; memset(w[i], 127, sizeof(int)*(m+5));} for (reg i=1; i<=n; ++i) for (reg j=1; j<=m; ++j) {w[i][j]=read(); rk[w[i][j]]=make(i, j);} } else { mat=new int*[n+5]; w=new int*[m+5]; for (reg i=0; i<=n+1; ++i) mat[i]=new int[m+5]; for (reg i=1; i<=n; ++i) for (reg j=1; j<=m; ++j) mat[i][j]=read(); for (reg i=0; i<=m+1; ++i) {w[i]=new int[n+5]; memset(w[i], 127, sizeof(int)*(n+5));} for (reg i=1; i<=m; ++i) for (reg j=1; j<=n; ++j) {w[i][j]=mat[j][i]; rk[w[i][j]]=make(i, j);} swap(n, m); } task::solve(); return 0; }