【GMOJ6293】迷宫

前言

为什么这群神仙跑的这么快。。。\(1200ms\)的我瑟瑟发抖\(qwq\)。

题目

题目链接：https://gmoj.net/senior/#main/show/6293

\(n\leq 5,m\leq 200000,Q\leq 50000\)。

思路

先想一个暴力\(dp\)怎么做。设\(f[i][j][p][q]\)表示从第\(i\)行\(p\)列到第\(j\)行\(q\)列的最少步数。那么对于任意一个\(k(i\leq k\leq j)\)，有

\[f[i][j][p][q]=min^{m}_{l=1}(f[i][k][p][l]+f[k+1][j][l][q]+1) \]

初始化是将每一列的任意两行的距离记录。
显然，这个做法是针对无修改操作的一种最暴力的区间\(dp\)。而题目是要求支持修改的，容易发现这个转移式可以改成广义矩阵乘法，而且每次是询问区间的\(dp\)值，所以考虑用动态\(dp\)瞎搞。
线段树维护区间矩阵乘法，线段树的每一个结点\([l,r]\)储存一个\(m\times m\)的矩阵，第\(i\)行\(j\)列表示从网格图\(l\)行\(i\)列走到\(r\)行\(j\)列的最小路径长度。
每次询问时间复杂度为\(O(m^3\log n)\)，总时间复杂度为\(O(nm^3+Qm^3\log n)\)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=200010,M=6,Inf=1e9;
int n,m,Q,opt,a[M][N];

struct matrix
{
	int a[M][M];
	
	matrix()
	{
		memset(a,0x3f3f3f3f,sizeof(a));
	}
	
	friend matrix operator *(matrix a,matrix b)
	{
		matrix c;
		for (int i=1;i<M;i++)
			for (int j=1;j<M;j++)
				for (int k=1;k<M;k++)
					c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]+1);
		return c;
	}
}mat[N];

struct SegTree
{
	int l[N*4],r[N*4];
	matrix f[N*4];
	
	void pushup(int x)
	{
		f[x]=f[x*2]*f[x*2+1];
	}
	
	void build(int x,int ql,int qr)
	{
		l[x]=ql; r[x]=qr;
		if (ql==qr)
		{
			f[x]=mat[ql];
			return;
		}
		int mid=(ql+qr)>>1;
		build(x*2,ql,mid); build(x*2+1,mid+1,qr);
		pushup(x);
	}
	
	void update(int x,int k)
	{
		if (l[x]==k && r[x]==k)
		{
			f[x]=mat[l[x]];
			return;
		}
		int mid=(l[x]+r[x])>>1;
		if (k<=mid) update(x*2,k);
			else update(x*2+1,k);
		pushup(x);
	}
	
	matrix ask(int x,int ql,int qr)
	{
		if (l[x]==ql && r[x]==qr) return f[x];
		int mid=(l[x]+r[x])>>1;
		if (qr<=mid) return ask(x*2,ql,qr);
		if (ql>mid) return ask(x*2+1,ql,qr);
		return ask(x*2,ql,mid)*ask(x*2+1,mid+1,qr);
	}
}seg;

int main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d%d",&m,&n,&Q);
	for (int i=1;i<=m;i++)
		for (int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			for (int k=j;k<=m;k++)
			{
				bool flag=1;
				for (int l=j;l<=k;l++)
					if (!a[l][i]) flag=0;
				if (flag) mat[i].a[j][k]=mat[i].a[k][j]=k-j;
			}
	seg.build(1,1,n);
	while (Q--)
	{
		scanf("%d",&opt);
		if (opt==1)
		{
			int x,i;
			scanf("%d%d",&x,&i);
			a[x][i]^=1;
			memset(mat[i].a,0x3f3f3f3f,sizeof(mat[i].a));
			for (int j=1;j<=m;j++)
				for (int k=j;k<=m;k++)
				{
					bool flag=1;
					for (int l=j;l<=k;l++)
						if (!a[l][i]) flag=0;
					if (flag) mat[i].a[j][k]=mat[i].a[k][j]=k-j;
				}
			seg.update(1,i);
		}
		else
		{
			int x,y,xx,yy;
			scanf("%d%d%d%d",&x,&y,&xx,&yy);
			matrix ans=seg.ask(1,y,yy);
			if (ans.a[x][xx]<Inf) printf("%d\n",ans.a[x][xx]);
				else printf("-1\n");
		}
	}
	return 0;
}