《高手训练》解题报告 4.2 RMQ 问题

RMQ 问题的练习题。

未完待续

矩阵最值 matrix

时空限制:\(1\texttt{s},512\texttt{MiB}\)。

题目描述

我们有一个 \(n\) 行 \(m\) 列的矩阵,现在小 Q 有 \(K\) 个问题,每次询问一个以 \(x_1\) 行 \(y_1\) 列为左上角,\(x_2\) 行 \(y_2\) 列为右下角的子矩阵的最大值。

数据范围

对于 \(100\%\) 的数据,\(n,m\leq 250\),\(K\leq 10^6\)。

题解

二维 RMQ 问题,自然可以用二维 \(\texttt{ST}\) 表解决,初始化时间复杂度为 \(\Theta(\max\{n,m\}+nm\log_2n\log_2m)\),单词查询时间复杂度为 \(\Theta(1)\),总的时间复杂度为 \(\Theta(\max\{n,m\}+nm\log_2n\log_2m)+K)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=250+5;
const int MAXM=250+5;
const int MAXLOG2N=8+1;
const int MAXLOG2M=8+1;

int a[MAXN][MAXM];

namespace ST{
	int Lg[MAXN];
	int Max[MAXN][MAXM][MAXLOG2N][MAXLOG2M];
	inline void Init(int n,int m){
		Lg[0]=-1;
		reg int S=max(n,m);
		for(reg int i=1;i<=S;++i)
			Lg[i]=Lg[i>>1]+1;
		for(reg int i=1;i<=n;++i)
			for(reg int j=1;j<=m;++j)
				Max[i][j][0][0]=a[i][j];
		for(reg int k=0;k<MAXLOG2N;++k)
			for(reg int l=0;l<MAXLOG2M;++l)
				if(!l&&!k)
					continue;
				else if(!l)
					for(reg int i=1;i+(1<<k)-1<=n;++i)
						for(reg int j=1;j+(1<<l)-1<=m;++j)
							Max[i][j][k][0]=max(Max[i][j][k-1][0],Max[i+(1<<(k-1))][j][k-1][0]);
				else
					for(reg int i=1;i+(1<<k)-1<=n;++i)
						for(reg int j=1;j+(1<<l)-1<=m;++j)
							Max[i][j][k][l]=max(Max[i][j][k][l-1],Max[i][j+(1<<(l-1))][k][l-1]);
		return;
	}
	inline int query(reg int x1,reg int y1,reg int x2,reg int y2){
		reg int k=Lg[x2-x1+1],l=Lg[y2-y1+1];
		return max(
			max(Max[x1][y1][k][l],Max[x2-(1<<k)+1][y1][k][l]),
			max(Max[x1][y2-(1<<l)+1][k][l],Max[x2-(1<<k)+1][y2-(1<<l)+1][k][l])
		);
	}
}

int n,m,K;

int main(void){
	n=read(),m=read(),K=read();
	for(reg int i=1;i<=n;++i)
		for(reg int j=1;j<=m;++j)
			a[i][j]=read();
	ST::Init(n,m);
	while(K--){
		static int x1,y1,x2,y2;
		x1=read(),y1=read(),x2=read(),y2=read();
		printf("%d\n",ST::query(x1,y1,x2,y2));
	}
	return 0;
}

奶牛排队 tahort

时空限制:\(1\texttt{s},128\texttt{MiB}\)。

题目描述

数据范围

题解

假设我们已经求得了当前区间 \([l,r]\) 中最右边的最小值的位置最左边的最大值的位置(经典的 RMQ 问题),记作 \(\text{pMin},\text{pMax}\)。那么我们可以分类讨论。

  • \(\text{pMin}=\text{pMax}\),这说明当前区间里面所有的数都一样,这部分对答案的贡献显然为 \(0\)。
  • \(\text{pMin}<\text{pMax}\),这里可以统计答案,即 \(\text{pMin}\sim\text{pMax}\) 这一段可以更新答案。然后由于 \(\text{pMin}+1\sim\text{pMax}-1\) 这段的长度显然小于此处,不可能再次更新答案,舍弃,我们递归解决 \([l,\text{pMin}-1]\) 和 \([\text{pMax}+1,r]\)。
  • \(\text{pMin}>\text{pMax}\),这里不符合条件,考虑被切成三段的区间:
    • \(l\sim\text{pMax}\);
    • \(\text{pMax}+1\sim\text{pMin}-1\);
    • \(\text{pMin}\sim r\)。
    • 分别递归处理即可。

