类楼房重建线段树

有意思

Posted by ShanLunjiaJian's Blog on April 16, 2021

默认\(n,q\leq 10^5\)。


[清华集训2013] 楼房重建

给一个序列\(a\),支持单点修改,查询把所有数从右往左扔进一个单调栈之后,单调栈的大小。

当然一个等价的说法是有多少个数大于它前面的所有数,也就是是严格的前缀\(\max\),不过这里我们用第一种。

使用线段树。考虑如何合并信息。

这题要全局查询,但是我们可以考虑区间查询。

考虑如果左儿子最大值大于等于右儿子最大值,那么右儿子直接弹没了,此时答案就是左儿子答案。

否则,发现不是很好合并,因为左儿子会影响右儿子答案。

我们搞一个calc(u,k)表示结点\(u\)区间中从右往左,最后往单调栈扔进一个\(k\)得到的单调栈大小。这样上面那个情况的答案就是calc(右儿子,左儿子max)。我的习惯是左儿子是lq(u),右儿子是rq(u),原因是我初一学线段树的时候英语不好,总是以为child的首字母是q。

容易发现它是一个分段函数,一共有\(O(len)\)段,所以如果没有修改,我们可以直接预处理出这个函数,预处理的复杂度是\(O(n\log n)\),单次查询是\(O(\log n)\)。

但是如果有修改,这个calc怎么写?

考虑我们在线段树上进行递归查询。如果每次只递归到一个儿子,那么复杂度是\(O(\log n)\),还可以接受。

  • 如果区间长度是\(1\),那么完全不用递归,直接返回t[u].max>k

  • 如果左儿子最大值不超过\(k\),那么左儿子没了,我们直接递归进入右儿子。

  • 如果左儿子最大值超过\(k\),那么左儿子最大值弹掉的东西不会比\(k\)少,所以\(k\)对右儿子没有影响了,递归进入左儿子。此时右儿子的贡献呢?就是calc(rq(u),t[lq(u)].max),这个东西重复计算太慢了,我们可以每个点维护一下,不妨记为val

所以可以写出代码

1
2
3
4
5
6
inline int calc(int u,int k)
{
	if(t[u].l==t[u].r) return a[u]>k;
	if(k<t[lq(u)].max) return calc(lq(u),k)+t[u].val;
	else return calc(rq(u),k);
}

,这是好的。然后怎么合并?

1
inline void push_up(int u){ t[u].max=max(t[lq(u)].max,t[rq(u)].max),t[u].val=calc(rq(u),t[lq(u)].max); }

维护一下就可以过了。复杂度,因为calc一次复杂度是\(O(\log n)\),一共是\(O(n\log^2 n)\)。

完整代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>

struct Num
{
	int x,y;
};
inline bool operator == (const Num &a,const Num &b){ return a.x==b.x&&a.y==b.y; }
inline bool operator < (const Num &a,const Num &b){ return (long long)a.y*b.x<(long long)a.x*b.y||(a==Num{0,0}&&b.y!=0); }
inline Num max(Num a,Num b){ return a<b?b:a; }

struct Node
{
	int l,r;
	Num max;
	int val;
}t[400002];

#define lq(u) ((u)<<1)
#define rq(u) ((u)<<1|1)

inline int calc(int u,Num k)
{
	if(t[u].l==t[u].r) return k<t[u].max;
	if(k<t[lq(u)].max) return calc(lq(u),k)+t[u].val;
	else return calc(rq(u),k);
}
inline void push_up(int u){ t[u].max=max(t[lq(u)].max,t[rq(u)].max),t[u].val=calc(rq(u),t[lq(u)].max); }

void build(int l,int r,int u)
{
	t[u].l=l,t[u].r=r;
	if(l==r)
	{
		t[u].max=Num{l,0};
		t[u].val=0;
		return;
	}
	int mid=(t[u].l+t[u].r)>>1;
	build(l,mid,lq(u)),build(mid+1,r,rq(u));
	push_up(u);
}

void change(int p,int u,int v)
{
	if(t[u].l==t[u].r)
	{
		t[u].max=Num{t[u].l,v};
		t[u].val=(t[u].max.y>0);
		return;
	}
	int mid=(t[u].l+t[u].r)>>1;
	if(p<=mid) change(p,lq(u),v);
	else change(p,rq(u),v);
	push_up(u);
}

