题目描述

给定一个包含 $n$ 个点的序列，第 $i$ 个点的坐标为 $(a_i, b_i)$ 。

共有 $q$ 次询问，每次询问一个区间 $[l, r]$ ，你需要求出下面式子的值。

$$\min_{i=l}^r \min_{j=i+1}^r (\|a_i - a_j\| + \|b_i - b_j\|)$$

保证序列中点的坐标和询问区间在指定范围内用指定方式随机生成。

输入格式

第一行输入两个正整数 $n, q$ 。

接下来 $n$ 行，每行输入两个整数 $a_i, b_i$ ，表示第 $i$ 个点的坐标为 $(a_i, b_i)$ 。

接下来 $q$ 行，每行输入两个正整数 $l, r$ ，表示询问区间 $[l, r]$ 。

输出格式

输出 $q$ 行，每行包含一个非负整数，表示答案。

样例一输入

4 5
1 1
2 2
1 2
2 1
1 4
1 3
1 2
2 3
3 4

样例一输出

1
1
2
1
2

样例二

见下发文件下的 geo2.in 与 geo2.ans 。

该样例约束与测试点 $2$ 一致。

样例三

见下发文件下的 geo3.in 与 geo3.ans 。

该样例约束与测试点 $18$ 一致。

下发文件

本题下发的文件除三个样例外还有 rand.cpp 。

rand.cpp 是一个数据生成器，与生成评测用例的数据生成器仅有随机种子不同。

输入 $n, q, A, B$ 后数据生成器才可生成整个数据，数据输出到 geo.in ，其中 $A, B$ 分别表示 $\|a_i\|$ 与 $\|b_i\|$ 的上界。

数据范围

对于所有测试点， $2 \le n \le 10^6$ ， $1 \le q \le 10^6$ ， $\|a_i\|, \|b_i\| \le 10^9$ ， $1 \le l < r \le n$ ，保证 $a_i, b_i, l, r$ 在指定范围内用指定方式随机生成。

测试点表格

对于每一档部分分，设其测试点编号范围为 $l \sim r$ ，则测试点 $l+1 \sim r-1$ 满足 $\|a_i\|, \|b_i\| \le 10^6$ ，测试点 $\lfloor \frac{l+r}{2} \rfloor + 1 \sim r$ 满足 $b_i = 0$ 。

提示

本题输入输出规模较大，请使用较为快速的输入输出方式。

#include <iostream>
#include <random>
using namespace std;
mt19937_64 Rand('C'^'h'^'e'^'r'^'i'^'s'^'h'^'e'^'d');
#define rand Rand
int main() {
    freopen("geo.in", "w", stdout);
    ios::sync_with_stdio(false);
    int n, q, A, B;
    cin >> n >> q >> A >> B;
    cout << n << " " << q << '\n';

    for (int i = 1; i <= n; i++) {
        cout << int(rand() % ((A << 1) + 1)) - A << " "
             << int(rand() % ((B << 1) + 1)) - B << '\n';
    }

    for (int i = 1; i <= q; i++) {
        int L = rand() % (n - 1) + 2, l = rand() % (n - L + 1) + 1;
        cout << l << " " << l + L - 1 << '\n';
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,q,a[1001001],b[1001001],ans[1001001];
int ls[1001001],rs[1001001];
void solve(vector<int>&u,vector<int>&v){
    if(v.size()==0||u.size()<2)return ;
    // cout<<u.size()<<"~~~"<<v.size()<<"\n";
    // for (auto i:u)cout<<i<<" "<<a[i]<<" "<<b[i],cout<<"\n";
    // for (auto i:v)cout<<ls[i]<<"&"<<rs[i],cout<<"\n";
    int n=u.size();
    int mn=1e18,l,r;
    for (int i=0;i<n;i++)
    for (int j=i+1;j<=i+10&&j<n;j++){
        int tmp=abs(a[u[i]]-a[u[j]])+abs(b[u[i]]-b[u[j]]);
        if(tmp<mn)mn=tmp,l=u[i],r=u[j];
    }
    if(l>r)swap(l,r);
    // cout<<l<<"$$"<<r<<"\n";
    vector<int>ul,ur,vl,vr;
    for (auto i:u){
        if(i<r)ul.push_back(i);
        if(l<i)ur.push_back(i);
    }
    for (auto i:v){
        if(ls[i]<=l&&r<=rs[i])ans[i]=mn;
        else {
            if(rs[i]<r)vl.push_back(i);
            else vr.push_back(i);
        }
    }
    solve(ul,vl);solve(ur,vr);
}
bool cmp(int x,int y){
    return a[x]<a[y]||(a[x]==a[y]&&b[x]<b[y]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    vector<int>u,v;
    for (int i=1;i<=n;i++)
    cin>>a[i]>>b[i],u.push_back(i);
    sort(u.begin(),u.end(),cmp);
    for (int i=1;i<=q;i++)
    v.push_back(i),cin>>ls[i]>>rs[i],ans[i]=0;
    solve(u,v);
    for (int i=1;i<=q;i++)
    cout<<ans[i]<<"\n";
}