luogu.com.cn/record/44833682

#include <stdio.h>
#include <string.h>
inline __int128 read()
{
	__int128 num=0;__int128 f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>=48&&c<=57)num=(num<<3)+(num<<1)+(c^48),c=getchar();
	return num*f;
}
#define int __int128 
				#define max(a,b) (a>b?a:b)
				#define min(a,b) (a<b?a:b)
inline int swap(int &a,int &b)
{
	int t=a;a=b,b=t;return 0;
}
__int128 n;
__int128 c[200005];
__int128 boom[200005][2];
inline void wt(int x)
{
	if(x>9)wt(x/10);
	putchar(x%10+48);
}
__int128 upd(__int128 sx,__int128 sy,__int128 ex,__int128 ey)
{
//	wt(sx);putchar(' ');wt(sy);putchar(' ');wt(ex);putchar(' ');wt(ey);putchar('\n');
	int ret=0;
	if(sx==ex)
	{
		__int128 t;
		if(sy>ey)t=sy,sy=ey,ey=t;
	//	printf("%lld\n",ey-sy);
		ret=ey-sy;
		for(__int128 i=0;i<n;i++)
		{
			if(boom[i][0]==sx&&sy<=boom[i][1]&&boom[i][1]<=ey)c[i]=1;
		}
	}
	else if(sy==ey)
	{
		__int128 t;
		if(sx>ex)t=sx,sx=ex,ex=t;
		//printf("%lld\n",ex-sx);
		ret=ex-sx;
		for(__int128 i=0;i<n;i++)
		{
			if(boom[i][1]==sy&&sx<=boom[i][0]&&boom[i][0]<=ex)c[i]=1;
		}
	}
	return ret;
}
signed main()
{
	n=read();
	for(__int128 i=0;i<n;i++)boom[i][0]=read(),boom[i][1]=read();
	__int128 sx=read(),sy=read(),ex=read(),ey=read();
	__int128 xs=2,ys=2,ans=0;__int128 r,cc;int q=0;
	while(1)
	{
		if(ex==sx&&ey==sy)break;
		if(ex>=sx&&ey>=sy)swap(ex,sx),swap(ey,sy),swap(xs,ys);
		if(ex==sx)
		{
			cc=sy/xs*xs;
			if(cc<=ey)
			{
				ans+=upd(sx,sy,sx,ey);
				break;
			}
		}
		else if(ey==sy)
		{
			r=sx/xs*xs;
			if(r<=ex)
			{
				ans+=upd(sx,sy,ex,sy);
				break;
			}
		}
		r=sx/xs*xs,cc=sy/xs*xs;
		ans+=upd(sx,sy,r,cc);sx=r,sy=cc;
		xs<<=1;q++;
	//	putchar('Q');wt(ans);puts("");
	//	printf("Q %lld\n",ans);
	}
wt(ans);puts("");
	for(__int128 i=0;i<n;i++)putchar(c[i]+48);
	return 0;
}

RT，思路是每次找到靠右的那个（找靠下的也行）那个往一个方块的左上角跳