时间复杂度为 \(T(n)=T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+\Theta(1)\),分析可知为 \(\Theta(n\log_2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e5+5;
const int MAXLOG2N=17+1;

namespace ST{
	int Lg[MAXN];
	int Max[MAXN][MAXLOG2N],pMax[MAXN][MAXLOG2N];
	int Min[MAXN][MAXLOG2N],pMin[MAXN][MAXLOG2N];
	inline void Init(reg int n,reg int a[]){
		Lg[0]=-1;
		for(reg int i=1;i<=n;++i)
			Lg[i]=Lg[i>>1]+1;
		for(reg int i=1;i<=n;++i)
			Max[i][0]=Min[i][0]=a[i],pMax[i][0]=pMin[i][0]=i;
		for(reg int j=1;j<MAXLOG2N;++j){
			for(reg int i=1;i+(1<<j)-1<=n;++i){
				if(Max[i][j-1]>=Max[i+(1<<(j-1))][j-1])
					Max[i][j]=Max[i][j-1],pMax[i][j]=pMax[i][j-1];
				else
					Max[i][j]=Max[i+(1<<(j-1))][j-1],pMax[i][j]=pMax[i+(1<<(j-1))][j-1];
				if(Min[i+(1<<(j-1))][j-1]<=Min[i][j-1])
					Min[i][j]=Min[i+(1<<(j-1))][j-1],pMin[i][j]=pMin[i+(1<<(j-1))][j-1];
				else
					Min[i][j]=Min[i][j-1],pMin[i][j]=pMin[i][j-1];
			}
		}
		return;
	}
	inline int query_pMin(reg int l,reg int r){
		reg int k=Lg[r-l+1];
		reg int left=Min[l][k],right=Min[r-(1<<k)+1][k];
		if(right<=left)
			return pMin[r-(1<<k)+1][k];
		else
			return pMin[l][k];
	}
	inline int query_pMax(reg int l,reg int r){
		reg int k=Lg[r-l+1];
		reg int left=Max[l][k],right=Max[r-(1<<k)+1][k];
		if(left>=right)
			return pMax[l][k];
		else
			return pMax[r-(1<<k)+1][k];
	}
}

int n;
int h[MAXN];
int ans;

inline void Solve(reg int l,reg int r){
	if(l>r||l==r)
		return;
	reg int pMin=ST::query_pMin(l,r),pMax=ST::query_pMax(l,r);
	if(pMax<pMin)
		Solve(l,pMax),Solve(pMax+1,pMin-1),Solve(pMin,r);
	else{
		ans=max(ans,pMax-pMin+1);
		Solve(l,pMin-1),Solve(pMax+1,r);
	}
	return;
}

int main(void){
	n=read();
	for(reg int i=1;i<=n;++i)
		h[i]=read();
	ST::Init(n,h);
	Solve(1,n);
	printf("%d\n",ans);
	return 0;
}

大数计数 moe

时空限制:\(1\texttt{s}/512\texttt{MiB}\)。

题目描述

一个长度为 \(n\) 的大数,用 \(S_1S_2S_3\cdots S_n\) 表示,其中 \(S_i\) 表示数的第 \(i\) 位,\(S_1\) 是数的最高位,告诉你一些限制条件,每个条件表示为四个数,\(l_1,r_1,l_2,r_2\),即两个长度相同的区间,表示子串 \(S_{l_1}S_{l_1+1}S_{l_1+2}\cdots S_{r_1}\) 与 \(S_{l_2}S_{l_2+1}S_{l_2+2}\cdots S_{r_2}\) 完全相同。

数据范围

对于 \(100\%\) 的数据,\(1\leq n,m\leq 10^5\)。

题解

考虑用并查集维护连通块数量,设连通块数量为 \(p\),那么答案为 \(9\times 10^{p-1}\)。

用倍增优化并查集即可优化时间复杂度到 \(\Theta(n\log_2n)\)。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=1e5+5;
const int MAXLOG2N=17+1;
const int p=1e9+7;

int n,m;
int f[MAXLOG2N][MAXN];

inline int find(reg int x,reg int y){
	if(f[y][x]!=x)
		f[y][x]=find(f[y][x],y);
	return f[y][x];
}

inline void merge(reg int x,reg int y,reg int len){
	if(find(x,len)!=find(y,len))
		f[len][f[len][x]]=f[len][y];
	return;
}

inline int fpow(reg int x,reg int exp){
	reg int res=1;
	while(exp){
		if(exp&1)
			res=1ll*res*x%p;
		x=1ll*x*x%p;
		exp>>=1;
	}
	return res;
}

int main(void){
	n=read(),m=read();
	for(reg int j=0;j<MAXLOG2N;++j)
		for(reg int i=1;i<=n;++i)
			f[j][i]=i;
	for(reg int i=1;i<=m;++i){
		static int l1,r1,l2;
		l1=read(),r1=read(),l2=read(),read();
		for(reg int j=MAXLOG2N-1;j>=0;--j)
			if(l1+(1<<j)-1<=r1){
				merge(l1,l2,j);
				l1+=(1<<j),l2+=(1<<j);
			}
	}
	for(reg int j=MAXLOG2N-1;j>=1;--j)
		for(reg int i=1;i+(1<<j)-1<=n;++i){
			merge(i,find(i,j),j-1);
			merge(i+(1<<(j-1)),f[j][i]+(1<<(j-1)),j-1);
		}
	reg int cnt=0;
	for(reg int i=1;i<=n;++i)
		if(find(i,0)==i)
			++cnt;
	printf("%lld\n",9ll*fpow(10,cnt-1)%p);
	return 0;
}

矩阵求和 sum

时空限制:\(1\texttt{s},128\texttt{MiB}\)。

题目描述

矩阵 \(C\) 由数组 \(A,B\) 生成,生成方式如下:\(C_{i,j}=A_iB_j+iB_j+jA_i+ij\)。

定义一个矩阵的价值为这个矩阵中最大的元素的值。

定义 \(F_k\) 为:矩阵 \(C\) 的所有大小为 \(k\times k\) 的子矩阵的值的和。

现在请你输出 \(F_1,F_2,\cdots,F_n\) 对 \(10^9+7\) 取模的结果。

数据范围

对于 \(100\%\) 的数据,\(N\leq 10^5,0\leq A_i,B_i\leq 10^7\)。

题解

转化 \(C_{i,j}\):
\[C_{i,j}=A_iB_j+iB_j+jA_i+ij=(A_i+i)(B_j+j)\]

考虑令 \(A_i=A_i+i,B_j=B_j+j\),那么 \(C_{i,j}=A_iB_j\)。