每日一题 - 240106 - C - Loong Tracking

• C - Loong Tracking

• TAG - $前缀和、坐标轴、重载运算符$
• 时间复杂度 - $O(M)$

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

const int N=1e6+7;
struct A{ 
    int x,y; 
    void operator += (A in) {
        x += in.x;
        y += in.y;
    }
}sum[N];
int idx;

void solve() {
    int n,m;
    scanf("%d%d",&n,&m );
    
    while( m-- ) {
        int op;
        scanf("%d",&op );

        if (op == 1) {
            char ch;
            scanf("%c%c",&ch,&ch );

            ++idx;
            switch(ch) {
                case 'R': sum[idx]+=sum[idx-1],sum[idx]+=(A){1,0}; break;
                case 'L': sum[idx]+=sum[idx-1],sum[idx]+=(A){-1,0}; break;
                case 'U': sum[idx]+=sum[idx-1],sum[idx]+=(A){0,1}; break;
                case 'D': sum[idx]+=sum[idx-1],sum[idx]+=(A){0,-1}; break;
            }
        } else {
            int ask;
            scanf("%d",&ask );

            bool f = ask - 1 >= idx ;
                        // 只需要左移：不需要前缀和数组 // 需要全部左移，还需要跟随头部：前缀和数组下标为 idx - (ask - 1)
            int t_idx = f ? 0 : idx - ask + 1 ;
                        // 只需要左移：x 轴方向上值为 -idx // 需要全部左移，还需要跟随头部：x 轴方向上值为 -(ask - 1) + 前缀和对应的 x 轴偏移量
            int dx = (f ? -idx : -(ask - 1)) + sum[t_idx].x ;
                        // 只需要左移，y 轴方向上不动 // 需要全部左移，还需要跟随头部：y 轴方向上值为前缀和对应的 y 轴偏移量
            int dy = sum[t_idx].y ;
            printf("%d %d\n",ask+dx,0+dy );
        }
    }
}

signed main() {
    int t=1;
    // scanf("%d",&t );
    while( t-- ) solve();
    return 0;
}

实现细节

• struct 重载运算符

参考示意图

• 无

参考链接

• 简谈 struct 运算符重载

作者 | 乐意奥AI