题解：AT_abc398_d [ABC398D] Bonfire

endswitch · 2025-03-23 11:39:12 · 题解

不妨将一个坐标哈希下来，同时维护一个哈希偏移量懒标记 tag。

对于 W / E 操作，将 tag 加 / 减 1，对于 N / S 操作，将 tag 加 / 减 N。

再维护一个 std :: set，表示此时有烟的每个点的坐标哈希值。每次查询点对 (r, c) 是否存在于 std :: set 中。对于插入一个新节点 s.insert(-tag) 即可。

需要注意的是，如果是按行列哈希的话，进制要开大一点。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int Q, n, m, tag;
char op;
set<int> s;

inline int to(int x, int y) {
    return x * (Q << 3) + y;
}

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> Q >> n >> m;

    s.insert(0);

    for(int i = 1 ; i <= Q ; ++ i) {
        cin >> op;

        if(op == 'N') tag -= (Q << 3);
        else if(op == 'W') -- tag;
        else if(op == 'S') tag += (Q << 3);
        else ++ tag;

        s.insert(-tag);

//      cerr << "tag:" << tag << ' ' << "to:" << to(n, m) << '\n';  
//      cerr << "\nset:\n";
//      for(auto j : s) cerr << j << ' ';
//      cerr << '\n';

        if(s.find(to(n, m) - tag) != s.end()) cout << 1;
        else cout << 0;

//      cout << '\n';
    }

    return 0;
}