楼房p4198

这一道题目稍微转换一下题意之后就可以知道需要维护一个斜率单调递增的序列（下文把每个点的斜率称为权值） 所以动态维护权值单增序列可以像下面这么做 我们根据线段树“分而治之”的思想，用每一个节点维护相似的信息 维护什么呢？维护在这一个节点的代表区间中，以这一个节点所代表的区间的第一个点为开头的最大的权值 ......

P4198 楼房重建(RE:题解再改造!!) 码 #include<bits/stdc++.h>#define MAXN 2000010using namespace std;int n,m;int x[MAXN],y[MAXN],ans[MAXN];double K[MAXN];int query ......

[传送门](https://www.luogu.com.cn/problem/P4198) 一眼数据结构。 考虑线段树，记录该区间能看到最多的建筑数量 $ans_{wz}$ 以及看到区间中最大的斜率（或者说，该区间内最后看到的建筑）$xl_{wz}$。 很明显，假如我现在的修改操作是 $(x,y)$ ......

P4198 楼房重建 题解 线段树二分 思路 考虑在线段树内维护二信息： 区间斜率最大值 $mx$ 区间最大斜率上升序列长度 $len$ 答案即为根节点的 $len$。 考虑转移信息二： 蓝色部分代表左区间的上升序列，红色是右区间的，绿色折线就是当前区间的上升序列。 🤔稍微思考之后发现，左区间的上 ......

楼房重建 先搞清楚题目要求的是什么。令 $k_0=0,k_i=\frac{h_i}{i}$，则题目求的一个从 $0$ 开始的单调上升序列的长度减一。 最暴力的做法就是直接维护上升的序列，修改后从修改处开始重新维护，但时间复杂度不对，考虑优化。 先忽略从 $0$ 开始的限制条件。 令 $mx_{\le ......