【ZJNU 組隊賽四】D：Splitting the Field

傳送門

題意

在二維平面上有n個點,初始時使用一個矩形將所有點都框起來;現在想用兩個矩形將這些點框起來,詢問用兩個矩形框起來之后的面積相比于初始時一個大矩形面積減少了多少;

題解

因為要用兩個矩形框住,那么思考一下就知道這兩個矩形只能是左右兩個或者是上下兩個，

①對于左右兩個矩形的情況:

就先將這些點按x值從小到大排序,若x值相同就按照y值從小到大排序;之后列舉以哪個點作為分為左右兩部分的分界點,在這兩邊分別求回應的矩形面積大小，

②對于上下兩個矩形的情況:

實際上將x,y值調換一下位置,再根據第一種情況一樣的做法就可以了，

那么問題就是怎么找出每個矩形的邊界呢,這時候就要請上線段樹了(實際好像不用也可以!),開兩顆線段樹,一顆維護x值的最大最小值,一顆維護y值的最大最小值;找到邊界之后,面積就呼之欲出啦!

AC Code(358ms)線段樹又臭又長又慢

/*******************************
*   Coder : He Shuo.           *
*   Type : Original Work       *
*******************************/

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define show(x) std :: cerr << #x << " = " << x << std :: endl
#define MAX MAXN
typedef long long ll;

const int MAXN = 5e4 + 50;
const ll mo = 998244353;
const int inf = 1e9 + 7;
inline int lson(int p){return p << 1;}
inline int rson(int p){return p << 1 | 1;}

struct node
{
    int x,y;
}p[MAXN];

int n,a[MAXN],b[MAXN];
ll ans = 1e18;
int cmp(node a,node b)
{
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}

struct tree
{
    int l,r;
    int Max,Min;
}t1[MAXN << 2],t2[MAXN << 2];

inline push_up1(int p)
{
    t1[p].Max = max(t1[lson(p)].Max,t1[rson(p)].Max);
    t1[p].Min = min(t1[lson(p)].Min,t1[rson(p)].Min);
}

inline push_up2(int p)
{
    t2[p].Max = max(t2[lson(p)].Max,t2[rson(p)].Max);
    t2[p].Min = min(t2[lson(p)].Min,t2[rson(p)].Min);
}

void build1(int p,int l,int r)
{
    t1[p].l = l,t1[p].r = r;
    if(l == r)
    {
        t1[p].Max = a[l];
        t1[p].Min = a[l];
        return;
    }
    int mid = l + r >> 1;
    build1(lson(p),l,mid);
    build1(rson(p),mid + 1,r);

    push_up1(p);
}

int query_Max1(int p,int l,int r)
{
    if(l <= t1[p].l && r >= t1[p].r)
    {
        return t1[p].Max;
    }

    int mid = t1[p].l + t1[p].r >> 1;
    int maxL = -inf,maxR = -inf;
    if(l <= mid)maxL = max(maxL,query_Max1(lson(p),l,r));
    if(r > mid)maxR = max(maxR,query_Max1(rson(p),l,r));
    return max(maxL,maxR);
}
int query_Min1(int p,int l,int r)
{
    if(l <= t1[p].l && r >= t1[p].r)
    {
        return t1[p].Min;
    }

    int mid = t1[p].l + t1[p].r >> 1;
    int minL = inf,minR = inf;
    if(l <= mid)minL = min(minL,query_Min1(lson(p),l,r));
    if(r > mid)minR = min(minR,query_Min1(rson(p),l,r));
    return min(minL,minR);
}

void build2(int p,int l,int r)
{
    t2[p].l = l,t2[p].r = r;
    if(l == r)
    {
        t2[p].Max = b[l];
        t2[p].Min = b[l];
        return;
    }
    int mid = l + r >> 1;
    build2(lson(p),l,mid);
    build2(rson(p),mid + 1,r);

    push_up2(p);
}

int query_Max2(int p,int l,int r)
{
    if(l <= t2[p].l && r >= t2[p].r)
    {
        return t2[p].Max;
    }

    int mid = t2[p].l + t2[p].r >> 1;
    int maxL = -inf,maxR = -inf;
    if(l <= mid)maxL = max(maxL,query_Max2(lson(p),l,r));
    if(r > mid)maxR = max(maxR,query_Max2(rson(p),l,r));
    return max(maxL,maxR);
}
int query_Min2(int p,int l,int r)
{
    if(l <= t2[p].l && r >= t2[p].r)
    {
        return t2[p].Min;
    }

    int mid = t2[p].l + t2[p].r >> 1;
    int minL = inf,minR = inf;
    if(l <= mid)minL = min(minL,query_Min2(lson(p),l,r));
    if(r > mid)minR = min(minR,query_Min2(rson(p),l,r));
    return min(minL,minR);
}


///上面就是又臭又長的線段樹,功能就是維護區間最值(大家都會~)
void solve()
{
    ///經典排序~
    sort(p + 1,p + 1 + n,cmp);
    for(int i = 1;i <= n;i ++)
    {
        a[i] = p[i].x;
        b[i] = p[i].y;
    }
    build1(1,1,n);///維護x值的極值;
    build2(1,1,n);///維護y值的極值;
    for(int i = 1;i <= n - 1;i ++)///必須要用兩個矩形,所以只要列舉到n - 1;
    {
        int Max_x_i = query_Max1(1,1,i);
        int Min_x_i = query_Min1(1,1,i);

        int Max_y_i = query_Max2(1,1,i);
        int Min_y_i = query_Min2(1,1,i);


        int Max_x_n = query_Max1(1,i + 1,n);
        int Min_x_n = query_Min1(1,i + 1,n);

        int Max_y_n = query_Max2(1,i + 1,n);
        int Min_y_n = query_Min2(1,i + 1,n);
        
		///以上經典求邊界~
        
        ll res = 1LL * (Max_x_i - Min_x_i) * (Max_y_i - Min_y_i) + 1LL * (Max_x_n - Min_x_n) * (Max_y_n - Min_y_n);
        ans = min(ans,res);
    }
}

int main()
{
    scanf("%d",&n);
    int Max_Y = 0,Min_Y = inf;
    int Max_X = 0,Min_X = inf;
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
        Max_X = max(Max_X,p[i].x);
        Max_Y = max(Max_Y,p[i].y);
        Min_X = min(Min_X,p[i].x);
        Min_Y = min(Min_Y,p[i].y);
    }
    ///經典求邊界,算出初始矩形的面積;
    ll ff = 1LL *(Max_X - Min_X) * (Max_Y - Min_Y);

    solve();
    ///交換一下位置同理求出答案;
    for(int i = 1;i <= n;i ++)swap(p[i].x,p[i].y);
    solve();
    
	///要記得是求節約的面積;
    printf("%lld",ff - ans);
}