计蒜客 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

Given the

Input Format

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 $q(1≤n,q≤10^5), where n is the number of houses, and q is the number of zoning requests.$

The next $y(−10^9≤x,y≤10^9), 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 first house has address 1, the second house has address 2, and so on. No two houses will be at the same location.$

The next

Output Format

Output

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

样例输出1

1
0

样例输入2

样例输出2

300
299

题意

n个点q次询问，每次询问编号[a,b]的点中，最多忽略一个点覆盖剩下点的最小正方形。

题解

如果不忽略点，那么就是max(最大的X-最小的X，最大的Y-最小的Y)。

如果忽略点，那么就有4种情况，最大的X，最大的Y，最小的X，最小的Y，那么就是次大，次小。

还有4种情况，忽略的点同时是最大的X最大的Y，最大的X最小的Y，最小的X最小的Y，最小的X最大的Y。

线段树维护比较复杂，要自己仔细推一下。

代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int N=1e5+5;
  5 int x[N],y[N];
  6 map<pair<int,int>,int>ma;
  7 int x_maxx[N<<2],x_maxx1[N<<2],x_minn[N<<2],x_minn1[N<<2];
  8 int y_maxx[N<<2],y_maxx1[N<<2],y_minn[N<<2],y_minn1[N<<2];
  9 
 10 void up(int rt)
 11 {
 12     int ls=rt<<1,rs=rt<<1|1;
 13     x_maxx1[rt]=max(min(x_maxx[ls],x_maxx[rs]),max(x_maxx1[ls],x_maxx1[rs]));
 14     x_maxx[rt]=max(x_maxx[ls],x_maxx[rs]);
 15     
 16     x_minn1[rt]=min(max(x_minn[ls],x_minn[rs]),min(x_minn1[ls],x_minn1[rs]));
 17     x_minn[rt]=min(x_minn[ls],x_minn[rs]);
 18     
 19     y_maxx1[rt]=max(min(y_maxx[ls],y_maxx[rs]),max(y_maxx1[ls],y_maxx1[rs]));
 20     y_maxx[rt]=max(y_maxx[ls],y_maxx[rs]);
 21     
 22     y_minn1[rt]=min(max(y_minn[ls],y_minn[rs]),min(y_minn1[ls],y_minn1[rs]));
 23     y_minn[rt]=min(y_minn[ls],y_minn[rs]);
 24 }
 25 int X_MAX,X_MAX1,X_MIN,X_MIN1;
 26 int Y_MAX,Y_MAX1,Y_MIN,Y_MIN1;
 27 void query(int L,int R,int l,int r,int rt)
 28 {
 29     if(L<=l&&r<=R)
 30     {
 31         //printf("FUCK=%d
%d %d
",rt,X_MIN,X_MIN1);
 32         X_MAX1=max(min(X_MAX,x_maxx[rt]),max(X_MAX1,x_maxx1[rt]));
 33         X_MAX=max(X_MAX,x_maxx[rt]);
 34         
 35         X_MIN1=min(max(X_MIN,x_minn[rt]),min(X_MIN1,x_minn1[rt]));
 36         X_MIN=min(X_MIN,x_minn[rt]);
 37         
 38         Y_MAX1=max(min(Y_MAX,y_maxx[rt]),max(Y_MAX1,y_maxx1[rt]));
 39         Y_MAX=max(Y_MAX,y_maxx[rt]);
 40         
 41         Y_MIN1=min(max(Y_MIN,y_minn[rt]),min(Y_MIN1,y_minn1[rt]));
 42         Y_MIN=min(Y_MIN,y_minn[rt]);
 43         //printf("rt=%d
%d %d
",rt,X_MIN,X_MIN1);
 44         return;
 45     }
 46     int mid=(l+r)>>1;
 47     if(L<=mid)query(L,R,l,mid,rt<<1);
 48     if(R>mid)query(L,R,mid+1,r,rt<<1|1);
 49 }
 50 void build(int l,int r,int rt)
 51 {
 52     if(l==r)
 53     {
 54         x_maxx[rt]=x_minn[rt]=x[l];
 55         x_maxx1[rt]=-2e9;
 56         x_minn1[rt]=2e9;
 57         
 58         y_maxx[rt]=y_minn[rt]=y[l];
 59         y_maxx1[rt]=-2e9;
 60         y_minn1[rt]=2e9;
 61         return;
 62     }
 63     int mid=(l+r)>>1;
 64     build(l,mid,rt<<1);
 65     build(mid+1,r,rt<<1|1);
 66     up(rt);
 67 }
 68 int main()
 69 {
 70     int n,q;
 71     scanf("%d%d",&n,&q);
 72     for(int i=1;i<=n;i++)
 73     {
 74         scanf("%d%d",&x[i],&y[i]);
 75         ma[{x[i],y[i]}]=i;
 76     }
 77     build(1,n,1);
 78     /*
 79     for(int i=1;i<=7;i++)
 80         printf("i=%d
%d %d %d %d
%d %d %d %d
",i,x_maxx[i],x_maxx1[i],x_minn[i],x_minn1[i],
 81         y_maxx[i],y_maxx1[i],y_minn[i],y_minn1[i]);
 82     */
 83     while(q--)
 84     {
 85         int l,r;
 86         scanf("%d%d",&l,&r);
 87         X_MAX=X_MAX1=Y_MAX=Y_MAX1=-2e9;
 88         X_MIN=X_MIN1=Y_MIN=Y_MIN1=2e9;
 89         query(l,r,1,n,1);
 90         //printf("%d %d %d %d
",X_MAX,X_MAX1,X_MIN,X_MIN1);
 91         //printf("%d %d %d %d
",Y_MAX,Y_MAX1,Y_MIN,Y_MIN1);
 92         int ans=max(X_MAX-X_MIN,Y_MAX-Y_MIN);
 93         ans=min(ans,max(X_MAX1-X_MIN,Y_MAX-Y_MIN));
 94         ans=min(ans,max(X_MAX-X_MIN1,Y_MAX-Y_MIN));
 95         ans=min(ans,max(X_MAX-X_MIN,Y_MAX1-Y_MIN));
 96         ans=min(ans,max(X_MAX-X_MIN,Y_MAX-Y_MIN1));
 97         if(l<=ma[{X_MAX,Y_MAX}]&&ma[{X_MAX,Y_MAX}]<=r)ans=min(ans,max(X_MAX1-X_MIN,Y_MAX1-Y_MIN));
 98         if(l<=ma[{X_MAX,Y_MIN}]&&ma[{X_MAX,Y_MIN}]<=r)ans=min(ans,max(X_MAX1-X_MIN,Y_MAX-Y_MIN1));
 99         if(l<=ma[{X_MIN,Y_MAX}]&&ma[{X_MIN,Y_MAX}]<=r)ans=min(ans,max(X_MAX-X_MIN1,Y_MAX1-Y_MIN));
100         if(l<=ma[{X_MIN,Y_MIN}]&&ma[{X_MIN,Y_MIN}]<=r)ans=min(ans,max(X_MAX-X_MIN1,Y_MAX-Y_MIN1));
101         printf("%d
",ans);
102     }
103     return 0;
104 }
105 /*
106 5 5
107 -1000000000 -1000000000
108 -1000000000 1000000000
109 1000000000 1000000000
110 1000000000 -1000000000
111 0 0
112 1 3
113 */