poj2464扫描线好题，树状数组解法

用树状数组解比线段树快了好多，难度也下降许多
分别用两个树状数组维护当前扫描线左侧和右侧的点，离散化y轴即可
#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

#define maxn 200005

struct node{

    int x,y;

    bool operator<(const node p)const {

        return x<p.x;

    }

}p[maxn];

int y[maxn],cnt,n;

int l[maxn],r[maxn];//两个树状数组维护扫描线左边的点数，右边的点数

void add(int *bit,int x,int num){

    for(int i=x;i<=cnt+;i+=i&-i)

        bit[i]+=num;

}

int sum(int *bit,int x){

    int res=;

    for(int i=x;i;i-=i&-i)

        res+=bit[i];

    return res;

}

int main(){

    while(scanf("%d",&n),n){

        memset(l,,sizeof l);

        memset(r,,sizeof r);

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

            scanf("%d%d",&p[i].x,&p[i].y);

            y[i]=p[i].y;

        }

        sort(p,p+n);sort(y,y+n);

        cnt=unique(y,y+n)-y;//离散化y轴

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

            add(r,lower_bound(y,y+cnt,p[i].y)-y+,);

        int Stan=-,st=;

        vector<int>Ollie;

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

            if(i==n || p[i].x!=p[i-].x){//一条竖线上的点统一处理

                for(int j=st;j<i;j++)

                    add(r,lower_bound(y,y+cnt,p[j].y)-y+,-);//把这条线上的点从r数组删去

                int stan=-,ollie=-;

                for(int j=st;j<i;j++){

                    int pos=lower_bound(y,y+cnt,p[j].y)-y+;

                    int a=sum(r,cnt)-sum(r,pos)+sum(l,pos-);

                    int b=sum(l,cnt)-sum(l,pos)+sum(r,pos-);

                    if(b==ollie) stan=min(stan,a);//使stan得分最小化

                    else if(b>ollie) stan=a,ollie=b;//使Ollie得分最大化

                }

                if(stan>Stan){Stan=stan;Ollie.clear();}//stan得分更新后同时跟新Ollie得分

                if(stan==Stan)Ollie.push_back(ollie);

                for(int j=st;j<i;j++)//最后把这条线上的点加入l数组

                    add(l,lower_bound(y,y+cnt,p[j].y)-y+,);

                st=i;

            }

        }

        printf("Stan: %d; Ollie:",Stan);

        sort(Ollie.begin(), Ollie.end());

        cnt=unique(Ollie.begin(), Ollie.end())-Ollie.begin();

        for(int i=;i<cnt;i++) printf(" %d",Ollie[i]);

        puts(";");

    }

    return ;

}