题解：CF1902D Robot Queries

Jerrycyx · 2024-11-08 11:49:13 · 题解

前缀和 + 二分。

以样例 1 为例，假设翻转的范围是 [2,5]，那么翻转前后的操作序列分别为：

（其中蓝色表示翻转前序列，红色表示翻转后序列。）

上面的操作序列可以转化为下图：

观察发现（你也可以自己多测几组例子），翻转一段操作序列实际上就是将这一段操作路径旋转 180\degree。因为查询点在翻转路径上等价于它的翻转点在原路径上（旋转中心是路径的起点与终点的中点），所以我们无需真的将路径翻转（铁定超时）。

所以我们将每次查询的操作序列（设翻转区间为 [l,r]）分为三部分：翻转路径前的正常路径操作序列 [0,l-1]，被翻转的路径操作序列 [l,r]，翻转路径后的正常路径操作序列 [r,n]，查询点在任意一段上面都可以输出 YES。（因为翻转前后路径位移总和不变，所以三段路径一定连续）

判断在查询点（或它的翻转点）是否在规定时间段内被路径经过，可以记录每一个点每一次被经过的时刻，设规定时间段为 [s,t]，二分查找（可以用 lower_bound）第一个大于等于 s 的时间点是否存在且小于等于 t，即可判断该点是否在规定时间段内被路径经过。

#include<cstdio>
#include<map>
#include<vector>
using namespace std;

const int N=2e5+5;
int n,q; char op[N];
pair<int,int> sum[N];
map<pair<int,int>,vector<int>> vst;

int check(int l,int r,int x,int y)
{
    vector<int> &v=vst[{x,y}];
    auto it=lower_bound(v.begin(),v.end(),l);
    if(it==v.end()) return false;
    else return *it<=r;
}
int main()
{
    scanf("%d%d%s",&n,&q,op+1);
    vst[{0,0}].push_back(0);
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1];
        if(op[i]=='U') sum[i].second++;
        if(op[i]=='D') sum[i].second--;
        if(op[i]=='L') sum[i].first--;
        if(op[i]=='R') sum[i].first++;
        vst[sum[i]].push_back(i);
    }
    for(int i=1;i<=q;i++)
    {
        int x,y,l,r; scanf("%d%d%d%d",&x,&y,&l,&r);
        int rx=sum[l-1].first+sum[r].first-x;
        int ry=sum[l-1].second+sum[r].second-y;
        if(check(0,l-1,x,y)||check(l,r,rx,ry)||check(r,n,x,y)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}