思路

其他所有部位会跟随上一个部位移动，很容易让人联想到队列。但是，如果是按顺序存储移动的时间复杂度就到了 $O(n)$。我们考虑倒序存储，每执行一次1操作我们就把新的队首添加到队尾，龙后面的部分就是队尾依次往后数了，操作时间复杂度为 $O(1)$。

AC Code

由于需要随时查询序列中的元素，所以STL中的队列不能用了。

做法1：手搓队列

代码来源于老师上课的PPT。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,s,t,q;
struct node{
    int x,y;
}a[2000006];
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;++i){
        a[n-i+1]={i,0};
    }
    int tot=n;
    char c;
    for(int i=1;i<=q;++i){
        cin>>k;
        if(k==1){
            cin>>c;
            node tmp=a[tot];
            if(c=='U')  tmp.y++;
            else if(c=='D') tmp.y--;
            else if(c=='L') tmp.x--;
            else tmp.x++;
            a[++tot]=tmp;
        }
        else{
            cin>>s;
            cout<<a[tot-s+1].x<<' '<<a[tot-s+1].y<<'\n';
        }
    }
}

做法2：双端队列

deque的好处在于不仅可以在队列的两端进行插入、删除，还可以通过下标随时访问队列中的元素，是本题数据结构的一个不二之选。

做法方面与手搓队列不尽相同，可以适当参考。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,q;
struct pos{
    ll x,y;
};
deque<pos> deq;
int main(){
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++)
        deq.push_front({i,0});
    for(ll i=1,opt;i<=q;i++){
        scanf("%lld",&opt);
        if(opt==1){
            char dire;
            cin>>dire;
            switch(dire){
                case 'R':
                    deq.push_back({deq[deq.size()-1].x+1,deq[deq.size()-1].y});break;
                case 'L':
                    deq.push_back({deq[deq.size()-1].x-1,deq[deq.size()-1].y});break;
                case 'U':
                    deq.push_back({deq[deq.size()-1].x,deq[deq.size()-1].y+1});break;
                default:
                    deq.push_back({deq[deq.size()-1].x,deq[deq.size()-1].y-1});
            }
        }else{
            ll x;
            scanf("%lld",&x);
            printf("%lld %lld\n",deq[deq.size()-x].x,deq[deq.size()-x].y);
        }
    }
    return 0;
}

需要注意：pair虽然方便但速度是没有struct结构体快的。

每次移动操作等价于删除数组末尾元素，在数组第一个位置插入当前头部位置坐标，可以用双端队列 $deque$来模拟这个过程

#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; // 注意deque 以 0 为起始编号
        }
    }
    return 0;
}