和箭头一起游走（主席树+倍增）

$n,m,q<=1e5,T<=1e15$n,m,q<=1e5,T<=1e15
题目保证箭头不会相交。

一道不卡精度的计算几何
发现一个箭头上的人只会走到另一个确定的箭头上或走出去，
那么我们可以把这个走的关系建成图。
求出每一步的距离后即可分三类简单讨论得到终点坐标。
对于$T<=1e15$T<=1e15我们可以倍增跳步。
但是我们还要写点定位。。。。。。（求出方向上下一条边）。
所以我们写主席树。
400行的标程真是把我看吐了，强行离线徒增代码长度
$\rm AC \ Code$AC Code

#include<bits/stdc++.h>
#define maxn 100005
#define lim 60
#define maxp maxn * 160
#define pb push_back
#define inf ((LL)(1e16))
#define mp make_pair
#define LL long long
#define pii pair<int,int>
using namespace std;

int n,m,q;
int p1[maxn][2],p2[maxn][2];
int rt[4][maxn],lc[maxp],rc[maxp],tg[maxp],tim[maxp],tot;
int mAp[300];
vector<int>G[2][maxn];

void ins(int &u,int l,int r,int ql,int qr,int id,int ti){
	if(l>qr||ql>r) return;
	lc[++tot]=lc[u],rc[tot]=rc[u],tg[tot]=tg[u],tim[tot]=tim[u];
	u=tot;
	if(ql<=l&&r<=qr){
		tg[u] = id , tim[u] = ti;
		return;
	}
	int mid = (l+r) >> 1;
	ins(lc[u],l,mid,ql,qr,id,ti),ins(rc[u],mid+1,r,ql,qr,id,ti);
}

int f[lim][maxn],apr[maxn],dir[maxn];
LL g[lim][maxn];
pii qry(int u,int l,int r,int p){
	if(!u) return mp(0,0);
	if(l==r) return mp(tim[u],tg[u]);
	int mid = (l+r) >> 1;
	if(p<=mid) return max(qry(lc[u],l,mid,p),mp(tim[u],tg[u]));
	return max(qry(rc[u],mid+1,r,p),mp(tim[u],tg[u]));
}

