HDOJ-1156 Brownie Points II 线段树/树状数组（模板）

http://acm.hdu.edu.cn/showproblem.php?pid=1156

在一张二位坐标系中，给定n个点的坐标，玩一个划线游戏（线必须穿过点），Stan先手画一条垂直的线，然后Ollie画一条水平的线（要求要穿过Stan那条线所穿过的某个点）。划分后，左上和右下点数是Ollie 的得分，左下和右上是Stan的得分。求Stan在保证最低得分（即不论Ollie后手怎么划，Stan最少能的的分数）最高，并给出基于符合的先手划法，Ollie后手的各种划线的得分（需要去重），升序输出。

这里可以发现，每次划分等同于枚举以某个点为原点，求一次局面，不同的局面分类到x轴坐标中，每个坐标中的局面集合求最小值，所有x轴坐标分类求最大值即求出了最低最大划法。

#include <iostream>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <cmath>

#include <cstdio>

#include <map>

#include <algorithm>

using namespace std;

struct node

{

    int x, y;

}p[];

bool cmpx(node a, node b)

{

    if (a.x == b.x) return a.y < b.y;

    return a.x < b.x;

}

const int N = ;

map<int, int> mpx, mpy;

int st[N];

int tre[N];

int ans[N];

int lowbit(int k)

{

    return k&-k;

}

int query(int k)

{

    int rec = ;

    while (k)

    {

        rec += tre[k];

        k -= lowbit(k);

    }

    return rec;

}

void add(int k)

{

    while (k <= N)

    {

        tre[k]++;

        k += lowbit(k);

    }

}

bool cmp(node a, int b)

{

    return a.x < b;

}

int main() {

    cin.sync_with_stdio(false);

    int n;

    while (cin>>n)

    {

        if (n == ) break;

        mpx.clear(), mpy.clear();

        queue<node> wq;

        fill(tre, tre + N, );

        fill(ans, ans + N, );

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

            cin >> p[i].x>>p[i].y,mpx[p[i].x]++,mpy[p[i].y]++,st[i]=p[i].y;

        sort(st, st + n);

        int len = unique(st, st + n) - st;

        sort(p, p + n, cmpx);

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

        {

            while (!wq.empty())

            {

                node ad = wq.front();

                if (ad.x < p[i].x) add(upper_bound(st, st + len, ad.y) - st + ),wq.pop();

                else break;

            }

            int py = upper_bound(st, st + len, p[i].y)-st+;

            ans[i] += query(py-);

            wq.push(p[i]);

        }

        while (!wq.empty()) wq.pop();

        fill(tre, tre + , );

        for (int i = n-; i >= ; i--)

        {

            while (!wq.empty())

            {

                node ad = wq.front();

                if (ad.x > p[i].x) add(len+st-upper_bound(st, st + len, ad.y) + ),wq.pop();

                else break;

            }

            int py = len + st - upper_bound(st, st + len, p[i].y) + ;

            ans[i] += query(py-);

            wq.push(p[i]);

        }

        map<int, int> getMi;

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

        {

            if (getMi.find(p[i].x) == getMi.end()) getMi[p[i].x] = ans[i];

            else getMi[p[i].x] = min(getMi[p[i].x], ans[i]);

        }

        map<int, int>::iterator mxit = getMi.end();

        for (map<int, int>::iterator it = getMi.begin(); it != getMi.end(); it++)

        {

            if (mxit == getMi.end())

                mxit = it;

            else if (mxit->second < it->second)

                mxit = it;

        }

        cout << "Stan: " << mxit->second << "; Ollie:";

        set<int> rpy;

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

            if (getMi[p[i].x]==ans[i]&&ans[i] == mxit->second)

                rpy.insert(n - ans[i] - mpx[p[i].x] - mpy[p[i].y] + );

        for (set<int>::iterator it = rpy.begin(); it != rpy.end(); it++)

        {

            cout << ' ' << *it;

        }

        cout << ";" << endl;

    }

    return ;

}