【poj2464】樹狀數組

這道題。。太特么多細節了。。

題意：在平面直角坐標系中給你N個點，stan和ollie玩一個游戲，首先stan在豎直方向上畫一條直線，該直線必須要過其中的某個點，然后ollie在水平方向上畫一條直線，該直線的要求是要經過一個stan之前畫過的點。 這時候平面就被分割成了四塊，兩個人這時候會有一個得分，stan的得分是平面上第1、3象限內的點的個數，ollie的得分是平面上第2、4象限內的點的個數，在統計的時候在所畫線上的點都不計算在內。求最終stan使得自己的最差得分最高，并且輸出此時ollie的得分。

?

題解：

我們可以枚舉哪顆星星是中心點，然后就可以知道他們所確定的直線。

線上可以維護四個值：up，down，left，right，分別表示線上四個方位有多少顆星星。

然后我們只要求BL,就可以知道其它：

TL=橫坐標比x小的星星總數-BL-left

TR=y坐標比x大的星星總數-TL-up

BR=y坐標比x小的星星總數-BL-down

各種細節><

?

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=200010,INF=(int)1e9+100;
int n,pl,mx,c[N],cntx[N],cnty[N],sumx[N],sumy[N],sx[N][2],sy[N][2],u[N],d[N],l[N],r[N],a1[N],a2[N];
bool num[N];
struct node{
    int x,y;
}a[N];
struct nd{
    int d,id,tmp;
}p[2*N];

bool cmp_num(int x,int y){return x<y;}
bool cmp_d(nd x,nd y){return x.d<y.d;}
bool cmp_a(node x,node y)
{
    if(x.x==y.x) return x.y<y.y;
    return x.x<y.x;
}
int maxx(int x,int y){return x>y ? x:y;}

void clear()
{
    memset(cntx,0,sizeof(cntx));
    memset(cnty,0,sizeof(cnty));
    memset(sumx,0,sizeof(sumx));
    memset(sumy,0,sizeof(sumy));
    memset(c,0,sizeof(c));
    memset(a1,63,sizeof(a1));
    memset(a2,-1,sizeof(a2));
}

void add(int x)
{
    for(int i=x;i<=mx;i+=(i&(-i))) c[i]++;
}
int getsum(int x)
{
    int ans=0;
    for(int i=x;i>=1;i-=(i&(-i))) ans+=c[i];
    return ans;
}

int main()
{
    freopen("a.in","r",stdin);
    // freopen("me.out","w",stdout);
    while(1)
    {
        scanf("%d",&n);
        if(n==0) break;
        pl=0;clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            p[++pl].d=a[i].x;p[pl].id=i;p[pl].tmp=0;
            p[++pl].d=a[i].y;p[pl].id=i;p[pl].tmp=1;
        }
        sort(p+1,p+1+pl,cmp_d);
        mx=0;p[0].d=INF;
        for(int i=1;i<=pl;i++)
        {
            if(p[i].d!=p[i-1].d) mx++;
            if(p[i].tmp==0) a[p[i].id].x=mx;
            else a[p[i].id].y=mx;
        }
        
        sort(a+1,a+1+n,cmp_a);
        // for(int i=1;i<=n;i++) 
            // printf("%d %d\n",a[i].x,a[i].y);
        for(int i=1;i<=n;i++)
        {
            d[i]=cntx[a[i].x];cntx[a[i].x]++;
            l[i]=cnty[a[i].y];cnty[a[i].y]++;
        }
        // for(int i=1;i<=mx;i++) 
            // printf("i = %d  %d %d\n",i,cntx[i],cnty[i]);
        for(int i=1;i<=n;i++)
        {
            u[i]=cntx[a[i].x]-d[i]-1;
            r[i]=cnty[a[i].y]-l[i]-1;
        }
        for(int i=1;i<=mx;i++) 
        {
            sumx[i]=sumx[i-1]+cntx[i];
            sumy[i]=sumy[i-1]+cnty[i];
        }
        for(int i=1;i<=n;i++)
        {
            int x=a[i].x,y=a[i].y;
            sx[i][0]=sumx[x-1];
            sx[i][1]=sumx[mx]-sumx[x];
            sy[i][0]=sumy[y-1];
            sy[i][1]=sumy[mx]-sumy[y];
        }
        // for(int i=1;i<=n;i++)
        // {
            // printf("%d  sx0 %d sx1 %d sy0 %d sy1 %d d %d u %d l %d r %d\n",i,sx[i][0],sx[i][1],sy[i][0],sy[i][1],d[i],u[i],l[i],r[i]);
        // }
        for(int i=1;i<=n;i++)
        {
            int x=a[i].x,y=a[i].y;
            int BL=getsum(a[i].y-1)-d[i];
            int TL=sx[i][0]-BL-l[i];
            int TR=sy[i][1]-TL-u[i];
            int BR=sy[i][0]-BL-d[i];
            add(y);
            if(TR+BL<a1[x]) a1[x]=TR+BL,a2[x]=TL+BR;
            else if(TR+BL==a1[x]) a2[x]=maxx(a2[x],TL+BR);
            // printf("%d  BL = %d  BR = %d  TR = %d TL = %d\n",i,BL,BR,TR,TL);
        }
        int ans=0,nl=0;;
        for(int i=1;i<=mx;i++) 
        {
            if(a1[i]<INF) ans=maxx(ans,a1[i]);
        }
        printf("Stan: %d; Ollie:",ans);
        memset(num,0,sizeof(num));
        for(int i=0;i<=n;i++) 
            if(a1[i]==ans) num[a2[i]]=1;
        for(int i=0;i<=n;i++) 
            if(num[i]) printf(" %d",i);
        printf(";\n");
    }
    return 0;
}

?