日常做题
1. P4198 楼房重建
非常离谱的线段树题，反正我当时看了标签是想不出来怎么线段树的。题意就是求斜率单调上升的序列长度（以下简称该序列为答案序列）。好，我们尽力地去想一下线段树怎么做。同样记左区间、右区间节点为 \(p1, p2\) ，我们考虑维护区间的答案长度， 记为 \(len\) 。很快就会发现，合并起来非常难搞，貌似只有O(n)的复杂度做法。这时，我们就尝试着再多维护一个值：区间斜率最大值，记为 \(v\) 。同时我们也可以观察到，显然，两个区间合并时，左区间的答案序列必定是会保留的。那么，我们现在处理右区间就好了。若右区间的最大值小于等于左区间的最大值，那么很明显，右区间的答案序列必然无法对总的答案产生贡献。而当右区间的最大值大于左区间的最大值时，我们就试着递归处理, 求出右区间可以保留的答案序列（此时以下的区间均为目前区间的子区间，即意味着的以下的 \(v, len\)均已知）：
传入左区间最大值， 记为 \(lmax\)。
- 当 \(l == r\) 时，直接返回 \(v > lmax\) 的值即可。
- 当当前区间的左区间最大值小于等于 \(lmax\) 时，直接在右区间递归即可。
- 当当前区间的左区间最大值大于 \(lmax\) 时，这个时候，右区间的答案我们就可以直接O(1)算出来了：\(len - p1.len\)。既然左区间的 \(v\) 已经大于 \(lmax\) ，那么右区间的答案序列不就都可以保留嘛，那么它的长度就是 \(len - p1.len\) 。因此只需再在左区间递归即可。
容易证明，此操作的复杂度为 \(O(log n)\)，加上线段树查询的复杂度，最后就是 \(O(n log^2n)\) 。
code:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define p1 p * 2
#define p2 p * 2 + 1
#define tl tree[p].l
#define tr tree[p].r
struct xds{
int l, r;
double v;
int len;
}tree[N * 4];
int n, m;
int l(int p, double mv){ //查找区间p中斜率大于mv的单调上升序列长度
if(tree[p].v <= mv) return 0;
if(tl == tr){
return tree[p].v > mv;
}
if(tree[p1].v <= mv) return l(p2, mv);
return l(p1, mv) + tree[p].len - tree[p1].len;
}
void pushup(int p){
tree[p].v = max(tree[p1].v, tree[p2].v);
tree[p].len = tree[p1].len + l(p2, tree[p1].v);
}
void build(int p, int l, int r){ //建树
tl = l, tr = r;
if(l == r){tree[p] = {l, r, 0, 0}; return ;} //注意：刚开始区间长度不能设为1
int mid = l + r >> 1;
build(p1, l, mid);
build(p2, mid + 1, r);
pushup(p);
}
void change(int p, int x, int y){ //修改的同时返回答案
// cout << p << " " << x << " " << y << endl;
if(tl == tr){tree[p].v = (double) y / x, tree[p].len = 1; return ;} //直到修改时才能把区间长度设为1
int mid = tl + tr >> 1;
if(x <= mid) change(p1, x, y);
else change(p2, x, y);
pushup(p);
// cout << p << " " << x << " " << y << " " << tree[p].v << " " << tree[p].len << endl;
}
int main(){
freopen("shuju.in", "r" ,stdin);
freopen("shuju.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
build(1, 1, n);
while(m--){
int x, y;
cin >> x >> y;
change(1, x, y);
cout << tree[1].len << endl;
}
return 0;
}