学步园

果然题意罗里吧嗦的题做法也很麻烦。。

给出二维平面上的一些点，Stan可以任选一个点作一条垂线，然后Ollie可以在垂线上再选一个点作水平线。在一、三象限的点数算Stan的分数，在二、四象限的点算Ollie的分数。

两个人都想要自己的分数最大。

问Stan分数的最大值，且有多种情况时，按大小顺序列出Ollie的所有可能得分（无重复）。

主要重点是维护两棵x轴上的树状数组，当前位置的左边有多少个点和右边有多少个点。

把坐标值离散化，把点按x的大小排序；从左往右扫描，所以先把点插入右边的树（即每个y有多少个点）。

每扫过一个x，先把该x上的点从右边的树删去，然后对该x处的垂线上的每个点求一次四个象限的点的个数；当往下一个x扫描时，把此时的x上的所有点再插入左边的树。

然后一些细节乱搞一下。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 200010

int ny[MAXN];
int sl[MAXN], sr[MAXN];
int n, stan, st, tot;
vector<int> ollie;

inline int lowbit(int x)
{
    return x & -x;
}

int sum(int s[], int i)
{
    int ret = 0;
    while(i > 0)
    {
        ret += s[i];
        i -= lowbit(i);
    }
    return ret;
}

void add(int s[], int i, int val)
{
    while(i <= n)
    {
        s[i] += val;
        i += lowbit(i);
    }
}

struct Point
{
    int x, y;
    bool operator <(const Point &argu) const
    {
        return x < argu.x;
    }
}pp[MAXN];

int main()
{
//    freopen("C.in", "r", stdin);

    while(scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; i++) scanf("%d%d", &pp[i].x, &pp[i].y), ny[i] = pp[i].y;
        sort(ny, ny + n);

        int cnty = 0;
        for(int i = 0; i < n; i++) if(ny[cnty] != ny[i]) ny[++cnty] = ny[i]; cnty++;
        for(int i = 0; i < n; i++) pp[i].y = lower_bound(ny, ny + cnty, pp[i].y) - ny + 1;

        sort(pp, pp + n); pp[n].x = pp[n - 1].x + 1;

        memset(sr, 0, sizeof(sr));
        memset(sl, 0, sizeof(sl));
        for(int i = 0; i < n; i++) add(sr, pp[i].y, 1);

        stan = -1, st = 0;
        for(int i = 0; i < n; i++)
        {
            if(pp[i].x != pp[i + 1].x)
            {
                for(int j = st; j <= i; j++) add(sr, pp[j].y, -1);
                int tmps = -1, tmpo = -1;
                for(int j = st; j <= i; j++)
                {
                    int a = sum(sr, cnty) - sum(sr, pp[j].y) + sum(sl, pp[j].y - 1);
                    int b = sum(sl, cnty) - sum(sl, pp[j].y) + sum(sr, pp[j].y - 1);
                    if(b == tmpo) tmps = min(tmps, a);
                    if(b >  tmpo) tmps = a, tmpo = b;
                }
                if(tmps >  stan) stan = tmps, ollie.clear();
                if(tmps == stan) ollie.push_back(tmpo);
                for(int j = st; j <= i; j++) add(sl, pp[j].y, 1);
                st = i + 1;
            }
        }
        sort(ollie.begin(), ollie.end());
        tot = unique(ollie.begin(), ollie.end()) - ollie.begin();
        printf("Stan: %d; Ollie:", stan);
        for(int i = 0; i < tot; i++) printf(" %d", ollie[i]);
        puts(";");
    }
    return 0;
}