rt，使用cdq分治做本题时先用的sort对某操作区间进行排序。结果发现又WA又TLE。准备先改到只有超时之后再优化算法，结果一直调不出。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define orz cout<<"lytcltcltcltcltcltcl"<<endl
inline int r(){int s=0,k=1;char c=getchar();while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}while(isdigit(c)){s=s*10+c-'0';c=getchar();}return s*k;}
int n,m,c[2500005],cnt;
const int mx=1000005;
struct dot
{
	int x,y;
}a[1000001];
struct asks
{
	int opt,x,y,ans,bh;
}t[1000001],f[1000001];
bool cmp(asks x,asks y)
{
	return x.x<y.x;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int y)
{
	for(;x<=2e6+15;x+=lowbit(x))
	c[x]=max(c[x],y);
}
void del(int x)
{
	for(;x<=2e6+15;x+=lowbit(x))
	c[x]=0;
}
int sum(int x)
{
	int s=0;
	for(;x;x-=lowbit(x))
	s=max(s,c[x]);
	return s?s:-1e9;
}
void solve(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	for(int i=l;i<=r;i++)f[i]=t[i];
	sort(f+l,f+r+1,cmp);
	for(int i=l;i<=r;i++)
	{
		if(f[i].opt==1)
		{
			if(f[i].bh<=mid)add(f[i].y,f[i].x+f[i].y);
		}
		else if(f[i].bh>mid)
		{
//			cout<<"find?\n";
			int x=f[i].x,y=f[i].y,bh=f[i].bh;
//			cout<<x<<" "<<y<<" "<<endl;
			t[bh].ans=min(t[bh].ans,x+y-sum(y));
		}
	}
	for(int i=l;i<=r;i++)
		if(f[i].opt==1&&f[i].bh<=mid)
			del(f[i].y);
}
int main()
{
	n=r();m=r();
	for(int i=1;i<=n;i++)
	{
		t[++cnt].opt=1;
		t[cnt].x=r()+mx;
		t[cnt].y=r()+mx;
	}
	for(int i=1;i<=m;i++)
	{
		t[++cnt].opt=r();
		t[cnt].x=r()+mx;
		t[cnt].y=r()+mx;
		t[cnt].ans=1e9;
		t[cnt].bh=cnt;
	}
	m=cnt;
	
	solve(1,m);
	
	for(int i=1;i<=m;i++)t[i].x=mx+mx-t[i].x;
	solve(1,m);
	for(int i=1;i<=m;i++)t[i].x=mx+mx-t[i].x;
	
	for(int i=1;i<=m;i++)t[i].y=mx+mx-t[i].y;
	solve(1,m);
	
	for(int i=1;i<=m;i++)t[i].x=mx+mx-t[i].x;
	solve(1,m);
	
	for(int i=1;i<=m;i++)
	if(t[i].opt==2)printf("%d\n",t[i].ans);
}

然后把sort改成merge归并排序就直接A了？？？求问各位dalao这是为什么？？？？？

merge的代码如下：

#include<bits/stdc++.h>
using namespace std;
#define orz cout<<"lytcltcltcltcltcltcl"<<endl
inline int r(){int s=0,k=1;char c=getchar();while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}while(isdigit(c)){s=s*10+c-'0';c=getchar();}return s*k;}
int n,m,c[2500005],cnt;
const int mx=1000005;
struct dot
{
	int x,y;
}a[1000001];
struct asks
{
	int opt,x,y,ans,bh;
}t[1000001],f[1000001],cp[1000001];
bool cmp(asks x,asks y)
{
	return x.x<y.x;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int y)
{
	for(;x<=2e6+15;x+=lowbit(x))
	c[x]=max(c[x],y);
}
void del(int x)
{
	for(;x<=2e6+15;x+=lowbit(x))
	c[x]=0;
}
int sum(int x)
{
	int s=0;
	for(;x;x-=lowbit(x))
	s=max(s,c[x]);
	return s?s:-1e9;
}
void solve(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	merge(f+l,f+mid+1,f+mid+1,f+r+1,cp+l,cmp);
	for(int i=l;i<=r;i++)f[i]=cp[i];
	for(int i=l;i<=r;i++)
	{
		if(f[i].opt==1)
		{
			if(f[i].bh<=mid)add(f[i].y,f[i].x+f[i].y);
		}
		else if(f[i].bh>mid)
		{
//			cout<<"find?\n";
			int x=f[i].x,y=f[i].y,bh=f[i].bh;
//			cout<<x<<" "<<y<<" "<<endl;
			t[bh].ans=min(t[bh].ans,x+y-sum(y));
		}
	}
	for(int i=l;i<=r;i++)
		if(f[i].opt==1&&f[i].bh<=mid)
			del(f[i].y);
}
int main()
{
	n=r();m=r();
	for(int i=1;i<=n;i++)
	{
		t[++cnt].opt=1;
		t[cnt].x=r()+mx;
		t[cnt].y=r()+mx;
	}
	for(int i=1;i<=m;i++)
	{
		t[++cnt].opt=r();
		t[cnt].x=r()+mx;
		t[cnt].y=r()+mx;
		t[cnt].ans=1e9;
		t[cnt].bh=cnt;
	}
	m=cnt;
	for(int i=1;i<=m;i++)f[i]=t[i];
	solve(1,m);
	
	for(int i=1;i<=m;i++)t[i].x=mx+mx-t[i].x;
	for(int i=1;i<=m;i++)f[i]=t[i];
	solve(1,m);
	for(int i=1;i<=m;i++)t[i].x=mx+mx-t[i].x;
	
	for(int i=1;i<=m;i++)t[i].y=mx+mx-t[i].y;
	for(int i=1;i<=m;i++)f[i]=t[i];
	solve(1,m);
	
	for(int i=1;i<=m;i++)t[i].x=mx+mx-t[i].x;
	for(int i=1;i<=m;i++)f[i]=t[i];
	solve(1,m);
	
	for(int i=1;i<=m;i++)
	if(t[i].opt==2)printf("%d\n",t[i].ans);
}