NO IMAGE

有一個外星人控制了你的大腦。一開始你處於原點(0,0)。外星人有一個由(R,U,D,L)組成的長度為M 的操作序列,分別代表(右,上,下,左)。

平面上有N 個關鍵點,每當外星人給出一個操作,你需要在這個方向上找到最近的一個關鍵點,並走到那個點上。保證輸入資料合法。

100%的資料,N,M≤100000,xi,yi≤200000。

這樣,我們搞2個權值線段樹,一個存橫座標一個存縱座標,每次查詢當前座標的前繼或者後續即可

複雜度O(mlgn)

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define M 200010
#define ls s[x].l
#define rs s[x].r
using namespace std;
struct nod{ int l,r,s; };
struct Tree{
nod s[3000000];
int rt[M<<1],c;
Tree(){ 
c=0; s[0]=(nod){0,0,0};
memset(rt,0,sizeof rt);
}
inline int newnode(){ return   c; }
void ps(int x){ s[x].s=s[ls].s s[rs].s; }
void insert(int l,int r,int& x,int p){
if(!x) x=newnode();
if(l==r){ s[x].s=1; return; }
int m=l r>>1;
if(p<=m) insert(l,m,ls,p);
else insert(m 1,r,rs,p);
ps(x);
}
int getmax(int l,int r,int x){
for(int m;l<r;){
m=l r>>1;
if(s[rs].s) { l=m 1; x=rs; }
else { r=m; x=ls; }
}
return l;
}
int getmin(int l,int r,int x){
for(int m;l<r;){
m=l r>>1;
if(s[ls].s) { r=m; x=ls; }
else { l=m 1; x=rs; }
}
return l;
}
int getpre(int l,int r,int x,int p){
if(l==r) return p;
int m=l r>>1,v;
if(p<=m) return getpre(l,m,ls,p);
else v=getpre(m 1,r,rs,p);
if(v!=p||!s[ls].s) return v;
else return getmax(l,m,ls);
}
int getsuc(int l,int r,int x,int p){
if(l==r) return p;
int m=l r>>1,v;
if(p>m) return getsuc(m 1,r,rs,p);
else v=getsuc(l,m,ls,p);
if(v!=p||!s[rs].s) return v;
else return getmin(m 1,r,rs);
}
void insert(int x,int y){ insert(1,M<<1,rt[x],y); }
int pre(int x,int y){ return getpre(1,M<<1,rt[x],y); }
int suc(int x,int y){ return getsuc(1,M<<1,rt[x],y); }
} rot,lin;
int n,m,x,y; char s[100010];
int main(){
freopen("tratincice.in","r",stdin);
freopen("tratincice.out","w",stdout);
scanf("%d%d",&n,&m);
rot.insert(M,M);
lin.insert(M,M);
for(int i=0;i<n;  i){
scanf("%d%d",&x,&y);
x =M; y =M;
rot.insert(x,y);
lin.insert(y,x);
}
x=y=M; scanf("%s",s);
for(int i=0;i<m;  i){
if(s[i]=='U') y=rot.suc(x,y);
if(s[i]=='D') y=rot.pre(x,y);
if(s[i]=='L') x=lin.pre(y,x);
if(s[i]=='R') x=lin.suc(y,x);
}
printf("%d %d\n",x-M,y-M);
}