题目描述

有一个边长为 $m$的正方形，其中有 $n$个箭头，每个箭头从 $(x_1,y_1)$指向 $(x_2,y_2)$（保证满足 $x_1=x_2$或 $y_1=y_2$，没有相交的箭头）。有 $Q$个人，每个人有一个起点和一个初始朝向，每一个单位时间，他们就会向自己的朝向移动一个单位长度，如果碰到了箭头，就会有一股神奇的力量使得 TA 转而朝向箭头指的方向。

第 $i$个人运动 $t_i$个单位时间就会停下，问你每个人最终是在哪里停下的。如果 TA 走出了正方形，就输出 TA 还待在正方形中时的最后一个位置。

数据范围

$m,n,Q \leq 10^5,t_i \leq 10^{15}$

题目分析

我们肯定想要知道，从一个箭头/人继续往前走，会先走到哪个箭头。这个的话，我们可以对每个朝向的箭头（并将朝同一个方向的人加进来）做一次扫描线。打个比方，我们要找朝左的箭头可以到的下一个朝向不同的箭头（如果到的下一个箭头朝向还是相同，没意义 QvQ），那么我们就把所有箭头按照开始位置的 $x$坐标从小到大排序，然后依次处理，对于不是朝左的箭头，我们在线段树里将其 y 坐标覆盖的范围染色。对于朝左的箭头，我们去线段树里寻找其 y 坐标处的颜色，确定它下一个到哪个箭头。

然后使用倍增，处理一下从每个箭头走 $2^j$步会走到哪个箭头，从当前箭头的头部走到第 $2^j$个箭头的头部要走多久。

最后处理询问，这个按照倍增的套路暴力搞一搞就可以了。不过注意一下一个人本来就在箭头上的情况……

实际上这题还是很简单的，可惜我太蠢了考场没有想出来╮(╯▽╰)╭

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read() {
    LL q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+(LL)(ch-'0'),ch=getchar();
    return q;
}
const int N=100005;
int n,m,Q,tot;
struct node{int x,y,l,r,bj,id;}a[N<<1];
int X1[N],Y1[N],X2[N],Y2[N],X0[N],Y0[N];char arr[N],gt[N];
int nxt[N<<1][50],c[N<<2];LL dis[N<<1][50],ti[N];//17

void build(int s,int t,int i) {
    c[i]=0;if(s==t) return;
    int mid=(s+t)>>1;
    build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
}
void pd(int i) {c[i<<1]=c[(i<<1)|1]=c[i],c[i]=0;}
void chan(int l,int r,int s,int t,int i,int num) {
    if(l<=s&&t<=r) {c[i]=num;return;}
    int mid=(s+t)>>1;
    if(c[i]) pd(i);
    if(l<=mid) chan(l,r,s,mid,i<<1,num);
    if(mid+1<=r) chan(l,r,mid+1,t,(i<<1)|1,num);
    if(c[i<<1]==c[(i<<1)|1]) c[i]=c[i<<1];
}
int query(int x,int s,int t,int i) {
    if(c[i]||s==t) return c[i];
    int mid=(s+t)>>1;
    if(x<=mid) return query(x,s,mid,i<<1);
    else return query(x,mid+1,t,(i<<1)|1);
}

int cmp(node s1,node s2) {return s1.x==s2.x?s1.bj<s2.bj:s1.x<s2.x;}
void solve() {
    sort(a+1,a+1+tot,cmp),build(1,m,1);
    for(int i=1;i<=tot;++i)
        if(a[i].bj==0) chan(a[i].l,a[i].r,1,m,1,a[i].id);
        else nxt[a[i].id][0]=query(a[i].y,1,m,1);
}
void workL() {//朝左的箭头
    tot=0;
    for(int i=1;i<=n;++i)
        if(arr[i]=='L') a[++tot]=(node){X1[i],Y1[i],0,0,1,i};
        else a[++tot]=(node){X1[i],0,min(Y1[i],Y2[i]),max(Y1[i],Y2[i]),0,i};
    for(int i=1;i<=Q;++i)
        if(gt[i]=='L') a[++tot]=(node){X0[i],Y0[i],0,0,1,i+n};
    solve();
}
void workR() {//朝右的箭头
    tot=0;
    for(int i=1;i<=n;++i)
        if(arr[i]=='R') a[++tot]=(node){-X1[i],Y1[i],0,0,1,i};
        else a[++tot]=(node){-X1[i],0,min(Y1[i],Y2[i]),max(Y1[i],Y2[i]),0,i};
        //将所有的 x 坐标取相反数，相当于从大到小排序，节省代码量
    for(int i=1;i<=Q;++i)
        if(gt[i]=='R') a[++tot]=(node){-X0[i],Y0[i],0,0,1,i+n};
    solve();
}
void workD() {//朝下的箭头
    tot=0;
    for(int i=1;i<=n;++i)
        if(arr[i]=='D') a[++tot]=(node){Y1[i],X1[i],0,0,1,i};
        else a[++tot]=(node){Y1[i],0,min(X1[i],X2[i]),max(X1[i],X2[i]),0,i};
        //将关键词 x 和关键词 y 交换一下，也是减小代码量的
    for(int i=1;i<=Q;++i)
        if(gt[i]=='D') a[++tot]=(node){Y0[i],X0[i],0,0,1,i+n};
    solve();
}
void workU() {//朝上的箭头
    tot=0;
    for(int i=1;i<=n;++i)
        if(arr[i]=='U') a[++tot]=(node){-Y1[i],X1[i],0,0,1,i};
        else a[++tot]=(node){-Y1[i],0,min(X1[i],X2[i]),max(X1[i],X2[i]),0,i};
    for(int i=1;i<=Q;++i)
        if(gt[i]=='U') a[++tot]=(node){-Y0[i],X0[i],0,0,1,i+n};
    solve();
}

