我写一下这题怎么卡常吧（虽然我不算特别快，但是至少能过了）
1.加快读
2.cdq分治内用归并排序代替sort
3.当cdq分治区间右端点r<=n时，不用计算区间[l,mid]中的修改操作对[mid+1,r]中的询问操作的影响，因为[l,r]内都是修改操作(这样做快了好多啊)
4.树状数组清空时，如果当前清空的位置本身就为-INF，就不用继续清空下去，因为再往上要不就是没有被修改过，要不就是已经被修改成-INF了。
5.加快输似乎没有用（可能是我打的不好）

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int Read()
{
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    int t=c-'0'; c=getchar();
    while (c>='0'&&c<='9') t=t*10+c-'0',c=getchar();
    return t;
}
void Print(int x)
{
    if (x>=10) Print(x/10);
    putchar((x%10)|'0');
}
int n,m;
int maxn[1000005];
void add(int k,int t)
{
    for (int i=k;i<=1000001;i+=i&(-i)) maxn[i]=max(maxn[i],t);
}
int Suan(int k)
{
    int t=-2e9;
    for (int i=k;i;i-=i&(-i)) t=max(t,maxn[i]);
    return t;
}
void Clean(int k)
{
    for (int i=k;i<=1000001;i+=i&(-i))
    {
        if (maxn[i]==-2e9) break;
        maxn[i]=-2e9;
    }
}
struct Node
{
    int bh,t,x,y;
}a1[1000001],a2[1000001],t[1000001],tem[1000001];
int idx=0;
bool cmp1(const Node& t1,const Node& t2)
{
    if (t1.x!=t2.x) return t1.x<t2.x;
    else return t1.t<t2.t;
}
bool cmp2(const Node& t1,const Node& t2)
{
    if (t1.x!=t2.x) return t1.x<t2.x;
    else return t1.t>t2.t;
}
int ans[1000001];
void Solve(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    Solve(l,mid); Solve(mid+1,r);

    int t1=l,t2=mid+1,t3=l;
    while (t1<=mid&&t2<=r)
    {
        if (cmp1(a1[t1],a1[t2])) tem[t3++]=a1[t1],t1++;
        else tem[t3++]=a1[t2],t2++;
    }
    while (t1<=mid) tem[t3++]=a1[t1],t1++;
    while (t2<=r) tem[t3++]=a1[t2],t2++;
    for (int i=l;i<=r;i++) a1[i]=tem[i];

    t1=l,t2=mid+1,t3=l;
    while (t1<=mid&&t2<=r)
    {
        if (cmp2(a2[t1],a2[t2])) tem[t3++]=a2[t1],t1++;
        else tem[t3++]=a2[t2],t2++;
    }
    while (t1<=mid) tem[t3++]=a2[t1],t1++;
    while (t2<=r) tem[t3++]=a2[t2],t2++;
    for (int i=l;i<=r;i++) a2[i]=tem[i];

    if (r<=n) return;

    idx=0;
    for (int i=l;i<=r;i++)
    {
        if (tem[i].bh<=mid&&tem[i].t==1) t[++idx]=tem[i];
        else if (tem[i].bh>mid&&tem[i].t==2) t[++idx]=tem[i];
    }
    for (int i=1;i<=idx;i++)
    {
        if (t[i].t==1) add(t[i].y,t[i].x+t[i].y);
        else ans[t[i].bh]=min(ans[t[i].bh],t[i].x+t[i].y-Suan(t[i].y));
    }
    for (int i=1;i<=idx;i++) if (t[i].t==1) Clean(t[i].y);
    for (int i=1;i<=idx;i++)
    {
        if (t[i].t==1) add(1000002-t[i].y,t[i].x-t[i].y);
        else ans[t[i].bh]=min(ans[t[i].bh],t[i].x-t[i].y-Suan(1000002-t[i].y));
    }
    for (int i=1;i<=idx;i++) if (t[i].t==1) Clean(1000002-t[i].y);


    idx=0;
    for (int i=l;i<=r;i++)
    {
        if (tem[i].bh<=mid&&tem[i].t==1) t[++idx]=tem[i];
        else if (tem[i].bh>mid&&tem[i].t==2) t[++idx]=tem[i];
    }
    for (int i=idx;i>=1;i--)
    {
        if (t[i].t==1) add(t[i].y,-t[i].x+t[i].y);
        else ans[t[i].bh]=min(ans[t[i].bh],-t[i].x+t[i].y-Suan(t[i].y));
    }
    for (int i=idx;i>=1;i--) if (t[i].t==1) Clean(t[i].y);
    for (int i=idx;i>=1;i--)
    {
        if (t[i].t==1) add(1000002-t[i].y,-t[i].x-t[i].y);
        else ans[t[i].bh]=min(ans[t[i].bh],-t[i].x-t[i].y-Suan(1000002-t[i].y));
    }
    for (int i=idx;i>=1;i--) Clean(1000002-t[i].y);

}
int main()
{
    for (int i=1;i<=1000001;i++) maxn[i]=-2e9;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        a1[i].x=Read(); a1[i].y=Read(); a1[i].t=1; a1[i].bh=i;
        a1[i].x++; a1[i].y++;
    }
    for (int i=1;i<=m;i++)
    {
        a1[n+i].t=Read(); a1[n+i].x=Read(); a1[n+i].y=Read(); a1[n+i].bh=n+i;
        a1[n+i].x++; a1[n+i].y++;
    }
    for (int i=1;i<=n+m;i++) a2[i]=a1[i];
    for (int i=n+1;i<=n+m;i++) ans[i]=2e9;
    Solve(1,n+m);
    for (int i=n+1;i<=n+m;i++)
    {
        if (ans[i]!=2e9) Print(ans[i]),putchar('\n');
    }
    return 0;
}