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[200005];
bool cmpx(node a, node b)
{
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
const int N = 200005;
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 = 0;
    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 == 0) break;
        mpx.clear(), mpy.clear();
        queue<node> wq;
        fill(tre, tre + N, 0);
        fill(ans, ans + N, 0);
        for (int i = 0; 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 = 0; 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 + 1),wq.pop();
                else break;
            }
            int py = upper_bound(st, st + len, p[i].y)-st+1;
            ans[i] += query(py-1);
            wq.push(p[i]);
        }
        while (!wq.empty()) wq.pop();
        fill(tre, tre + 200005, 0);
        for (int i = n-1; i >= 0; i--)
        {
            while (!wq.empty())
            {
                node ad = wq.front();
                if (ad.x > p[i].x) add(len+st-upper_bound(st, st + len, ad.y) + 1),wq.pop();
                else break;
            }
            int py = len + st - upper_bound(st, st + len, p[i].y) + 1;
            ans[i] += query(py-1);
            wq.push(p[i]);
        }
        map<int, int> getMi;
        for (int i = 0; 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 = 0; 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] + 1);
        
        for (set<int>::iterator it = rpy.begin(); it != rpy.end(); it++)
        {
            cout << ' ' << *it;
        }
        cout << ";" << endl;
    }
    return 0;
}

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

相关推荐