题解 万猪拱塔
2021/9/13 6:35:09
本文主要是介绍题解 万猪拱塔，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
传送门
第一思路是和将军令挺像的，可以压成一维
但在一维上做这个问题只会 \(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;
}
这篇关于题解 万猪拱塔的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难？答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图，怎么办？
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗？
- 2024-06-0514-ShardingSphere的分布式主键实现
