UVA10869 - Brownie Points II(线段树)
题目链接
题目大意：平面上有n个点，Stan和Ollie在玩游戏，游戏规则是：Stan先画一条竖直的线作为y轴，条件是必需要经过这个平面上的某一点，而ollie则画x轴，可是要在Stany画的y轴上经过的点中随意选择一点来作为原点画x轴。然后这个平面就被划分为4个象限，轴上的点都不算，1，3象限的点的个数就是Stan的得分，2，4就是ollie的得分。问Stan每画一条y轴，每条轴上都有个得分的最小值，求这些最小值中的最大值，而且输出这时ollie的得分。
解题思路：将y轴离散化建树，希望每次枚举一个点就能够得到这个点的Stan的得分。从左往右，从上往下处理每一个点，通过线段树能够得到y高度上的点的个数，就是第一象限的得分。然后每次查询完一个点就要将这个点在线段树中删掉。同理得到第三象限的得分。这题还要输出ollie的得分，而且要按顺序，用set来存储。
代码：
#include <cstdio> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> #include <iostream> using namespace std; const int maxn = 2e5; #define lson(x) (x<<1) #define rson(x) ((x<<1) | 1) int n; vector<int> pos; map<int, int>x, y; set<int> score, vec; struct Point { int x, y, score; }p[maxn]; int cmp_x (const Point &a, const Point &b) { if (a.x == b.x) return a.y > b.y; return a.x < b.x; } struct Node { int l, r, v, addv; void set (int l, int r, int addv, int v) { this->l = l; this->r = r; this->v = v; this->addv = addv; } }node[4 * maxn + 5]; void add_node (int u, int addv) { node[u].addv += addv; node[u].v += (node[u].r - node[u].l + 1) * addv; } void pushdown (int u) { if (node[u].addv) { add_node(lson(u), node[u].addv); add_node(rson(u), node[u].addv); } } void pushup (int u) { node[u].set (node[lson(u)].l, node[rson(u)].r, 0, node[lson(u)].v + node[rson(u)].v); } void build (int u, int l, int r) { if (l == r) { node[u].set (l, r, 0, y[pos[l]]); return ; } int m = (l + r)>>1; build (lson(u), l, m); build (rson(u), m + 1, r); pushup(u); } void update (int u, int l, int r, int add) { if (node[u].l >= l && node[u].r <= r) { add_node(u, add); return; } pushdown(u); int m = (node[u].l + node[u].r)>>1; if (l <= m) update (lson(u), l, r, add); if (r > m) update (rson(u), l, r, add); pushup(u); } int query (int u, int l, int r) { if (node[u].l >= l && node[u].r <= r) return node[u].v; pushdown(u); int m = (node[u].l + node[u].r)>>1; int ans = 0; if (l <= m) ans += query(lson(u), l, r); if (r > m) ans += query(rson(u), l, r); pushup(u); return ans; } void init () { x.clear(); y.clear(); pos.clear(); for (int i = 0; i < n; i++) { scanf ("%d%d", &p[i].x, &p[i].y); p[i].score = 0; x[p[i].x]++; y[p[i].y]++; pos.push_back(p[i].y); } sort (pos.begin(), pos.end()); sort (p, p + n, cmp_x); pos.erase(unique (pos.begin(), pos.end()), pos.end()); } void solve_rtop () { int x; build(1, 0, (int)pos.size() - 1); for (int i = 0; i < n; i++) { x = lower_bound(pos.begin(), pos.end(), p[i].y) - pos.begin(); if (x + 1 <= pos.size() - 1) { p[i].score += query(1, x + 1, pos.size() - 1); //printf ("%d %d %d\n", p[i].x, p[i].y, x); } update (1, x, x, -1); } } void solve_lboutom () { int x; build(1, 0, (int)pos.size() - 1); for (int i = n - 1; i >= 0; i--) { x = lower_bound(pos.begin(), pos.end(), p[i].y) - pos.begin(); if (x - 1 >= 0) { p[i].score += query (1, 0, x - 1); //printf ("%d %d %d\n", p[i].x, p[i].y, p[i].score); } update (1, x, x, -1); } } void add_ans (int tmp) { for (set<int>::iterator it = vec.begin(); it != vec.end(); it++) score.insert(n - tmp - x[p[*it].x] - y[p[*it].y] + 1); } void solve () { init(); solve_lboutom(); solve_rtop(); score.clear(); vec.clear(); int ans = -1; int tmp = p[0].score; int pre = p[0].x; for (int i = 0; i < n; i++) { if (pre == p[i].x) { if (tmp == p[i].score) vec.insert(i); else if (tmp > p[i].score) { vec.clear(); vec.insert(i); tmp = p[i].score; } } else { if (ans <= tmp) { if (ans < tmp) score.clear(); add_ans(tmp); } ans = max (ans, tmp); tmp = p[i].score; pre = p[i].x; vec.clear(); vec.insert(i); } } if (ans <= tmp) { if (ans < tmp) score.clear(); add_ans(tmp); } ans = max (ans, tmp); printf("Stan: %d; Ollie:", ans); for (set<int>::iterator it = score.begin(); it != score.end(); it++) printf(" %d", *it); printf(";\n"); } int main () { while (scanf ("%d", &n) && n) { solve(); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/4197785.html
相关资源：数据结构—成绩单生成器