NAIPC2018-K-Zoning Houses

题目描述

Given a registry of all houses in your state or province, you would like to know the minimum size of an axis-aligned square zone such that every house in a range of addresses lies in the zone or on its border. The zoning is a bit lenient and you can ignore any one house from the range to make the zone smaller.
The addresses are given as integers from 1..n. Zoning requests are given as a consecutive range of houses. A valid zone is the smallest axis-aligned square that contains all of the points in the range,ignoring at most one.
Given the (x, y) locations of houses in your state or province, and a list of zoning requests, you must figure out for each request: What is the length of a side of the smallest axis-aligned square zone that contains all of the houses in the zoning request, possibly ignoring one house?

输入

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line containing two integers n and q (1 ≤ n, q ≤ 105 ), where n is the number of houses, and q is the number of zoning requests.
The next n lines will each contain two integers, x and y (−109 ≤ x, y ≤ 109 ), which are the (x,y) coordinates of a house in your state or province. The address of this house corresponds with the order in the input. The ﬁrst house has address 1, the second house has address 2, and so on. No two houses will be at the same location.
The next q lines will contain two integers a and b (1 ≤ a < b ≤ n), which represents a zoning request for houses with addresses in the range [a..b] inclusive.

输出

Output q lines. On each line print the answer to one of the zoning requests, in order: the side length of the smallest axis-aligned square that contains all of the points of houses with those addresses, if at most one house can be ignored.

样例输入

样例输出

1
0

给出n个点的坐标和q个询问。每个询问给出一段区间[l,r]，找出一个最小的中心在原点的正方形使得包含区间内所有的点，但是可以忽略区间内的一个点.


如果不考虑忽略一个点的话每次询问只要找出区间内点的最大最小横纵坐标就可以。忽略一个点一定优于或等于不忽略，所以直接考虑忽略哪个点。需要考虑的最多只有四个点，横坐标最大，横坐标最小，纵坐标最大，纵坐标最小。
所以对每次询问，求删掉横坐标最大，横坐标最小，纵坐标最大，纵坐标最小的点之后的答案，取最小的那个即可

线段树被卡常了qwq，写了ST还得加读入优化才能过，就很难受

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N=2e5;
const int INF=2e9;
P xmx[N][20],xmi[N][20],ymx[N][20],ymi[N][20];
int n,m,x,y,ans;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void ST(int n)
{
    for (int j=1;(1<<j)<=n;j++)
    {
        for (int i=1;i+(1<<j)-1<=n;i++)
        {
            xmi[i][j]=min(xmi[i][j-1],xmi[i+(1<<(j-1))][j-1]);
            ymi[i][j]=min(ymi[i][j-1],ymi[i+(1<<(j-1))][j-1]);
            xmx[i][j]=max(xmx[i][j-1],xmx[i+(1<<(j-1))][j-1]);
            ymx[i][j]=max(ymx[i][j-1],ymx[i+(1<<(j-1))][j-1]);
        }
    }
}
P RMQ(int l,int r,int t)
{
    if (l>r)
    {
        if (t==1||t==3) return P(INF,0);
        else return P(-INF,0);
    }
    int k=0;
    while ((1<<(k+1))<=r-l+1) k++;
    if (t==1) return min(xmi[l][k],xmi[r-(1<<k)+1][k]);
    else if (t==2) return max(xmx[l][k],xmx[r-(1<<k)+1][k]);
    else if (t==3) return min(ymi[l][k],ymi[r-(1<<k)+1][k]);
    else if (t==4) return max(ymx[l][k],ymx[r-(1<<k)+1][k]);
}
void does(int x,int y,int pos)
{
    int dx=max(RMQ(x,pos-1,2).first,RMQ(pos+1,y,2).first)-min(RMQ(x,pos-1,1).first,RMQ(pos+1,y,1).first);
    int dy=max(RMQ(x,pos-1,4).first,RMQ(pos+1,y,4).first)-min(RMQ(x,pos-1,3).first,RMQ(pos+1,y,3).first);
    ans=min(ans,max(dx,dy));
}
int main()
{
    n=read();
    m=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&xmi[i][0].first,&ymi[i][0].first);
        xmi[i][0].second=i; ymi[i][0].second=i;
        xmx[i][0]=xmi[i][0]; ymx[i][0]=ymi[i][0];
    }
    ST(n);
    while(m--)
    {
        x=read();
        y=read();
        ans=INF;
        does(x,y,RMQ(x,y,1).second);
        does(x,y,RMQ(x,y,2).second);
        does(x,y,RMQ(x,y,3).second);
        does(x,y,RMQ(x,y,4).second);
        printf("%d
",ans);
    }
    return 0;
}

View Code