题解

暴力就不说了。

注意到每一次移动，只会在横坐标与纵坐标之间的一个修改，而且障碍的坐标不变。所以考虑统计每一个 $x$ 坐标所对应的 $y$ 坐标们，以及 $y$ 坐标所对应的 $x$ 坐标们。

由于值域巨大，使用 $\texttt{map}$ 存储。

现在我们进行操作。如果我们碰不到障碍，直接修改坐标就好了；如果碰到障碍了，那么我们一定是碰到了第一个在路上的障碍。明显的二分。

随便调一下，然后就过了。

时间复杂度：$O((n+m) \log^2n)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
const ll MAXN=2e5+25,INF=1ll<<60;
ll n,m,c,t,posx,posy;
char op;
ll x[MAXN],y[MAXN];
map<ll,vector<ll>> mpa,mpb;
inline ll bfind(const vector<ll> &a,const ll &x,const ll &op){
    ll ans=-1,l=0,r=a.size();
    r--;
    if(op==0){
        while(l<=r){
            ll mid=l+r>>1;
            if(a[mid]>=x){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        if(ans==-1) return INF;
        return a[ans];
    }
    if(op==1){
        while(l<=r){
            ll mid=l+r>>1;
            if(a[mid]<=x){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(ans==-1) return -INF;
        return a[ans];
    }
    if(op==2){
        while(l<=r){
            ll mid=l+r>>1;
            if(a[mid]<=x){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(ans==-1) return -INF;
        return a[ans];
    }
    while(l<=r){
        ll mid=l+r>>1;
        if(a[mid]>=x){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    if(ans==-1) return INF;
    return a[ans];
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        mpa[x[i]].eb(y[i]);
        mpb[y[i]].eb(x[i]);
    }
    for(auto &it:mpa) sort(it.second.begin(),it.second.end());
    for(auto &it:mpb) sort(it.second.begin(),it.second.end());
    while(m--){
        cin>>op>>c;
        if(op=='w'){
            t=bfind(mpa[posx],posy,0);
            if(t<=posy+c) posy=t-1;
            else posy+=c;
        }
        else if(op=='d'){
            t=bfind(mpa[posx],posy,1);
            if(t>=posy-c) posy=t+1;
            else posy-=c;
        }
        else if(op=='l'){
            t=bfind(mpb[posy],posx,2);
            if(t>=posx-c) posx=t+1;
            else posx-=c;
        }
        else{
            t=bfind(mpb[posy],posx,3);
            if(t<=posx+c) posx=t-1;
            else posx+=c;
        }
    }
    cout<<posx<<' '<<posy;
    return 0;
}