Java教程

题解 万猪拱塔

本文主要是介绍题解 万猪拱塔,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

传送门

第一思路是和将军令挺像的,可以压成一维
但在一维上做这个问题只会 \(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]\) 内的块染黑):
image
有了这个转化,令 \(f(l)\) 为 \([l,r]\) 内含1个或3个黑色块的矩形个数
有 \(f(l) \geqslant 4, f(r)=4\) 所以和上面一样统计答案
然后考虑 \(r+1\) 时的更新
发现给一个块染色只影响4个矩形,大力分情况讨论即可
其实情况并不多,具体看代码
复杂度 \(O(nmlognm)\)

Code:
#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;
}
这篇关于题解 万猪拱塔的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!