【线段树】洛谷 P4198 楼房重建

题链

解：带修改的查询包含第一个值的$[1，n]$的最长上升子序列（姑且这么叫吧…）；

线段树维护节点区间最大值以及区间包含最左值的最长上升子序列，则询问的答案就是根节点的信息

区间最大值$p[rt].maxn$很好维护，主要是维护 区间包含最左值的最长上升子序列 这里记为$p[rt].upcnt$;

显然对于每一个叶子节点（$[i,i]$）节点信息就是 { $maxn =$ 本身的值，$upcnt = 1$} ;

更新$p[rt].upcnt$时，左孩子$[l,m]$区间$p[ls].upcnt$都是需要加上的，毕竟是从前往后看，右孩子$[m+1,r]$则需要查找大于左孩子最大值的数目，把左孩子的最大值当作目标然后递归查找；

现在开始递归查找，如果左孩子$[l,m]$的最大值小于等于目标值，那么就去查找右孩子$[m+1,r]$，如果左孩子$[l,m]$的最大值大于目标值，则右孩子的贡献就是 整个区间$[l,r].upcnt -$ 左孩子$[l,m].upcnt +$ 递归左孩子的值；

终点就是当 $l == r$ 时，当前值大于目标值返回 $1$ ，否则 $0$；

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("O2")
using namespace std;
using namespace __gnu_pbds;
#define Pair pair<LL,LL>
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997

int n,m;
struct node{
	double maxn;
	int upcnt;
}p[MS<<2];

int cal(int rt,int l,int r,double tar){
	if(l == r) return p[rt].maxn > tar;
	int m = l+r>>1;
	if(p[ls].maxn <= tar) return cal(rs,m+1,r,tar);
	else return p[rt].upcnt - p[ls].upcnt + cal(ls,l,m,tar);
}

void push_up(int rt,int l,int r){
	p[rt].maxn = max(p[ls].maxn,p[rs].maxn);
	int m = l+r>>1;
	p[rt].upcnt = p[ls].upcnt + cal(rs,m+1,r,p[ls].maxn);
}

void update(int L,int R,int l,int r,int rt,double val){
	if(L <= l && r <= R){
		p[rt].maxn = val;
		p[rt].upcnt = 1;
		return;
	}
	int m = l+r>>1;
	if(m >= L) update(L,R,l,m,ls,val);
	if(m <  R) update(L,R,m+1,r,rs,val);
	push_up(rt,l,r);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	while(m--){
		double x,y;
		cin >> x >> y;
		double k = y/x;
		update(x,x,1,n,1,k);
		int ans = p[1].upcnt;
		cout << ans << "\n";
	}


	return 0;

}