进击的图灵机

图灵机是一种通过读取纸带执行命令，模拟计算的抽象机器，为现代计算机提供了理论基础。现在有一个运行逻辑十分简单粗暴的图灵机，我们称之为"进击的图灵机"。

这种图灵机可以在二维平面上沿平行于坐标轴的方向行走，为了便于讨论，我们假设二维平面可以用 $xOy$ 坐标系来描述，图灵机初始在坐标系的 $(0,0)$ 点。

该图灵机所识别的纸带上有四种可能的命令 $U,D,L,R$ ，其含义分别为：

$U$ ：沿向量 $(0,1)$ 的方向行走一单位长度；

$D$ ：沿向量 $(0,-1)$ 的方向行走一单位长度；

$L$ ：沿向量 $(-1,0)$ 的方向行走一单位长度；

$R$ ：沿向量 $(1,0)$ 的方向行走一单位长度；

例如，若图灵机读取到命令序列 $UULRD$ ，则其坐标变化的序列为 $(0,0)→(0,1)→(0,2)→(-1,2)→(0,2)→(0,1)$ 。

现在，操作者有一条长度为 $n$ 的纸带，他每次让图灵机读取并执行这条纸带上连续的一段命令，一共进行 $m$ 次，对于每次执行命令，图灵机都会从坐标系的 $(0,0)$ 点出发，请你回答图灵机在这次执行命令过程中会回到坐标原点几次（最开始图灵机在原点的一次不计入考虑）。

输入第一行包含两个整数 $n,m(1 \leq n,m \leq 200000)$ ，表示纸带长度与执行命令次数。

第二行是一个长为 $n$ 的字符串，表示你手中的纸带，保证该字符串中只含有大写的 $U,D,L,R$ 。

接下来 $m$ 行，每行两个数字 $l,r(1 \leq l \leq r \leq n)$ ，表示这次执行命令读取的是纸带上第 $l$ 个字母到第 $r$ 个字母之间（含端点）的部分。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; char s[N]; pair<int,int> v[N]; map<pair<int,int>,vector<int>> mp; int main(){ int n,m; scanf("%d%d",&n,&m); scanf("%s",s+1); int x=0,y=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++; v[i]={x,y}; mp[{x,y}].push_back(i); } while(m--){ int l,r; scanf("%d%d",&l,&r); vector<int> &t=mp[v[l-1]]; auto st=lower_bound(t.begin(),t.end(),l); auto ed=upper_bound(t.begin(),t.end(),r); printf("%d\n",ed-st); } return 0; }

详情