楼房重建

楼房重建

题意

小 A 在平面上 \((0,0)\) 点的位置，第 \(i\) 栋楼房可以用一条连接 \((i,0)\) 和 \((i,H_i)\) 的线段表示，其中 \(H_i\) 为第 \(i\) 栋楼房的高度。如果这栋楼房上任何一个高度大于 \(0\) 的点与 \((0,0)\) 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

有 \(m\) 次修改，每次修改 \(H_x\) 为 \(y\)，并查询小 A 能看到多少个楼房。

思路

首先可以把楼房转化为斜率，\(k_i=\frac{H_i}{i}\)，若 \(i<j\) 且 \(k_i<k_j\) 则 \(i\) 不会挡住 \(j\)。

所以小 A 能看到的楼房均满足 \(k_i<k_x(i<x)\)，即 \(k_x\) 是 \(k\) 的一个前缀最大值。

问题转化为了单点修改，询问全局前缀最大值的个数。

这个可以使用分块解决。

每次单点修改时，暴力重新统计块内的前缀最大值存入数组。

查询时从左往右查每个块，在块内的前缀最大值数组内二分第一个大于当前最大值的数，

后面的数都是前缀最大值，统计答案，更新最大值，继续下一个块。

时间复杂度：\(O(n(\frac{n}{B}+B\log n))\)，\(B=\sqrt{\frac{n}{\log n}}\) 时取得最小值 \(O(n\sqrt{n\log n})\)。

警示：只用转化为斜率，不用再用 atan 转化为角度，会损失精度导致答案错误。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T> 
void read(T& x) {x = 0; T f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -f;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}x = x * f;
}
template <typename T> 
void write(T x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');
}
const int N = 2e5 + 5, M = 2e3 + 5; 
const double PI = acos(-1);
int B, n, m, cnt;
int id[N], L[N], R[N];
double r[N];
vector <double> pre[M];void init() {B = sqrt(1.0 * n / log2(n));for (int i = 1; i <= n; i ++) {id[i] = (i - 1) / B + 1;if (!L[id[i]]) L[id[i]] = i;R[id[i]] = i;}cnt = id[n]; 
}void modify(int x, int y) {r[x] = (double)(y) / (double)(x);pre[id[x]].clear();double nowMax = 0;for (int i = L[id[x]]; i <= R[id[x]]; i ++) {if (r[i] > nowMax && r[i] != 0) {pre[id[x]].push_back(r[i]);nowMax = r[i];}}
}int query() {int res = 0;double nowMax = 0;for (int i = 1; i <= cnt; i ++) {if (pre[i].empty()) continue;auto pos = upper_bound(pre[i].begin(), pre[i].end(), nowMax);res += pre[i].end() - pos;nowMax = max(nowMax, pre[i].back());}return res;
}int main() {read(n); read(m);init();while (m --) {int x, y;read(x); read(y);modify(x, y);write(query());putchar('\n');		}return 0;
}