Robot Queries

题意简述

给定长度为 $n$ 的机器人移动指令字符串，指令包含 U/D/L/R。
共有 $q$ 次查询，每次查询给出目标坐标 $(x,y)$，以及区间 $[l,r]$。
本次查询临时把第 $l\sim r$ 条指令反转，不修改原串。
问执行修改后的指令路径中，机器人是否可以走到坐标 $(x,y)$，输出YES/NO。

查询之间互相独立。

思路推导

反转后的指令序列分为三部分：
$$s_1{s}_2\cdots s_{l-1}\underset{被反转的中间段}{\underbrace{s_r{s}_{r-1}\cdots s_l}}{s}_{r+1}\cdots s_n$$
每条指令视作向量，向量加法满足结合律、交换律。

• 前缀 $s_1\cdots s_{l-1}$、后缀 $s_{r+1}\cdots s_n$ 指令顺序不变，路径和原路径完全一致。
• 中间段指令颠倒，不能直接拿目标坐标在原路径查询。
  
  
  定义： $pos[i]$：执行完前 $i$ 条指令后的坐标，本质是向量前缀和。
  $$pos[0]=(0,0),pos[i]=pos[i-1]+{\vec{s}}_i$$ 反转段内部，执行 $k$ 条反转指令后到达点 $P_{xy}$：
  $$P_{xy}=pos[l-1]+{\vec{s}}_r+{\vec{s}}_{r-1}+\cdots +{\vec{s}}_{r-k+1}$$
  向量求和与顺序无关： $${\vec{s}}_{r-k+1}+\cdots +{\vec{s}}_r=pos[r]-pos[r-k]$$
  代入： $$P_{xy}=pos[l-1]+(pos[r]-pos[r-k])$$
  移项得到核心公式： $$\mathbf{pos}[\mathbf{r}-\mathbf{k}]=\mathbf{pos}[\mathbf{l}-1]+\mathbf{pos}[\mathbf{r}]-{\mathbf{P}}_{\mathbf{xy}}$$ 范围：$1\le k\le r-l+1$ $$l-1\le r-k\le r-1$$

反转段内部到达 $P_{xy}$ $⟺$ 原路径下标 $i\in [l-1,r-1]$，满足 $pos[i]=pos[l-1]+pos[r]-P_{xy}$

查询分3种情况

设查询目标 $T=(x,y)$

1. 前缀 $[1,l-1]$：不受反转，直接查询原路径，$T$ 是否存在下标区间 $[1,l-1]$。
2. 后缀 $[r+1,n]$：不受反转，直接查询原路径，$T$ 是否存在下标区间 $[r+1,n]$。
3. 反转中间段：计算对称点 $Tar=pos[l-1]+pos[r]-T$；查询原路径 $Tar$ 是否存在下标区间 $[l-1,r-1]$。
   任意一个成立输出YES，否则NO。

预处理设计

1. pos[]保存每一步坐标，必须包含起点 $pos[0]=(0,0)$。
2. unordered_map<ll, vector<int>> umap

• 将坐标 $(x,y)$ 打包为64位整数作为key；
• value：到达该坐标的所有下标，插入天然有序；
• 使用lower_bound二分快速判定区间内是否存在下标。

3. 原点下标0必须存入哈希，$l=1$时 $l-1=0$会访问。

复杂度：预处理 $O(n)$，单次查询 $O(\log n)$；总 $O(n+q\log n)$，支持 $n,q\le 2\cdot 10^5$。


相似题目：

1. 3694. 删除子字符串后不同的终点 - 力扣（LeetCode）
2. Problem - 1296C - Yet Another Walking Robot - Codeforces

void solve(){
	//读入数据
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	
	vector<array<int, 4>> query(q);
	for(auto & [x, y, l, r] : query){
		cin >> x >> y >> l >> r;
	}
	
	//预处理pos数组和umap
	vector<pair<int, int>> pos(n+1);
	unordered_map<ll, vector<int>> umap;
	auto f=[](char c, auto & p) -> void {
		auto & [x, y]=p;
		if(c=='U') ++y;
		else if(c=='D') --y;
		else if(c=='L') --x;
		else ++x;
	};
	
	pos[0]={0, 0};
	//记得插入原点
	umap[0].push_back(0);
	pair<int, int> p={0, 0};
	for(int i=0; i<n; ++i){
		f(s[i], p);
		pos[i+1]=p;
		auto & [x, y]=p;
		ll k=(uint64_t)x << 32 | (uint32_t)y;
		umap[k].push_back(i+1);
	}
	
	//在对应区间内二分查找是否存在合法下标
	auto ff=[&](pair<int,int> p, int l, int r, int flag) -> bool {
		if(l>r) return false;
		if(p.first==0 && p.second==0) return true;
		
		if(flag==0){
			auto & [x, y]=p;
			ll key=(uint64_t)x << 32 | (uint32_t)y;
			auto & v=umap[key];
			if(v.empty()) return false;
			
			auto it=lower_bound(v.begin(), v.end(), l);
			if(it==v.end() || *it>r) return false;
			else return true;
		}else{
			auto & [x, y]=p;
			auto [x0, y0]=pos[l-1];
			auto [x1, y1]=pos[r];
			int kx=x0+x1-x;
			int ky=y0+y1-y;
			ll key=(uint64_t)kx << 32 | (uint32_t)ky;
			auto & v=umap[key];
			if(v.empty()) return false;
			
			auto it=lower_bound(v.begin(), v.end(), l-1);
			if(it==v.end() || *it>r-1) return false;
			else return true;
		}
	};
	
	//处理查询
	for(auto & [x, y, l, r] : query){
		bool ok1, ok2, ok3;
		ok1=ff({x, y}, 1, l-1, 0);
		ok2=ff({x, y}, r+1, n, 0);
		ok3=ff({x, y}, l, r, 1);
		
		if(ok1 || ok2 || ok3){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	}
}