int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	build(1,n,1);
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),change(x,1,y),printf("%d\n",calc(1,Num{0,0}));
	return 0;
}

所以说,类楼房重建线段树就是通过维护一个分支的信息,实现线段树上\(O(\log n)\)查询我们需要的信息。

当然这要求信息性质比较优秀。具体怎么优秀?不好说……

总之就是可以维护递归的一边,使得每次只递归一个儿子。

应用这一算法的常见标志有,单点修改;前后缀min/max,单调栈(实际上是一个东西),每个点\(O(len)\)的信息(但是这个条件很不充分),等等。当然最主要还是前后缀min/max。


加强 : 区间加。

呃你发现,对于完全包含在操作区间内的结点,我们维护的那个val并不会受影响,所以直接打标记即可。


HDU6406 Taotao Picks Apples

就是 楼房重建。


CF1340F Nastya and CBS

多种括号的括号序列,支持单点修改,查询区间括号是否匹配。

考虑如果一个区间跟某些东西拼一拼可能合法,那么它匹配之后留在栈里的只有可能是一堆右括号然后一堆左括号,看起来像是))))((((之类的。当然这两堆都可能是空的。

合并的时候,对于左儿子的左括号和右儿子的右括号,我们取短的那一边尝试匹配长的那一边的相同长度,如果刚好匹配也就是类型完全相同,那就把剩下的部分合并,否则就直接不合法。看类型是否相同,显然可以使用hash搞定。

考虑如果没有修改,我们可以直接预处理每个点区间内左括号每个后缀的hash值和右括号每个前缀的hash值,这个东西可以建树的时候单次\(O(len)\)地爆力合并出来,之后可以支持查询的时候\(O(1)\)合并。

如果有修改,我们考虑扔掉这个预处理,转而使用类楼房重建线段树。用calcL(u,k)表示求\(u\)的后\(k\)个左括号的hash值,维护cntL,valL表示这个区间合并之后的左括号数量和hash值,那么

  • 如果\(k\)是\(0\),直接返回\(0\)

  • 如果\(u\)不合法,直接返回不合法

  • 如果\(u\)右儿子的左括号数量不少于\(k\)个,返回calc(rq(u),k),这是因为右儿子的左括号在合并的时候一定会留下来

  • 如果\(u\)右儿子的左括号数量少于\(k\)个,

    • 如果t[lq(u)].cntL<t[rq(u)].cntR,直接返回\(0\),因为右儿子的左括号不够,左儿子的左括号都被右儿子的右括号匹配完了

    • 否则,计算temp=calc(lq(u),k-t[rq(u)].cntL+t[rq(u)].cntR),返回merge(temp,t[rq(u)].valL),其中merge是hash值的合并。表示右儿子的左括号占了t[rq(u)].cntL个,同时左右儿子匹配之后左儿子的左括号跟右儿子的右括号匹配,少了t[rq(u)].cntR

calcR类似,硬实现即可。

在这个问题上,类楼房重建线段树相当于通过线段树上的查询,以一个\(\log\)的代价,把原来维护的\(O(n)\)信息变成了\(O(1)\)从而支持修改。我并不能想到怎么样合并的信息是可以用这种技巧的/ll


zr256 数组

维护一个序列\(a\),支持单点修改,查询有多少个区间不包含重复元素。

套路大家都懂,设\(pre_i\)表示\(a_i\)上一次出现的下标,也就是最大的\(j<i\)满足\(a_j=a_i\)。于是一个区间\([l,r]\)合法当且仅当对于所有\(l\leq k\leq r\),都有\(pre_k<l\),也就是\(\max_{i=l}^r(pre_i)<l\)。

显然单点修改就是改三个\(pre\)。

静态问题考虑枚举左端点统计右端点,这个右端点是连续的一段,可以在线段树上二分出来,单次\(O(n\log n)\)。这太慢了。

枚举左端点统计右端点对\(pre\)不是很友好,我们枚举右端点统计左端点。

右端点右移会增加一个数,而这个数的\(pre\)会对左端点们产生新的限制,所以我们假设\(l_r\)表示右端点为\(r\)时的左端点,那么就有\(l_r=\max(l_{r-1},pre_r+1)\)。这就非常好。

所以我们的答案就是

\[\sum_{i=1}^{n}(i-l_i+1)=\frac{1}{2}n(n+1)+n-\sum_{i=1}^nl_i\]

你发现后面那个,要是不断拆开,会得到一个\(pre+1\)的前缀\(\max\)。这就非常好,因为变成了前缀\(\max\)求和。

线段树,整一个calc(u,k)表示已经有前缀\(\max\) \(k\)时\(u\)区间内后面那个式子的值,

  • 如果区间长度是\(1\),返回max(t[u].max,k)

  • 如果k>t[lq(u)].max,返回(mid-l+1)*k+calc(rq(u),k)

  • 如果k<=t[lq(u)].max,维护t[u].val=calc(rq(u),t[lq(u)].max),返回calc(lq(u),k)+t[rq(u)].val

。维护即可。


[HNOI/AHOI2018] 转盘

有一个\(n\)个格子的转盘,转盘上有一个指针。你可以选定一个指针在\(0\)时刻的起始位置,然后每两个时刻之间,你可以选择下一时刻转到下一个位置(如果在\(n\)则转到\(1\)),或者不转。

转盘上每个格子有一个物品,第\(i\)个格子里的物品出现在时刻\(t_i\)。如果某个时刻,你所在的格子里的物品已经出现了(出现时刻小于等于当前时刻),那么你就可以拿走这个物品。求最早在哪一时刻拿走所有物品。强制在线。

考虑在中间停留,等价于一开始就等着,所以我们假设一开始停\(k\)时刻,然后选择物品\(p\),然后走一圈,那么最后就在时刻\(k+n-1\)结束。

为了方便把编号前移一位变成\(0\)到\(n-1\),于是这两个值合法当且仅当满足一组限制 :

\[t_{(p+i)\bmod{n}}\leq k+i\bmod{n}\]

然后容易想到要破环成链。问题变成

\[t_{p+i}\leq k+i\]

当然这里\(i\)的范围也要变成\(p\leq i\leq p+n-1\)。

然后移项

\[t_{p+i}-i\leq k\]

那么如果我们选择了一个\(p\),答案就是\(\max(t_{p+i}-i+p)\)。

所以总的答案就是

\[\min_{p=0}^{n-1}\left(\max_{i=0}^{n-1}(t_{p+i}-i)\right)+n-1\]

你发现这个\(i\)的范围很不爽。注意到我们一直枚举\(p+i\)到\(2n-1\)是不会影响答案的,所以就变成了一堆后缀\(\max\)在取\(\min\)。

你还发现这个\(\max\)里面东西有点多,我们设\(a_i=t_i-i\)。

经过这两步,上面的式子就变成了

\[\min_{p=0}^{n-1}\left(\max_{i=0}(a_{p+i})+p\right)+n-1\]

线段树。每个点维护\(p\)在它区间内的答案ans,然后考虑单点修改。

呃实际上非常简单,我们只需要重新求出改了的位置的\(f\)即可。

等等,改一个位置,可能会影响前面很多的\(f\),这个并不好维护。不过既然是后缀\(\max\),我们考虑类楼房重建线段树。

核心是,对于一串连续的相等的后缀\(\max\),最左边那一个比其它所有都要优。

calc(u,k)表示\(u\)右边已经有一个后缀\(\max\) \(k=a_{p_0}\)时的答案,那么

  • 如果区间长度是\(1\),直接返回max(k,t[u].max)+mid+n-1,也就是取mid时的答案。

  • 如果t[rq(u)].max<=k,返回min(calc(lq(u),k),k+mid+1+n-1),因为此时右儿子里面所有的后缀最大值都等于\(k\),我们可以只拿右区间左端点mid+1尝试更新。当然这里的+1-1可以消掉,这么写是为了清楚。

  • 如果t[rq(u)].max>k,维护t[u].val=calc(lq(u),t[rq].max),返回min(t[u].val,calc(rq(u),k))

直接维护即可。注意这个题强制在线的lastans是初始答案。


试看看!

例题1.7

CF671E Organizing a Race

有一条路,路上有\(n\)个城市顺次排列,每个城市有一个加油站,开到第\(i\)个城市可以立刻获得\(g_i\)单位的油。从城市\(i\)开到城市\(i+1\)需要耗费\(w_i\)单位的油。

现在要举办一场赛车比赛,赛道建立在城市\(l,r\)之间。比赛分为两轮,第一轮从\(l\)出发到\(r\),第二轮从\(r\)出发到\(l\)。一开始车会获得起点处加油站的油(比赛开始后不会再次获得),如果车没到达终点就没油了那么赛道不合法。求经过城市最多的合法赛道经过的城市数。

直接抄官方题解。

爆力怎么做?容易想到一个简单贪心,我们从左往右贪心地操作,也就是到走不动了再操作;从右往左则把剩下的一口气加到右端点。直接实现是\(O(n^3)\)的。

我们首先尝试用式子表示上面的东西。

设\(pre_i=pre_{i-1}+g_{i-1}-w_{i-1}\)表示一个前缀和,\(suf_i=suf_{i-1}+g_i-w_{i-1}\)表示另一个前缀和。实际上它俩分别是从\(1\)走到\(i\)和从\(i\)走到\(1\)的所得(正的是油变多了,负的是变少了;不考虑油箱空了)。那么从\(i\)走到\(j\)的所得就是\(pre_j-pre_i\),走回来就是\(suf_j-suf_i\)。

你发现\([l,r]\)合法当且仅当对于任意\(l\leq i\leq r\),从\(l\)走到\(i\)和从\(i\)走到\(r\)的所得都是正的,也就是

\[pre_i-pre_l\geq 0,suf_r-suf_k\geq 0\]

。进行移项,我们得到

\[pre_l=\min_{i=l}^r(pre_i),suf_r=\max_{i=l}^r(suf_i)\]

,这个好像有点意思。

然后,如果从左往右是合法的,那么从右往左走需要在\(r\)处操作的次数,也就是把\(suf_r\)变成最大值的操作次数,显然就是

\[\max_{i=l}^r(suf_i)-suf_r\]

然后考虑往右走的时候那个”走不动了”,我们设\(next_i\)为最小的满足\(pre_j<pre_i\)的\(j\),也就是第一个走不到的位置,不存在则连到一个虚点\(n+1\)。

你发现\(next\)形成了一棵树,每个位置\(i\)往右走到头需要加油的所有位置\(next_i-1,next_{next_i}-1,...\),就是这棵树上到根的链上所有点\(-1\)。

此时有一个直觉,我们从\(n+1\)出发dfs这棵树,走到每个点的时候处理它作为左端点的答案。这有一个好处,就是每走一步都只会在一个位置操作若干次,或是撤销一个位置的操作。

既然从左往右是合法的,我们可以维护\(cost_r\)表示从当前的\(l\)从左往右走到\(r\)需要多少次操作,然后直接使用上面计算从右往左需要的值的式子,容易写出一个\(O(n^2)\)的暴力。

要优化,考虑数据结构维护。

发现移动\(l\)的时候,对\(suf\)和\(cost\)的影响都是一个后缀加。所以我们要支持

  • 两个序列的后缀加。

  • 查询\(cost_r+\max_{i=l}^r(suf_i)-suf_r\leq k\)的最大\(r\)。

然后你发现查询的时候这个从\(l\)开始枚举\(i\)就很难受,容易发现我们可以通过把\(suf\)前面加一个巨大的数从而消去它们的影响,这样我们就可以从\(1\)开始了。

现在问题变成了 :

  • 两个序列的区间加。

  • 查询\(cost_r+\max_{i=1}^r(suf_i)-suf_r\leq k\)的最大\(r\)。

前缀\(\max\),类楼房重建线段树。

线段树上二分,问题转化成查询区间\(cost_r+\max_{i=1}^r(suf_i)-suf_r\leq k\)的最小值。

整一个calc(u,k)表示前面已经有前缀最大值\(k\)的情况下,结点\(u\)区间内的上面那个东西。

  • 如果k>t[lq(u)].max,维护t[u].s表示最小的\(cost_r-suf_r\),返回min(t[lq(u)].s+k,calc(rq(u),k))

  • 如果k<=t[lq(u)].max,维护t[u].val=calc(rq(u),t[lq(u)].max)返回min(calc(lq(u),k),t[u].val)

  • 如果区间长度是\(1\),返回t[u].s+max(k,t[u].max)

发现两个序列的区间加对我们维护的val也是区间加,所以可以直接打标记。

代码不是很好写,只是还能写。

lk给出了一个\(O(n\log n)\)做法,并没有看懂是什么东西。