「bzoj2957」楼房重建 - 线段树/区间依赖

题目大意

    小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
    为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上$(0,0)$点的位置，第$i$栋楼房可以用一条连接$(i,0)$和$(i,H_i)$的线段表示，其中$H_i$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于$0$的点与$(0,0)$的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
    施工队的建造总共进行了$M$天。初始时，所有楼房都还没有开始建造，它们的高度均为$0$。在第$i$天，建筑队将会将横坐标为$X_i$的房屋的高度变为$Y_i$(高度可以比原来大，也可以比原来小，甚至可以保持不变)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

---

题目分析

不妨使用线段树维护斜率$\frac yx$。
考虑，若左区间有一个很大的斜率$k$，那么右区间比$k$小的斜率就不会被计算进入答案（维护一个类似单调栈的东西）。
这样右区间统计的答案对左区间产生了依赖，我们不妨命名为区间依赖。

这样的区间依赖问题一般可以用线段树很好的解决。
用线段树解决修改问题，考虑向上合并答案。
每次合并答案的时候累加左区间答案，右区间答案不能直接累加，我们需要一个函数计算其贡献。

$cal(id,v)$表示$id$区间比$v$大的个数。
若$id$左区间最大值比$v$小，那么左区间无贡献，左区间对右区间也没有影响，递归右区间。
否则，说明$v$对右区间无影响，仅影响了左区间，递归左区间即可。

这样每次递归呈单链形态，时间复杂度$O(n\log^2 n)$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005;

struct Segment_Tree {
	struct Tree {
		int left,right;
		double max;
		int ans;
		Tree(int l=0,int r=0):left(l),right(r) {
			max=ans=0;
		}
	} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
	void build(int index,int Left,int Right) {
		tree[index]=Tree(Left,Right);
		if(Left==Right)return;
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
	}
	int cal(int index,double val) {
		if(tree[index].left==tree[index].right)return tree[index].max>val;
		if(tree[ls].max<=val)return cal(rs,val);
		return tree[index].ans-tree[ls].ans+cal(ls,val);
	}
	void push_up(int index) {
		tree[index].max=max(tree[ls].max,tree[rs].max);
		tree[index].ans=tree[ls].ans+cal(rs,tree[ls].max);
	}
	void modify(int index,int target,double val) {
		if(tree[index].right<target||tree[index].left>target)return;
		if(tree[index].left==tree[index].right) {
			tree[index].ans=1;
			tree[index].max=val;
			return;
		}
		modify(ls,target,val);
		modify(rs,target,val);
		push_up(index); 
	}
} st;

int n,m;

int main() {
	n=Get_Int();
	m=Get_Int();
	st.build(1,1,n);
	while(m--) {
		int x=Get_Int(),y=Get_Int();
		st.modify(1,x,(double)y/x);
		printf("%d\n",st.tree[1].ans);
	}
	return 0;
}