void pre() {
    for(int i=1;i<=n;++i)
        if(nxt[i][0])
        dis[i][0]=abs(Y2[nxt[i][0]]-Y2[i])+abs(X2[nxt[i][0]]-X2[i]);
    for(int i=1;i<=Q;++i)
        if(nxt[i+n][0])
        dis[i+n][0]=abs(Y2[nxt[i+n][0]]-Y0[i])+abs(X2[nxt[i+n][0]]-X0[i]);
    for(int j=1;j<=49;++j)//伟大的倍增
        for(int i=1;i<=n+Q;++i)
        nxt[i][j]=nxt[nxt[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[nxt[i][j-1]][j-1];
}
void print(char fx,LL tt,LL x,LL y) {
    if(fx=='L') printf("%lld %lld\n",max(1LL,x-tt)-1,y-1);
    else if(fx=='R') printf("%lld %lld\n",min((LL)m,x+tt)-1,y-1);
    else if(fx=='D') printf("%lld %lld\n",x-1,max(1LL,y-tt)-1);
    else printf("%lld %lld\n",x-1,min((LL)m,y+tt)-1);
}
void walk() {
    int kx,ky,to,kjl;
    for(int i=1;i<=Q;++i) {
        if(!nxt[i+n][0]) {print(gt[i],ti[i],X0[i],Y0[i]);continue;}
        int now=i+n;LL tt=ti[i];
        for(int j=49;j>=0;--j)
            if(tt>=dis[now][j]&&nxt[now][j]) tt-=dis[now][j],now=nxt[now][j];
        if(!nxt[now][0]) {print(arr[now],tt,X2[now],Y2[now]);continue;}
        char ch=(now<=n?arr[now]:gt[now-n]);
        int x1=(now<=n?X1[now]:X0[now-n]),x2=(now<=n?X2[now]:X0[now-n]);
        int y1=(now<=n?Y1[now]:Y0[now-n]),y2=(now<=n?Y2[now]:Y0[now-n]);
        to=nxt[now][0];
        if(now>n&&x1>=min(X1[to],X2[to])&&x1<=max(X1[to],X2[to])
            &&y1>=min(Y1[to],Y2[to])&&y1<=max(Y1[to],Y2[to])) kx=x1,ky=y1;//特判人本来就在箭头上
        else if(ch=='L') ky=y1,kx=max(X1[to],X2[to]);
        else if(ch=='R') ky=y1,kx=min(X1[to],X2[to]);
        else if(ch=='D') kx=x1,ky=max(Y1[to],Y2[to]);
        else kx=x1,ky=min(Y1[to],Y2[to]);//寻找当前箭头走到下一箭头，落到的位置
        kjl=abs(kx-x2)+abs(ky-y2);//走到下一箭头要走的时间
        if(kjl>tt) print(ch,tt,x2,y2);
        else print(arr[to],tt-kjl,kx,ky);//还可以沿着下一箭头走
    }
}
int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=read(),m=read()+1;char ch[10];
    for(int i=1;i<=n;++i) {
        X1[i]=read()+1,Y1[i]=read()+1,X2[i]=read()+1,Y2[i]=read()+1;
        if(Y1[i]==Y2[i]&&X1[i]>X2[i]) arr[i]='L';
        else if(Y1[i]==Y2[i]&&X1[i]<X2[i]) arr[i]='R';
        else if(X1[i]==X2[i]&&Y1[i]>Y2[i]) arr[i]='D';
        else arr[i]='U';
    }
    Q=read();
    for(int i=1;i<=Q;++i)
        X0[i]=read()+1,Y0[i]=read()+1,scanf("%s",ch),gt[i]=ch[0],ti[i]=read();
    workL(),workR(),workD(),workU(),pre(),walk();
    return 0;
}