ABC335 C - Loong Tracking

\(\mathtt{TAG}\)： STL，模拟

\(\mathtt{APPRAIS}\)：STL の巧用

前置知识

deque 可以下表 \(O(1)\) 访问。
deque 可以删除队尾队首元素，在队尾队首插入元素。

First. 修改

设 deque 中第 \(i\) 个元素表示部件 \(i\) 的位置。

每次修改，即在队首插入 \(1\) 接下来会走到的点，然后删除 \(n\) 原来的位置。

这样，原本 \(i\) 的位置就赋给了 \(i + 1\)，也就实现了题目中所说的：\(i\) 部分 \((2\le i \le N)\) 移动到部件 \(i−1\) 移动前的坐标位置。\(1\) 也移至了新的位置。

Second. 查询

直接访问 deque 中第 \(x\) 个位置即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pi;
const int N = 1e6 + 10;
int n , q;
pi p[N];

signed main() {
    ios::sync_with_stdio(0);
    cin >> n >> q;
    deque<pi> que;
    for (int i = 1; i <= n; i++) {
        que.push_back({ i, 0 });
    }
    while (q--) {
        int opt , id;
        char arr;
        cin >> opt;
        if (opt == 1) {
            cin >> arr;
            if (arr == 'L') {
                pi pos = que.front();
                pos.first--;
                que.pop_back();
                que.push_front(pos);
            } else if (arr == 'R') {
                pi pos = que.front();
                pos.first++;
                que.pop_back();
                que.push_front(pos);
            } else if (arr == 'U') {
                pi pos = que.front();
                pos.second ++;
                que.pop_back();
                que.push_front(pos);
            } else {
                pi pos = que.front();
                pos.second --;
                que.pop_back();
                que.push_front(pos);
            }
        } else {
            cin >> id;
            cout << que[id - 1].first << ' ' << que[id - 1].second << endl;
        }
    }
    return 0;
}