#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n,m,Q,dx[N],dy[N];
char ch[N];
ll A[N],B[N];
ll makep(int xi,int yi){
	return 2ll * (xi + N) * N + yi + N;
}
int getid(ll x){
	int res = lower_bound(B + 1, B + 1 + m, x) - B;
	return res;
}
int mp[N];
struct question{
	int pos,id,sgn;
	ll point;
}q[N * 5];
int ans[N];
question makeq(int posi,ll pointi,int idi,int sgni){
	question tmp;
	tmp.pos = posi;
	tmp.point = pointi;
	tmp.id = idi;
	tmp.sgn = sgni;
	return tmp;
}
bool cmpq(question a,question b){
	return a.pos < b.pos;
}
int main(){
	scanf("%d",&n);
	scanf("%s",ch + 1);
	for(int i = 1; i <= n; i += 1){
		dx[i] = dx[i - 1];
		dy[i] = dy[i - 1];
		if(ch[i] == 'U') dy[i] += 1;
		else if(ch[i] == 'D') dy[i] -= 1;
		else if(ch[i] == 'L') dx[i] -= 1;
		else dx[i] += 1;
		A[i] = B[i] = makep(dx[i], dy[i]);
	}
	A[0] = B[n + 1] = makep(0, 0);
	sort(B + 1, B + 2 + n);
	m = unique(B + 1, B + 2 + n) - B - 1;
	for(int i = 0; i <= n; i += 1)
		A[i] = getid(A[i]);
	int cnt = 0;
	scanf("%d",&Q);
	for(int i = 1; i <= Q; i += 1){
		int xi,yi,li,ri;
		scanf("%d%d%d%d",&li,&ri,&xi,&yi);
		q[++cnt] = makeq(li - 1,makep(xi,yi),i,1);
		if(ri > li){
			int tx = dx[li - 1] + dx[ri] - xi;
			int ty = dy[li - 1] + dy[ri] - yi;
			q[++cnt] = makeq(ri - 1, makep(tx, ty), i, 1);
			q[++cnt] = makeq(li - 1, makep(tx, ty), i, -1);
		}
		q[++cnt] = makeq(n, makep(xi,yi), i, 1);
		q[++cnt] = makeq(ri - 1, makep(xi,yi), i, -1);
	}
	sort(q + 1,q + 1 + cnt,cmpq);
	for(int i = 0,j = 1; i <= n,j <= cnt; i += 1){
		mp[A[i]] += 1;
		while(q[j].pos == i && j <= cnt){
			int res = getid(q[j].point);
			if(B[res] == q[j].point)
				ans[q[j].id] += q[j].sgn * mp[res];
			j += 1;
		}
	}
	for(int i = 1; i <= Q;i += 1)
		if(ans[i]) printf("YES\n");
		else printf("NO\n");
	return 0;
}

Solution

Robot

$50pts$

这个应该很简单吧？直接暴力模拟即可，时间复杂度 $O(NQ)$。

$100pts$

这里就需要你注意到 翻转的特性 了。先给出结论：假设翻转前经过的第 $j$ 个点为 $(x_{1j},y_{1j})$，翻转后经过的第 $j$ 个点为 $(x_{2j},y_{2j})$，那么对于任意 $k$ 属于区间 $[l_i,r_i)$，都有：

$$x_{1,k},y_{1,k}) + (x_{2,l_i + r_i - k - 1},y_{2,l_i + r_i - k - 1}) = (x_{1,l_i - 1},y_{1,l_i - 1}) + (x_{1,r_i},y_{1,r_i}) $$

下面我们来解说一下这个结论：

• 首先，容易发现，对于任意的 $k$ 属于 $[1,l_i - 1]$ 或 $[r_i,n]$，$(x_{2,k},y_{2,k})=(x_{1,k},y_{1,k})$
• 接着，考察区间 $[l_i,r_i)$ 之间的 $k$。我们不妨这样分别考虑翻转前和翻转后的点：对于翻转前的点，认为它是从 $(x_{1,l_i - 1},y_{1,l_i - 1})$ 走过来的，而对于翻转后的点，我们认为它是从 $(x_{1,r_i},y_{1,r_i})$ 走过来的。这样处理的好处是什么呢？容易注意到，结论描述的事实上是翻转前后的点的对称性，而且是翻转前从左数的第 $i$ 个点对应翻转后从右数的第 $i$ 个点。这样的话，我们就可以应用数学归纳法来证明上面的结论了。
• 证明的第一步，$l_i - 1$ 和 $r_i$ 显然一定是满足这个式子的，即第 $0$ 个点是满足该结论的。
• 证明的第二步，假设第 $k$ 个点是满足这个结论的，我们来证明第 $k + 1$ 个点也是满足这一性质的。因为操作序列被翻转了，所以翻转前和翻转后的序列在这一点需要进行的操作恰好是相反的（$L$ 与 $R$ 是相反的，$U$ 和 $D$ 是相反的），所以第 $k$ 个点进行操作变成第 $k + 1$ 个点以后，两个对应点的 $x$ 坐标之和与 $y$ 坐标之和没有发生变化。
• Q.E.D

OK，那么我们这下就可以把问题拆解为这样的三个部分了：查询 $[1,l_i - 1]$ 中有没有出现 $(x_i,y_i)$；查询 $[l_i,r_i-1]$ 中有没有出现 $(x_i,y_i)$ 对应的对称点；查询 $[r_i,n]$ 中有没有出现 $(x_i,y_i)$。

那么怎么实现查询操作呢？直接 map 就完事了（懒人福利）。std 的写法是先把坐标转化成数字表示然后离散化然后直接用桶存。

时间复杂度为 $O((N + Q)logN)$ 。