进击的图灵机

假设执行完内的指令之后位于。

然后问题转换一下就是内和点相同的点有多少个。

然后由于只有个操作，所以不同的点数至多有个，所以对于每个点可以哈希一下，然后离散化映射成一个数，不同的数至多也只有个。

对于数维护一个vector记录所有数的下标，然后再二分就可以求区间内出现了多少次。

#include <bits/stdc++.h>
using namespace std;
#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 2e5 + 5;

int n, m;
char s[N];

int64_t hashCode(int x, int y) { return int64_t(x) * N + (y); }
int64_t h[N];
int64_t a[N], b[N];
int sb;

vector<int> p[N];

void go(char ch, int& x, int& y) {
  switch (ch) {
    case 'U':
      ++y;
      break;

    case 'D':
      --y;
      break;

    case 'L':
      --x;
      break;

    case 'R':
      ++x;
      break;

    default:
      break;
  }
}

void solve(int Case) {
  cin >> n >> m;
  cin >> s + 1;

  int x = N, y = N;
  b[++sb] = hashCode(x, y);
  a[0] = hashCode(x, y);
  for (int i = 1; i <= n; ++i) {
    go(s[i], x, y);
    a[i] = b[++sb] = hashCode(x, y);
  }

  sort(b + 1, b + 1 + sb);
  sb = unique(b + 1, b + 1 + sb) - (b + 1);
  debug(sb);
  for (int i = 1; i <= sb; ++i) p[i].push_back(0);
  for (int i = 0; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + sb, a[i]) - b;
  for (int i = 1; i <= n; ++i) p[a[i]].push_back(i);
  for (int i = 1; i <= sb; ++i) p[i].push_back(n + 1);

  function<int(int, int, int)> L = [&](int x, int l, int r) -> int {
    int y = lower_bound(p[x].begin(), p[x].end(), l) - p[x].begin();
    debug(x, y, p[x], l, r);
    return y;
  };

  function<int(int, int, int)> R = [&](int x, int l, int r) -> int {
    int y = upper_bound(p[x].begin(), p[x].end(), r) - p[x].begin();
    debug(x, y, p[x], l, r);
    return y;
  };

  int l, r;
  for (int i = 1; i <= m; ++i) {
    cin >> l >> r;
    debug(l, r);
    printf("%d\n", R(a[l - 1], l, r) - L(a[l - 1], l, r));
  }
}

int main() {
#ifdef BACKLIGHT
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; ++t) solve(t);
  return 0;
}