首先考虑按照题意模拟 对于每只蚂蚁先二分找到离它最近的格点 然后模拟 复杂度$O(n^2)$

注意到蚂蚁的移动规则中较为麻烦的是转向操作 实际上 我们还会有很多情况会直行相当长的一段距离 两种情况混在一起 故考虑转化

对于网格图中一条长度为偶数的边，蚂蚁在经过它之后方向并不会发生改变 因此我们将这样的边合并到别的边上 将情况转化为每走完一条边都会转向

画图分析可得，蚂蚁的行动路线为一条折线

我们将折线中“一个横”+“一个竖”看做一个整体结构 发现可以将路线拆分为若干个这样的结构+一个不完整的结构

处理一个不完整的结构可以$O(1)$完成 对于完整的结构我们可以二分其数量 二分过程中结构总长度可以用前缀和处理复杂度$O(nlogn)$

我们需要先找到删边前离蚂蚁最近的格点位置 然后删边 再处理

这时候我们注意到 在合并长度为偶数的边后，蚂蚁所在的直线有可能会被删除 这时候如果直接再次二分找到最近的格点会导致方向混乱

所以我们记录蚂蚁的方向 删边后处理时 先让它严格（影响二分条件）地走一步，再二分找删边后最近的格点

代码比较抽象：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define mkp make_pair
#define psb push_back
#define bug cout<<"---\n";
#define pii pair<int,int>
#define ls(p) (p<<1)
#define rs(p) ((p<<1)|1)
#define ppb pop_back
#define ppf pop_front
#define psb push_back
const int inf=1e16,mod=1e9+7;
int n,m;
int lnx[1010000],lny[1010000],xtt,ytt;
int dsx[1010000],dsy[1010000];
int nx[1010000],ny[1010000];
struct Que{
	int qx,qy,qt,qn;
}que[1010000];
int sumx[1010000],sumy[1010000];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("data.in","r",stdin);
//	freopen("data.my","w",stdout);
//	system("fc ex.out ex.my");return 0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		char op;
		int x;
		cin>>op>>x;
		if(op=='x') lnx[++xtt]=x;
		else lny[++ytt]=x; 
	}
	lnx[++xtt]=inf;
	lny[++ytt]=inf;
	sort(lnx+1,lnx+xtt+1);
	sort(lny+1,lny+ytt+1);
	for(int i=1;i<xtt;i++){
		dsx[i]=lnx[i+1]-lnx[i];
		if(dsx[i]%2==1) nx[i]=i;
	}for(int i=1;i<ytt;i++){
		dsy[i]=lny[i+1]-lny[i];
		if(dsy[i]%2==1) ny[i]=i;
	}
	nx[xtt-1]=xtt-1;
	ny[ytt-1]=ytt-1;	
	for(int i=xtt-1;i>=1;i--){
		if(nx[i]==0) nx[i]=nx[i+1];
	}for(int i=ytt-1;i>=1;i--){
		if(ny[i]==0) ny[i]=ny[i+1];
	}
	
	int lx=0,ly=0;
	for(int i=1;i<=m;i++){
		int xx,yy,tt,nwt=0;
		cin>>xx>>yy>>tt;
		int l=1,r=xtt;
		while(l<r){
			int mid=(l+r)/2;
			if(lnx[mid]>=xx) r=mid;
			else l=mid+1;
		}
		if(lnx[l]-xx>=tt){
			que[i]={xx+tt,yy,0,0};
			continue;
		}else{
			lx=l;
			nwt=nwt+lnx[l]-xx;
			tt=tt-(lnx[l]-xx);
			xx=lnx[l];
		}l=1,r=ytt;
		while(l<r){
			int mid=(l+r)/2;
			if(lny[mid]>=yy) r=mid;
			else l=mid+1;
		}
		if(lny[l]-yy>=tt){
			que[i]={xx,yy+tt,0,0};
			continue;
		}else{
			ly=l;
			nwt=nwt+lny[l]-yy;
			tt=tt-(lny[l]-yy);
			yy=lny[l];
		}
		if(nwt%2==0){
			int toy=ny[ly];
			int dist=lny[toy]-lny[ly];
			if(dist>=tt){
				que[i]={xx,yy+tt,0,0};
				continue;
			}else{
				ly=toy;
				tt-=dist;
				yy+=dist;
				nwt^=dist;
			}
		}else{
			int tox=nx[lx];
			int dist=lnx[tox]-lnx[lx];
			if(dist>=tt){
				que[i]={xx+tt,yy,0,0};
				continue;
			}else{
				lx=tox;
				tt-=dist;
				xx+=dist;
				nwt^=dist;
			}
		}que[i]={xx,yy,tt,nwt%2};
	}
	for(int i=2;i<xtt;i++){
		if(lnx[i]%2==lnx[i-1]%2){
			lnx[i]=2*inf+lnx[i-1]%2;
		}
	}for(int i=2;i<ytt;i++){
		if(lny[i]%2==lny[i-1]%2){
			lny[i]=2*inf+lny[i-1]%2;
		}
	}
	sort(lnx+1,lnx+xtt+1);
	sort(lny+1,lny+ytt+1);
	while(lnx[xtt]>inf) xtt--;
	while(lny[ytt]>inf) ytt--;
	for(int i=1;i<xtt;i++){
		dsx[i]=lnx[i+1]-lnx[i];
		sumx[i]=sumx[i-1]+dsx[i];
	}for(int i=1;i<ytt;i++){
		dsy[i]=lny[i+1]-lny[i];
		sumy[i]=sumy[i-1]+dsy[i];
	}
	for(int i=1;i<=m;i++){
		int xx=que[i].qx,yy=que[i].qy,tt=que[i].qt,nwt=que[i].qn;
		
		if(tt==0){
			cout<<xx<<" "<<yy<<"\n";
			continue;
		}
		int l,r;
		if(nwt%2==0){
			l=1,r=ytt;
			while(l<r){
				int mid=(l+r)/2;
				if(lny[mid]>yy) r=mid;//注意这里
				else l=mid+1;
			}
			if(lny[l]-yy>=tt){
				cout<<xx<<" "<<yy+tt<<"\n";
				continue;
			}else{
				ly=l;
				nwt=nwt+lny[l]-yy;
				tt=tt-(lny[l]-yy);
				yy=lny[l];
			}l=1,r=xtt;
			while(l<r){
				int mid=(l+r)/2;
				if(lnx[mid]>=xx) r=mid;
				else l=mid+1;
			}
			if(lnx[l]-xx>=tt){
				cout<<xx+tt<<" "<<yy<<"\n";
				continue;
			}else{
				lx=l;
				nwt=nwt+lnx[l]-xx;
				tt=tt-(lnx[l]-xx);
				xx=lnx[l];
			}
		}else{
			l=1,r=xtt;
			while(l<r){
				int mid=(l+r)/2;
				if(lnx[mid]>xx) r=mid;//注意这里
				else l=mid+1;
			}
			if(lnx[l]-xx>=tt){
				cout<<xx+tt<<" "<<yy<<"\n";
				continue;
			}else{
				lx=l;
				nwt=nwt+lnx[l]-xx;
				tt=tt-(lnx[l]-xx);
				xx=lnx[l];
			}
			l=1,r=ytt;
			while(l<r){
				int mid=(l+r)/2;
				if(lny[mid]>=yy) r=mid;
				else l=mid+1;
			}
			if(lny[l]-yy>=tt){
				cout<<xx<<" "<<yy+tt<<"\n";
				continue;
			}else{
				ly=l;
				nwt=nwt+lny[l]-yy;
				tt=tt-(lny[l]-yy);
				yy=lny[l];
			}
		}
		l=-1,r=min(xtt-lx-1,ytt-ly-1);
		while(l<r){
			int delta=(l+r+1)/2;
			int val=sumx[lx+delta]-sumx[lx-1]+sumy[ly+delta]-sumy[ly-1];
			if(val<=tt) l=delta;
			else r=delta-1;
		}
		int val=sumx[lx+l]-sumx[lx-1]+sumy[ly+l]-sumy[ly-1];
		tt-=val;
		nwt^=val;
		lx=lx+l+1;ly=ly+l+1;
		xx=lnx[lx],yy=lny[ly];
		if(tt==0){
			cout<<xx<<" "<<yy<<"\n";
			continue;
		} 
		while(tt){
			if(nwt%2==0){
				if(dsy[ly]>=tt){
					cout<<xx<<" "<<yy+tt<<"\n";
					break;
				}else{
					yy=lny[ly+1];
					tt-=dsy[ly];
					nwt+=dsy[ly];
					ly++;
				}
			}else{
				if(dsx[lx]>=tt){
					cout<<xx+tt<<" "<<yy<<"\n";
					break;
				}else{
					xx=lnx[lx+1];
					tt-=dsx[lx];
					nwt+=dsx[lx]; 
					lx++;
				}
			}
		}
	}
	return 0;
}

复杂度$O(nlogn)$ 快快出加强版