Description

给定n座楼，初始高度为0，每次可以改变某栋楼的高度，求每次改变高度之后从原点可以看到几栋楼

Solution 1

一个比较显然的做法是分块，假设块大小是S,分为L块，维护每块中斜率单调上升的序列

每次暴力修改复杂度为 O(S)

每次询问时对每块序列中二分第一个大于之前斜率的位置即可，复杂度 O(L?logN)

显然 S=N/S?logN即S=NlogN??????√ 时最优

Solution 2

其实我们还可以用线段树做，修改一个值其实是对它前面的楼没有任何影响的，我们可以用线段树维护一个最大值以及能看到的楼的个数

正常进行单调修改，同时维护答案，每次维护的时候其实就是左端答案加上右端大于左端最大值的部分

复杂度 O(Nlog2N)

Code1(分块)

#include 
   
     using namespace std; typedef long long LL; const int N = 100005; const double eps = 1e-10; int cnt[80]; double a[N], b[80][1300]; inline int read(int &t) { int f = 1;char c; while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1; t = c - '0'; while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c - '0'; t *= f; } int main() { int n, m, x, y; read(n), read(m); int S = (int)sqrt(n * log(n) / log(2) + 0.5), L = n / S + (n % S ? 1 : 0); while (m--) { read(x), read(y); a[x - 1] = (double)y / x; int bl = (--x) / S; cnt[bl] = 0; double now = 0.0; for (int i = bl * S; i < (bl + 1) * S && i < n; ++i) if (a[i] > now + eps) b[bl][cnt[bl]++] = a[i], now = a[i]; now = 0.0; int ans = 0; for (int i = 0; i < L; ++i) { int l = 0, r = cnt[i] - 1; int t; while (l <= r) { int mid = l + r >> 1; if (b[i][mid] > now + eps) t = mid, r = mid - 1; else l = mid + 1; } if (b[i][cnt[i] - 1] > now + eps) ans += cnt[i] - t; now = max(now, b[i][cnt[i] - 1]); } printf("%d\n", ans); } return 0; }
   

Code2(线段树)

#include 
   
     using namespace std; #define ls (rt << 1) #define rs (rt << 1 | 1) const int N = 100005; int cnt[N << 2]; double mx[N << 2]; inline int read(int &t) { int f = 1;char c; while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1; t = c - '0'; while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c - '0'; t *= f; } int calc(int rt, int l, int r, double x) { if (l == r) return mx[rt] > x; int mid = l + r >> 1; if (mx[ls] <= x) return calc(rs, mid + 1, r, x); else return cnt[rt] - cnt[ls] + calc(ls, l, mid, x); } void change(int rt, int l, int r, int p, double x) { if (l == r) { mx[rt] = x; cnt[rt] = 1; return; } int mid = l + r >> 1; if (p <= mid) change(ls, l, mid, p, x); else change(rs, mid + 1, r, p, x); mx[rt] = max(mx[ls], mx[rs]); cnt[rt] = cnt[ls] + calc(rs, mid + 1, r, mx[ls]); } int main() { int n, m, x, y; read(n), read(m); while (m--) { read(x), read(y); change(1, 1, n, x, (double) y / x); printf("%d\n", cnt[1]); } return 0; }