usaco 2016 Feb 负载平衡

题目大意：平面上一堆点，用两条平行于坐标轴的直线将其分为四部分，使得点数最多的一部分最少

第一维枚举，第二维三分，点集用两棵树状数组维护

#include<bits/stdc++.h>

#define maxn 100010

using namespace std;

inline int read(){

    int s=;char ch=getchar();

    for(;ch<''||ch>'';ch=getchar());

    for(;ch>=''&&ch<='';ch=getchar())s=s*+ch-'';

    return s;

}

int n;

struct node{

    int x,y;

    int cntx,cnty;

}s[maxn];

int cmp1(node a,node b){return a.x<b.x;}

int cmp2(node a,node b){return a.y<b.y;}

int c1[maxn];

int c2[maxn];

void add(int a[],int x,int v){

    for(;x<=n;x+=x&-x)a[x]+=v;

}

int ask(int a[],int x){

    int ans=;

    for(;x;x-=x&(-x))ans+=a[x];

    return ans;

}

int get(){

    int L=,R=n,mid1,mid2,k1,k2,p1,p2;

    int sum1=ask(c1,n);

    int sum2=ask(c2,n);

    while(R-L>=){

        mid1=(L+L+R)/,mid2=(L+R+R)/;

        p1=ask(c1,mid1);p2=ask(c2,mid1);

        k1=max(max(p1,sum1-p1),max(p2,sum2-p2));

        p1=ask(c1,mid2);p2=ask(c2,mid2);

        k2=max(max(p1,sum1-p1),max(p2,sum2-p2));

        if(k1>k2)L=mid1;else R=mid2;

    }

    int ans=(<<);

    for(int i=L;i<=R;++i){

        p1=ask(c1,i);p2=ask(c2,i);

        ans=min(ans,max(max(p1,sum1-p1),max(p2,sum2-p2)));

    }return ans;

}

int main(){

    freopen("Load_Balancing.in","r",stdin);

    freopen("Load_Balancing.out","w",stdout);

    n=read();

    for(int i=;i<=n;++i){

        s[i].x=read();s[i].y=read();

    }

    sort(s+,s+n+,cmp2);

    s[].cnty=;

    for(int i=;i<=n;++i)

        if(s[i].y==s[i-].y)s[i].cnty=s[i-].cnty;

        else s[i].cnty=s[i-].cnty+;

    sort(s+,s+n+,cmp1);

    s[].cntx=;

    for(int i=;i<=n;++i)

        if(s[i].x==s[i-].x)s[i].cntx=s[i-].cntx;

        else s[i].cntx=s[i-].cntx+;

    for(int i=;i<=n;++i)add(c2,s[i].cnty,);

    int L=,R=s[n].cntx,now=,ans=(<<);

    for(int i=L;i<=R+&&now<=n;++i){

        while(s[now].cntx<=i&&now<=n)add(c2,s[now].cnty,-),add(c1,s[now].cnty,),now++;

        int k=get();

        if(k<ans)ans=k;

    }printf("%d\n",ans);

    return ;

}