Reincarnation

正因为梦易碎，才格外美好。

CF232E Quick Tortoise

发表于 更新于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

你以为的简单题，可不一定是简单题。

题目简介

题目来源：

评测链接：https://codeforces.com/problemset/problem/232/E

形式化题意：给定一张 的网格图，由 . 和 # 组成，# 表示障碍，不可走。多组询问是否能只向下和向右从 走到 。

数据范围：

看到这个离谱的数据范围，我还在想是不是可以 解决，然后想想 好像也不是很好卡过去，看起来是一个很简单的题，但总感觉哪里没对（指 原难度 *3000）

这种无修改多询问的题我们以前也似乎见过（猫树的时候提到过）。对于没有修改的题，我们可以考虑离线下来统一处理（类似于莫队），对于询问，我们要做到 的复杂度，所以可以选择按照 坐标分治（ 也行），记录 ，对于当前询问：

  1. 如果 ，则如果存在路径，必然会经过 ，处理当前询问。
  2. 如果 ，分治至 处理该询问。
  3. 如果 ，分治至 处理该询问。

对于询问的处理：我们记录布尔变量 表示从 到 的到达关系。其中 表示从 是否能到达 ，而 则表示能否从 到达 。

那显然的，当且存在 使得 ，则该询问有解。

对于每一层，我们有两个步骤：一是预处理 ，二是判断询问。时间复杂度为 ，所以总时间复杂度为 ，理论可过，但实际上会被卡掉。

这个时候可以选择卡常，也可以选择将 的 维进行滚动（卡空间），也可以选择 std::bitset 优化，最后的时间复杂度为 ，可过。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// ----- Eternally question-----
// Problem: Quick Tortoise
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF232E
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-01-04 20:35:41
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e2+10,MAXQ=6e5+10;
int N,M,Q;
std::bitset<MAXN>Pre[MAXN][MAXN],Suf[MAXN][MAXN];
char Mp[MAXN][MAXN];
struct query
{
	int x1,x2,y1,y2,id;
	inline void readIn(int x){ read(x1,y1,x2,y2),id=x; }
}Qry[MAXQ],T[MAXQ];
bool ans[MAXQ];
void conquer(int l,int r,int ql,int qr)
{
	if(l>r||ql>qr) return ;
	int tl=ql-1,tr=qr+1;
	int mid=(l+r)>>1;
	for(int i=1;i<=M;++i) Pre[mid][i]=Suf[mid][i]=0;
	for(int i=M;i>=1;--i)
		if(Mp[mid][i]=='.') Pre[mid][i][i]=1,Pre[mid][i]|=Pre[mid][i+1];
	for(int i=M;i>=1;--i)
		if(Mp[mid][i]=='.') Suf[mid][i][i]=1,Suf[mid][i]|=Suf[mid][i-1];
	for(int x=mid-1;x>=l;--x)
		for(int y=M;y>=0;--y)
			if(Mp[x][y]=='.') Pre[x][y]=Pre[x+1][y]|Pre[x][y+1];
			else Pre[x][y]=0;
	for(int x=mid+1;x<=r;++x)
		for(int y=1;y<=M;++y)
			if(Mp[x][y]=='.') Suf[x][y]=Suf[x-1][y]|Suf[x][y-1];
			else Suf[x][y]=0;
	for(int i=ql;i<=qr;++i)
	{
		auto q=Qry[i];
		if(q.x2<mid){ T[++tl]=q;continue; }
		if(q.x1>mid){ T[--tr]=q;continue; }
		ans[q.id]=(Pre[q.x1][q.y1]&Suf[q.x2][q.y2]).any();
	}
	for(int i=ql;i<=tl;++i) Qry[i]=T[i];
	for(int i=tr;i<=qr;++i) Qry[i]=T[i];
	conquer(l,mid-1,ql,tl),conquer(mid+1,r,tr,qr);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) scanf("%s",Mp[i]+1);
	read(Q);
	for(int i=1;i<=Q;++i) Qry[i].readIn(i);
	conquer(1,N,1,Q);
	for(int i=1;i<=Q;++i) puts(ans[i]?"Yes":"No");
	return 0;
}
/*

*/

当然，这道题也有在线做法，也就是猫树，加上 std::bitset 优化之后的时间复杂度可以做到 。

相关文章