我认为这份代码复杂度是正确的。单 log。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, q; char s[N];
map < pair <int, int> , vector <int> > f;
int a[N], b[N];
signed main() {
    cin >> n >> q;
    int X = 0, Y = 0;
    scanf("%s", s + 1);
    f[{0, 0}].push_back(0);
    for(int i = 1;i <= n; ++i) {
        if(s[i] == 'L') X --;
        if(s[i] == 'R') X ++;
        if(s[i] == 'U') Y ++;
        if(s[i] == 'D') Y --;
        f[{X, Y}].push_back(i); 
        a[i] = X, b[i] = Y;
        // cout << X << " " << Y << "\n";
    }
    for(int i = 1, l, r, x, y;i <= q; ++i) {
        scanf("%d %d %d %d", &x, &y, &l, &r); bool ff = 0;
        vector <int> g = f[{x, y}]; 
        if(g.size() and (g[0] < l or g[g.size() - 1] >= r)) ff = 1; //puts("1");
        else  {
            g = f[{a[l - 1] + a[r] - x, b[l - 1] + b[r] - y}];
            if(!g.size()) { puts("NO"); continue ; }
            int L = 0, R = g.size() - 1;
            // puts("2");
            while(L < R) {
                int mid = L + R >> 1;
                if(g[mid] < l) L = mid + 1;
                else R = mid; 
                // cout << L <<"\n";
            }
            // puts("3");
            // cout << g[L] << ": " << a[l - 1] + a[r] - x << " " << b[l - 1] + b[r] - y << "\n";
            if(g[L] < r and g[L] >= l) ff = 1;
        }  
        puts(ff ? "YES" : "NO");
    }
    return 0;
}
/*
首先我们计算出原来的顺序能否过 (x, y)
然后考虑反转的影响  发现对于所有点，有 
x1 + x2 = 2x
y1 + y2 = 2y
*/