题解：P8164 [JOI 2022 Final] 沙堡 2 / Sandcastle 2
lucky_baizq · · 题解
H.P8164 [JOI 2022 Final] 沙堡 2 / Sandcastle 2 - 洛谷
题意：你从任意一个点出发，向比当前点权值小的点走，求最终可能完整的覆盖的矩形的数目。
题解：每个点若有合法路径，则连向的对应点固定，是相邻的比本身小的最大的点。考虑怎么判断一个矩形合法:连的边是一条链，则我们让一条完整的链设置一个权值使得其值独特，具体的，我们设
- 对于他作为四联通种最大值的位置（可能成为起点的位置），我们对它赋权
inf−f_i ，其中inf 是一个足够大的值； - 否则对它赋权
a_i−f_i 。
考虑这样做的正确性，确定好边界后，每个矩形合法就是一个值
这样你枚举上下界，每次暴力求出右边界三联通权值加左边四联通的权值
然后还要加上只有
Code：唐笑是我的神啊，
#include<bits/stdc++.h>
using namespace std;
namespace IO {
static const string name = "disinfect", suf_in = "in", suf_out = "out";
static constexpr int S = (1 << 21), dgt = 2, ir = 1; char b[S], *p1 = b, *p2 = b, pb[S], *p = pb; void Fl() { fwrite(pb, 1, p - pb, stdout), p = pb; }
#define _r return *this
struct Fr { bool _b(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; } char gc() { if (p1 == p2) p2 = (p1 = b) + fread(b, 1, S, stdin); return p1 == p2 ? ' ' : *p1++; } template <class T> Fr &operator>>(T &x) { char c = gc(); T f = 1; for (x = 0; !isdigit(c);) { if(c == '-') f = -1; c = gc(); } while (isdigit(c)) x = (x * 10) + (c ^ 48), c = gc(); x *= f; _r; } Fr &operator>>(char *s) { int l = 0; char c; operator>>(c); for (; !_b(c); s[l++] = c, c = gc()) ; s[l] = '\0'; _r; } Fr &operator>>(string &s) { s = ""; char c = gc(); while(_b(c)) c = gc(); while(!_b(c)) s += c, c = gc(); _r; } Fr &operator>>(double &x) { double t = 1, s = 0; char c = gc(); for (x = 0; !isdigit(c); c = gc()) s = (c == '-'); for (; isdigit(c); c = gc()) x = x * 10 + (c - 48); if (c == '.') for (c = gc(); isdigit(c); c = gc()) x += (t /= 10.0) * (c - 48), s && (x = -x); _r; } Fr &operator>>(char &c) { do c = gc(); while (_b(c)); _r; } } cin;
struct Fw { void pt(char c) { *p++ = c; if (p - pb == S) Fl(); } template <class T> Fw &operator<<(T x) { if (!x) { pt(48); _r; } x < 0 && (pt('-'), x = -x); int s[64], t = 0; while (x) s[++t] = x % 10, x /= 10; while (t) pt(s[t--] + 48); _r; } Fw &operator<<(char c) { pt(c); _r; } Fw &operator<<(const char *s) { operator<<((char *)s); _r; } Fw &operator<<(char *s) { int c = 0; while (s[c]) pt(s[c++]); _r; } Fw &operator<<(double x) { int k = 0; x < 0 && (pt('-'), x = -x), ir && (x += 5 * pow(10, -dgt - 1)), operator<<(int(x)), pt('.'), x -= int(x); while (k++ < dgt) pt(int(x *= 10) + 48), x -= int(x); _r; } Fw &operator<<(string s) { for(int i = 0; s[i] != '\0'; ++i) pt(s[i]); _r; } ~Fw() { Fl(); } } cout;
struct fileIO { fileIO() { freopen((name + "." + suf_in).c_str(), "r", stdin), freopen((name + "." + suf_out).c_str(), "w", stdout); } } ;
};
#define cin IO::cin
#define cout IO::cout
#define int long long
const int N=255,M=50010,X=1e9;
int n,m,a[N][M],ans,l[N][M],c[N][M],r[N][M];
unordered_map<int,int>t;
int f(int x,vector<int> v) {
int s=X,mx=0;
for(int y:v)
if(y<x)mx=max(mx,y);
else s=x;
return s-mx;
}
signed main(){
cin>>n>>m;
if(n<=m)
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
if(n>m){
swap(n,m);
for(int j=0;j<m;j++)
for(int i=0;i<n;i++)
cin>>a[i][j];
}
for(int i=1;i<n-1;i++){
for(int j=0;j<m-1;j++)l[i][j]=l[i-1][j]+f(a[i][j],{a[i-1][j],a[i][j+1],a[i+1][j]});
for(int j=1;j<m;j++)r[i][j]=r[i-1][j]+f(a[i][j],{a[i-1][j],a[i][j-1],a[i+1][j]});
for(int j=1;j<m-1;j++)c[i][j]=c[i-1][j]+f(a[i][j],{a[i-1][j],a[i][j-1],a[i+1][j],a[i][j+1]});
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++,t.clear())
for(int s=0,k=1;k<m;k++){
t[l[i][k-1]-l[j-1][k-1]-f(a[i][k-1],{a[i+1][k-1],a[i][k]})-f(a[j][k-1],{a[j-1][k-1],a[j][k]})+s]++;//插入左端點，放在左邊插入
auto it=t.find(s+f(a[i][k],{a[i+1][k],a[i][k-1]})+f(a[j][k],{a[j-1][k],a[j][k-1]})+r[j-1][k]-r[i][k]-X);//把這個右端點的r缺失的貢獻補救上
if(it!=t.end())ans+=it->second;
s+=c[j-1][k]-c[i][k]+f(a[i][k],{a[i+1][k],a[i][k-1],a[i][k+1]})+f(a[j][k],{a[j-1][k],a[j][k-1],a[j][k+1]});//把這一列的全部給補上
}
for(int i=0;i<n;i++)for(int j=1,A=0,B=0;j<m;ans+=A+B,j++)if(a[i][j]<a[i][j-1])A++,B=0;else A=0,B++;//一行的
for(int j=0;j<m;j++)for(int i=1,A=0,B=0;i<n;ans+=A+B,i++)if(a[i][j]<a[i-1][j])A++,B=0;else A=0,B++;//一列的
cout<<ans+n*m;//加上一個點的
return 0;
}