HDU 5714 树状数组 + 离散化

题意：

Problem Description

小明在旅游的路上看到了一条美丽的河，河上有许多船只，有的船只向左航行，有的船只向右航行。小明希望拍下这一美丽的风景，并且把尽可能多的船只都完整地拍到一张照片中。

小明位于河的边上，并且可以在河边的任意位置进行拍照，照相机的视野恰好为90度角，只能以垂直于河边的方向进行拍照。河上的船只全都可看作是平行于河边的一条线段，跟河边的距离各不相同，有的正在向左移动，有的正在向右移动，但移动速度恰好都是一样的。小明可以等待恰当的时间让尽量多的船只都走进照相机的视野里，你不需要考虑船只之间会互相遮挡视野的情况。

Input

第一行为$T$，表示输入数据组数。

下面$T$组数据，对于每组数据：

第一行是一个数n(1≤n≤104)n(1\leq n\leq 10^{4})n(1≤n≤10​4​​)，表示船只的数量。

接下来$n$行，每行四个整数 x,y,z,d(−106≤x<y≤106,1≤z≤104)x,y,z,d(-10^{6}\leq x < y \leq 10^{6},1\leq z\leq 10^{4})x,y,z,d(−10​6​​≤x<y≤10​6​​,1≤z≤10​4​​)，表示船只的左端点位置、右端点位置、距离河边的距离，以及航行的方向。$d$为$-1$表示向左航行，$1$表示向右航行。

Output

对第$i$组数据，输出

Case #i:

然后输出一行，仅包含一个整数，表示最多可以拍到多少完整的船只。

Sample Input Copy 3 2 1 3 1 1 2 4 1 -1 2 1 3 1 -1 2 4 1 1 1 1 4 1 1 Sample Output Copy Case #1: 2 Case #2: 1 Case #3: 0

思路：

首先假定向左方向的船都是静止的，那么船要么向右移动要么静止。 对于区间是[L,R]的船，我们根据视角计算出在岸上可以观察这艘船的位置区间[l,r]，因为拍摄是可以等待船移动的，因为所有船的速度是一样的，如果我们选定了某个位置，那么这个位置能看到一些静止的船，除此之外，还可以等待该位置左边的且向右行驶的船移动到该位置，所以其实就是在当前位置pos的左边找一个位置pos'，使得pos'位置上能看到的向右行驶的船数+pos位置上静止的船数最大即可。 这样就可以利用树状数组来维护，每次区间左端点+1，右端点后一位-1，然后求得的sum(i)就是当前位置能看到的船数，向左和向右的船分别用一个BIT来维护。 另外需要注意到的一点是x,y的区间范围还是很大，需要离散化。

代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 22222; struct BIT { int n; int C[MAXN]; void init(int n) { this->n = n; memset(C, 0, sizeof(C)); } int lowbit(int x) { return x & -x; } void add(int x, int y) { while (x <= n) { C[x] += y; x += lowbit(x); } } int sum(int x) { int res = 0; while (x) { res += C[x]; x -= lowbit(x); } return res; } } lbit, rbit; struct Boat { int l, r, dir; }; vector <Boat> boat; int discre(int n) { int Max = 0; vector <int> vec; for (int i = 0; i < (int)boat.size(); i++) { vec.push_back(boat[i].l); vec.push_back(boat[i].r); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for (int i = 0; i < (int)boat.size(); i++) { boat[i].l = lower_bound(vec.begin(), vec.end(), boat[i].l) - vec.begin() + 1; boat[i].r = lower_bound(vec.begin(), vec.end(), boat[i].r) - vec.begin() + 1; Max = max(Max, max(boat[i].l, boat[i].r)); } return Max; } int main() { // freopen("in.txt", "r", stdin); int T, cs = 0; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); boat.clear(); for (int i = 1; i <= n; i++) { int l, r, d, dir; scanf("%d%d%d%d", &l, &r, &d, &dir); double len = (d - (r - l) / 2.0), mid = (l + r) / 2.0; if (len >= 0) boat.push_back((Boat) {mid - len, mid + len, dir}); } int m = discre(n); lbit.init(m); rbit.init(m); for (int i = 0; i < boat.size(); i++) { if (boat[i].dir == -1) { lbit.add(boat[i].l, 1); lbit.add(boat[i].r + 1, -1); } else { rbit.add(boat[i].l, 1); rbit.add(boat[i].r + 1, -1); } } int maxright = 0, ans = 0; for (int i = 1; i <= m; i++) { int leftcnt = lbit.sum(i); maxright = max(maxright, rbit.sum(i)); ans = max(ans, leftcnt + maxright); } printf("Case #%d:\n%d\n", ++cs, ans); } return 0; }