题解 P4198 【楼房重建】

题目链接

Solution 楼房重建

题目大意：维护一个数列(v)，单点修改，每次修改后回答有多少个位置(p)满足 (forall xin [1,p),v[x] < v[p])

线段树

---

分析：

分析题目可以发现我们需要将楼房高度转化为斜率，然后就是题目大意

我们将符合要求的位置(p)的集合称为一条链，那么我们维护链的长度和结尾元素（链上元素一定是严格单调递增的）

考虑怎么合并，记链长为(sum)，链结尾为(mx)，左右儿子为(ls)和(rs)

那么(ls)的(sum)是可以直接拿来用的，(rs)则需要求出只考虑大于(tr[ls].mx)的元素的链长，然后两条链接在一起就行了

我们记(calc(x,limit))表示(x)这段区间，只考虑大于(limit)的元素的链长

如果(limit > tr[ls].mx)，那么(calc(x,limit)=calc(rs,limit))

否则(calc(x,limit)=tr[rt].sum - tr[ls].sum+calc(ls,limit))

(rs)只考虑大于(tr[ls].mx)的元素的链长我们已经算出来了可以直接用，这样才能保证(calc)操作的复杂度为(O(logn))

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long double type;
const type eps = 1e-5;
const int maxn = 1e5 + 100;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
int n,m;

namespace st{
	#define ls (rt << 1)
	#define rs (rt << 1 | 1)
	struct node{
		type mx;
		int sum;
	}tr[maxn << 2];
	inline int calc(int rt,type limit,int l,int r){
		if(l == r)return tr[rt].sum * (tr[rt].mx > limit);
		int mid = (l + r) >> 1;
		if(limit > tr[ls].mx)return calc(rs,limit,mid + 1,r);
		else return tr[rt].sum - tr[ls].sum + calc(ls,limit,l,mid);
	}
	inline void modify(int pos,type v,int rt = 1,int l = 1,int r = n){
		if(l == r){
			tr[rt].mx = v;
			tr[rt].sum = v > eps;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid)modify(pos,v,ls,l,mid);
		else modify(pos,v,rs,mid+ 1,r);
		tr[rt].sum = tr[ls].sum + calc(rs,tr[ls].mx,mid + 1,r);
		tr[rt].mx = max(tr[ls].mx,tr[rs].mx);
	}
	#undef ls
	#undef rs
}
int main(){
#ifdef LOCAL
	freopen("fafa.in","r",stdin);
#endif
	n = read(),m = read();
	for(int x,y,i = 1;i <= m;i++){
		x = read(),y = read();
		st::modify(x,type(y) / x);
		printf("%d
",st::tr[1].sum);
	}
	return 0;
}