int main(){
	mAp[(int)'L'] = 0;
	mAp[(int)'R'] = 1;
	mAp[(int)'D'] = 2;
	mAp[(int)'U'] = 3;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&p1[i][0],&p1[i][1],&p2[i][0],&p2[i][1]);
		if(p1[i][0] == p2[i][0]) G[0][p2[i][0]].pb(i),G[1][p2[i][1]].pb(i),G[1][p1[i][1]].pb(i),dir[i]=2+(p2[i][1]>p1[i][1]);
		else G[1][p2[i][1]].pb(i),G[0][p2[i][0]].pb(i),G[0][p1[i][0]].pb(i),dir[i]=(p2[i][0]>p1[i][0]);
	}
	for(int t=0;t<2;t++){
		for(int i=0;i<=m;i++){
			if(i) rt[2*t][i] = rt[2*t][i-1];
			for(int j=G[t][i].size()-1;j>=0;j--)
				ins(rt[2*t][i],0,m,min(p1[G[t][i][j]][t^1],p2[G[t][i][j]][t^1]),max(p1[G[t][i][j]][t^1],p2[G[t][i][j]][t^1]),G[t][i][j],i+1);
		}
		for(int i=m;i>=0;i--){
			rt[2*t+1][i] = rt[2*t+1][i+1];
			for(int j=G[t][i].size()-1;j>=0;j--)
				ins(rt[2*t+1][i],0,m,min(p1[G[t][i][j]][t^1],p2[G[t][i][j]][t^1]),max(p1[G[t][i][j]][t^1],p2[G[t][i][j]][t^1]),G[t][i][j],m-i+1);
		}
	}
	for(int i=1;i<=n;i++)
		if(p1[i][0] == p2[i][0]){
			pii r = qry(rt[p1[i][1] < p2[i][1] ? 3 : 2][p2[i][1]+(p1[i][1] < p2[i][1] ? 1 : -1)],0,m,p1[i][0]);
			f[0][i] = r.second , apr[i] = abs(p2[r.second][1] - p2[i][1]) , g[0][i] = apr[i] + abs(p2[r.second][0]-p2[i][0]);
			if(r.second == 0)
				apr[i] = g[0][i] = (p1[i][1] < p2[i][1] ? m-p2[i][1] : p2[i][1]);
		}
		else{
			pii r = qry(rt[p1[i][0] < p2[i][0] ? 1 : 0][p2[i][0]+(p1[i][0] < p2[i][0] ? 1 : -1)],0,m,p1[i][1]);
			f[0][i] = r.second , apr[i] = abs(p2[r.second][0] - p2[i][0]) , g[0][i] = apr[i] + abs(p2[r.second][1]-p2[i][1]);
			if(r.second == 0)
				apr[i] = g[0][i] = (p1[i][0] < p2[i][0] ? m-p2[i][0] : p2[i][0]);
		}
	for(int j=1;j<lim;j++)
		for(int i=1;i<=n;i++) 
			f[j][i] = f[j-1][f[j-1][i]] , 
			g[j][i] = g[j-1][i] + g[j-1][f[j-1][i]];
	scanf("%d",&q);
	for(LL a[2];q--;){
		scanf("%lld%lld",&a[0],&a[1]);
		char ch[2];scanf("%s",ch);
		int D = mAp[ch[0]];
		LL T;scanf("%lld",&T);
		pii r = qry(rt[D][a[D/2]],0,m,a[D/2^1]);
		if(r.second && p2[r.second][D/2]^p1[r.second][D/2] && 
			(min(p1[r.second][D/2],p2[r.second][D/2]) <= a[D/2]) && 
			(max(p1[r.second][D/2],p2[r.second][D/2]) >= a[D/2]) )
			D=dir[r.second];
		if(r.second && T<=abs(p2[r.second][D/2]-a[D/2])){
			a[D/2] += (D&1?T:-T);
			printf("%lld %lld\n",a[0],a[1]);
			continue;
		}
		if(r.second && T<=abs(p2[r.second][0]-a[0])+abs(p2[r.second][1]-a[1])){
			T -= abs(p2[r.second][D/2]-a[D/2]) , a[D/2] = p2[r.second][D/2];
			a[dir[r.second]/2] += (p2[r.second][dir[r.second]/2] - p1[r.second][dir[r.second]/2]) / abs(p2[r.second][dir[r.second]/2] - p1[r.second][dir[r.second]/2]) * T; 
			printf("%lld %lld\n",a[0],a[1]);
			continue;
		}
		if(!r.second){
			a[D/2] += (D&1?T:-T);
			a[D/2] = max(min(a[D/2] , (LL)m) , 0ll);
			printf("%lld %lld\n",a[0],a[1]);
			continue;
		}
		T -= abs(p2[r.second][0]-a[0])+abs(p2[r.second][1]-a[1]);
		int u = r.second;
		for(int i=lim-1;i>=0;i--)
			if(g[i][u] <= T && f[i][u])
				T-=g[i][u],u=f[i][u];
		if(!f[0][u]){
			a[0] = p2[u][0] , a[1] = p2[u][1];
			a[dir[u]/2] += (dir[u]&1?T:-T);
			a[dir[u]/2] = max(min(a[dir[u]/2] , (LL)m) , 0ll);
			printf("%lld %lld\n",a[0],a[1]);
			continue;
		}
		if(T<=apr[u]){
			a[0] = p2[u][0] , a[1] = p2[u][1];
			a[dir[u]/2] += (dir[u]&1?T:-T);
			printf("%lld %lld\n",a[0],a[1]);
			continue;
		}
		int v = f[0][u];
		a[0] = p2[u][0] , a[1] = p2[u][1];
		a[dir[u]/2] = p2[v][dir[u]/2];
		a[dir[v]/2] += (p2[v][dir[v]/2]-p1[v][dir[v]/2])/abs(p2[v][dir[v]/2]-p1[v][dir[v]/2])*(T-apr[u]);
		printf("%lld %lld\n",a[0],a[1]);
	}
}