Link

CF1902 D Robot Queries

Question

Robot 初始在 \((0,0)\) ，有一个字符串 \(s\) ，表示运行列表

• \(U\)：y+1
• \(D\)：y -1
• \(L\) ：x -1
• \(R\) ：x+1

之后有 \(Q\) 次询问，有\(L,R,x,y\)，问把运行序列的 \([L,R]\) 反转，Robot 是否经过了点 \((x,y)\)

Solution

显然，对于一个区间 \([L,R]\) 内部顺序的变化，是不影响 \(s_L\) 执行前的那个点和 \(s_R\) 执行后的那个点的

之后来观察序列反转到底给中间的路径造成了什么影响

观察这样的一组操作 RDRUU

蓝色的是反转前的，绿色的是反转后的

我们重新在初始点建一个红色的坐标系，在最终点建一个黄色的坐标系，注意黄色坐标系是反着的

发现，红色坐标系里的每个点 \((x,y)\) 在黄色坐标系里面都有，于是，我们把黄色的坐标系里的点映射到红色坐标系

也就是

只需要判断 \((x',y')\) 是否在未反转的路径上

如何判断？

用 map<pair<int,int>,vector<int> > 记录，每个点 \((x,y)\) ，Robot 在这个点的时刻

对于 \((x',y')\) 只需要二分查找，是否有一个时刻在 \([L,R]\) 区间内

对于 \((x,y)\) 观察是否有一个时刻 在 \([L,R]\) 区间外，极端地，只需要判断第时刻和最后一个时刻即可

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
typedef pair<int,int> pii;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

char s[maxn];
map<pii,vector<int> > mp;
pii pos[maxn];

void check(){
    int x=read(),y=read(),l=read(),r=read();
    int x_=pos[r].first-x+pos[l-1].first,y_=pos[r].second-y+pos[l-1].second;

    auto& now1=mp[make_pair(x,y)];
    if(now1.size()>0){
        if(now1[0]<l||now1[now1.size()-1]>=r) {printf("YES\n");return ;}
    }
    auto& now2=mp[make_pair(x_,y_)];
    int pos_L=distance(now2.begin(),lower_bound(now2.begin(),now2.end(),l));
    if(pos_L<now2.size()&&now2[pos_L]<r) {printf("YES\n");return ;}

    printf("NO\n");
}
int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    int N=read(),Q=read();
    for(int i=1;i<=N;i++)
        s[i]=getchar();
    int x=0,y=0;
    pos[0]=make_pair(x,y);
    mp[pos[0]].push_back(0);
    for(int i=1;i<=N;i++){
        if(s[i]=='U') y++;
        if(s[i]=='D') y--;
        if(s[i]=='L') x--;
        if(s[i]=='R') x++;
        pos[i]=make_pair(x,y);
        mp[pos[i]].push_back(i);
    }
    for(int i=1;i<=Q;i++){
        check();
    }
}