默认\(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
未知来源题
维护一个序列\(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)\)做法，并没有看懂是什么东西。