若数学公式无法显现请自行刷新




传送门：Load Balancing_Silver

传送门的题面虽然是Silver，但和Platinum的区别也只在数据范围，所以看题面看水谷就行了。Platinum的数据范围是1E5，此解法也可AC

看了一眼题，先敲了60行splay，再认真看题……卧槽根本不用平衡树。但是既然都写了……不用就太吃亏了。这里就写下平衡树解法吧。

首先标准的二分，看不出来请自裁。令x线指与y轴平行的线，y线指与x轴平行的线。我们发现不能二分套二分的来求x线和y线，因为这两个在一起并不满足单调性。

看一下数据范围，如果是$Nlog(N)$或者$Nlog^2(N)$应该还是能够接受的。考虑枚举x线，二分y线，这时候我们需要的就是两棵平衡树，L存着在x线左侧的所有点的y坐标，另一棵R存着在x线右侧的所有点的y坐标。每次x线向后移时，只需要在L中插入一些，在R中删除一些即可。

至于为什么二分y线就是满足单调的呢？这点稍微画下图就能明白。check的条件也就是

if max(左下，右下)<=max(左上，右上)
   then l=mid+1
   else r=mid

然后稍微注意一下代码细节。如果直接二分x线权值我们不好让mid全为偶数。注意到题目并没有让我们输出x线y线，我们可以改为二分最后一个小于等于x线权值的点的横坐标。

AC代码：

#include <bits/stdc++.h>
using namespace std;

inline int red(){
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 1e5+10;
const int INF = 0x3f3f3f3f;

int n,res=INF,ans=INF;
int ypos[N];

struct point{int x,y;}p[N];
bool cmp(point a,point b){return a.x<b.x;}

namespace Splay{
    struct S{
        int ch[N][2],fa[N],sze[N],cnt[N],val[N];
        int root,tot;
        #define ls(A) ch[A][0]
        #define rs(A) ch[A][1]
        void pushup(int x){sze[x]=sze[ls(x)]+sze[rs(x)]+cnt[x];}
        void conect(int a,int p,int b){ch[a][p]=b,fa[b]=a;}
        void rotate(int x){
            int y=fa[x],z=fa[y],k=(rs(y)==x),w=(rs(z)==y);
            conect(z,w,x),conect(y,k,ch[x][k^1]),conect(x,k^1,y);
            pushup(y),pushup(x);
        }
        void splay(int x,int s){
            while(fa[x]!=s){
                int y=fa[x],z=fa[y],k=(ls(y)==x),w=(ls(z)==y);
                if(z!=s)    rotate(k==w?y:x);
                rotate(x);
            }
            if(!s)    root=x;
        }
        void insert(int tar){
            int x=root,y=0;
            while(x&&val[x]!=tar)    y=x,x=ch[x][tar>val[x]];
            if(x)    {++cnt[x],splay(x,0);return;}
            x=++tot;
            if(y)    ch[y][tar>val[y]]=x;
            fa[x]=y,sze[x]=cnt[x]=1,val[x]=tar;
            splay(x,0);
        }
        void find(int tar){        
            int x=root;if(!root)    return;
            while(ch[x][tar>val[x]]&&val[x]!=tar)    x=ch[x][tar>val[x]];
            splay(x,0);
        }
        int drive(int tar,int f){
            find(tar);int x=root;
            if(val[x]>tar&&f)    return x;
            if(val[x]<tar&&!f)    return x;
            x=ch[x][f];
            while(ch[x][f^1])    x=ch[x][f^1];
            return x;
        }
        void dereta(int tar){
            int per=drive(tar,0),net=drive(tar,1);
            splay(per,0),splay(net,per);    
            int del=ls(net);
            if(cnt[del]>1)    --cnt[del],splay(del,0);
            else    ls(net)=0;
        }
        int num(int tar){
            find(tar);
            return sze[ls(root)]+cnt[root];
        }
        int sum(){return sze[ls(root)]+sze[rs(root)]+cnt[root];}
    }s[2];
}

//ld=left down lu=left up rd=right down ru=right up
int check(int mid,int x){
    int per=Splay::s[0].num(ypos[mid])-1,net=Splay::s[1].num(ypos[mid])-1;
    int lef=Splay::s[0].sum()-2,rig=Splay::s[1].sum()-2;
    int ld=per,lu=lef-ld,rd=net,ru=rig-rd;
    if(max(ld,rd)<=max(lu,ru))    return res=min(res,max(lu,ru)),1;
    return 0;
}

int main(){
    n=red();
    for(int i=1;i<=n;++i)
        p[i].x=red(),p[i].y=ypos[i]=red();
    sort(p+1,p+n+1,cmp);sort(ypos+1,ypos+n+1);
    Splay::s[0].insert(-1e9),Splay::s[0].insert(1e9);
    Splay::s[1].insert(-1e9),Splay::s[1].insert(1e9);
    for(int i=1;i<=n;++i)    Splay::s[1].insert(p[i].y);
    for(int i=1,cnt=1;i<=n;++i){
        while(p[cnt].x<=p[i].x&&cnt<=n)    Splay::s[0].insert(p[cnt].y),Splay::s[1].dereta(p[cnt++].y);
        int l=1,r=n;res=INF;
        while(l+1<=r){
            int mid=l+r>>1;
            if(check(mid,cnt-1))    l=mid+1;
            else                    r=mid;
        }
        ans=min(ans,res);
    }
    printf("%d",ans);
    return 0;
}