楼房重建线段树学习笔记

楼房重建线段树是一种用于快速维护前/后缀最小/最大值以及其相关状态的特殊线段树。

楼房重建线段树的特殊之处主要体现在节点 $u$ 的两个儿子合并更新节点 $u$ 的数据上。

先看一道例题：

CF1690G Count the Trains

单点修改，改完查询不同的前缀最小值个数。

$1\le n,m\le 10^5$。

对原序列建出线段树，对应区间为 $[l,r]$ 的节点 $u$ 维护两个值：

• 区间中的最小值 $mn_u$
• 仅考虑这个区间时的答案 $ans_u$，即不考虑 $[1,l-1]$ 对 $[l,r]$ 中的前缀最小值的影响时 $[l,r]$ 中不同的前缀最小值的个数。

由于只有单点修改，所以考虑递归到底层再不断回溯更新答案即可。

考虑合并 $u$ 的两个儿子的信息：

• $mn_u$ 在两个儿子的最小值中取 $\min$ 即可。
• $ans_u$ 却不能直接取两个儿子的 $ans$ 相加，因为左儿子的区间的最小值会对右儿子的区间的前缀最小值有影响。

考虑 $ans_u$ 的求值，显然左儿子的答案可以直接加进 $ans_u$，那么考虑左儿子的区间的最小值 $val=mn_{ls}$ 对右儿子的答案的影响。

考虑引入一个函数 $calc(u,val)$，它返回 $u$ 考虑了前缀最小值 $val$ 的影响后的答案，代码如下：

int calc(int u,int l,int r,int val)
{
	if(l==r) return mx[u]<val;
	int mid=l+r>>1;
	if(val>mx[u<<1]) return calc(u<<1,l,mid,val)+ans[u]-ans[u<<1];
	else return calc(u<<1|1,mid+1,r,val);
}

其中 u<<1 和 u<<1|1 即为 $u$ 的左右儿子。

考虑这样做的正确性：

• 当区间长度为 $1$ 时，贡献直接暴力计算。
• 当区间长度大于 $1$ 时：
  1. 若 $val>mn_{ls}$，那么 $val$ 肯定不会对右子树的答案有影响，直接用 $ans_u-ans_{ls}$ 算出右子树考虑了左子树影响后的答案，然后递归左子树即可；
  2. 否则左子树肯定不会产生任何贡献，直接递归右子树。

这样做的时间复杂度显然是 $O(\log n)$ 的，因为每次会且仅会进入一个儿子的子树进行递归。

每次通过 $u$ 的两个儿子的信息更新 $u$ 的信息时直接 $ans_u\to ans_{ls}+calc(rs,mn_{ls})$ 即可。

这样做还有一个小小的问题，若 $ans$ 维护的东西不具有可减性，那么不能直接通过 $ans_u-ans_{ls}$ 算出右子树考虑了左子树影响后的答案， 也不能在 $calc$ 中同时递归两个子树。这时可以考虑每次合并两个儿子更新父亲的信息时记录右儿子的贡献。

完整代码如下：

// Problem: CF1690G Count the Trains
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1690G
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

int n,m;
int a[S];
int mx[S<<2],ans[S<<2];

int calc(int u,int l,int r,int val)
{
	if(l==r) return mx[u]<val;
	int mid=l+r>>1;
	if(val>mx[u<<1]) return calc(u<<1,l,mid,val)+ans[u]-ans[u<<1];
	else return calc(u<<1|1,mid+1,r,val);
}

void upda(int u,int l,int r)
{
	mx[u]=min(mx[u<<1],mx[u<<1|1]);
	int mid=l+r>>1;
	ans[u]=ans[u<<1]+calc(u<<1|1,mid+1,r,mx[u<<1]);
}

void upd(int u,int l,int r,int pos,int val)
{
	if(l==r)
	{
		mx[u]=val;
		ans[u]=1;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) upd(u<<1,l,mid,pos,val);
	else upd(u<<1|1,mid+1,r,pos,val);
	upda(u,l,r);
}

inline void slove()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),upd(1,1,n,i,a[i]);
	for(int i=1;i<=m;i++)
	{
		int pos,val;
		scanf("%d%d",&pos,&val);
		upd(1,1,n,pos,a[pos]-=val);
		printf("%d ",ans[1]);
	}
	printf("\n");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}

练习题目

• P4198 楼房重建（维护不同的前缀最大值的个数）
• 区间：

问题描述

小 A 最近在研究数组，他认为如果数组的一个区间内不包含重复的元素，那么这个区间是一个优美的区间。

现在小 A 弄到了一个有趣的数组，他想知道这个数组有多少个优美的区间。当然，他有时候也会觉得这个数组不够优美，此时他会修改数组中的一个元素。

小 A 发现在修改之后他不会算有多少个优美的区间了，于是他来向你求助。

输入格式

第一行输入一个数 $n$，表示数组长度。

接下来一行输入 $n$ 个整数，第 $i$ 个整数 $a_i$ 是数组中的第 $i$ 个元素。

接下来一行输入一个数 $q$，表示操作数量。

接下来 $q$ 行每行表示一次操作。如果某行第一个数为 $0$，则表示一次询问。否则后面输入两个数 $x$ 和 $y$，表示将 $a_x$ 修改为 $y$。

输出格式

对于每次询问，输出一行一个整数表示答案。

输入数据 1

3
1 2 3
3
0
1 1 2
0

输出数据 1

6
4

数据范围及约定

对于 $40\%$ 的数据，保证 $n\le 10^3$。

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le q\le 2n$，$1\le a_i\le n$。