单侧递归线段树

数据结构。

---

假如说我们现在需要维护一个关于单调栈的上的一些东西，比如结束时单调栈的大小，要求支持修改，就可以考虑使用单侧递归线段树。

其核心就是类似线段树二分一样，每次上传更新就在右子树二分出来第一个可以接上的答案，然后统计在这右边的答案，每次只会递归一侧，所以就叫单侧递归线段树。

在线段树中每个节点需要额外维护目前子树中的最大值，方便更新。

楼房重建

模板题，我们考虑如何在线段树上维护单调栈的大小，每个节点维护子树内的大小和最大值，然后更新做这样一个事情。

• 继承左子树答案
• 在右子树二分的同时加上右子树的答案。

具体实现可以看代码。

点击查看代码

//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n, m;
const int N = 1e5 + 10;
struct Segment{int l, r;int dat;double maxx;
}seg[N * 4];
double a[N];
int ask(int p, double val){if(seg[p].maxx <= val) return 0;if(seg[p].l == seg[p].r){return seg[p].maxx > val;}if(seg[p * 2].maxx >= val){return ask(p * 2, val) + seg[p].dat - seg[p * 2].dat;}else{return ask(p * 2 + 1, val);}
}
void upd(int p){seg[p].maxx = max(seg[p * 2].maxx, seg[p * 2 + 1].maxx);seg[p].dat = seg[p * 2].dat + ask(p * 2 + 1, seg[p * 2].maxx);
}
void build(int p, int l, int r){seg[p].l = l;seg[p].r = r;seg[p].maxx = -1;if(seg[p].l == seg[p].r) {return ;}int mid = (l + r) >> 1;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);
}
void change(int p, int x, double v){if(seg[p].l == seg[p].r){seg[p].dat = 1;seg[p].maxx = v;return ;}int mid = (seg[p].l + seg[p].r) >> 1;if(x <= mid){change(p * 2, x, v);}else{change(p * 2 + 1, x, v);}upd(p);
}
signed main() {
#ifndef Airfreopen("data.in","r",stdin);freopen("data.out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read();m = read();build(1, 0, n);change(1, 0, 0);for(int i = 1; i <= m; i++){int id = read();double x = read();x = x / id;change(1, id, x);cout << seg[1].dat - 1 << '\n';}return 0;
}

[HNOI/AHOI2018] 转盘

推式子题，我们考虑答案一定可以通过在起点停留一会，然后再往前走得到。

我们先断环成链，接下来考虑答案怎样表示：

发现还是不好刻画，于是就倒着考虑，就有，其中 \(i\) 是终点：

\[ans - (i - j) \ge t_j \]

\[ans \ge \max \{ t_j - j \} + i \]

接下来把 \(i\) 换成起点：

\[ans = \min_{i = 1}^{n} \max_{j = i}^{i + n - 1} \{ T_j + i - j \} + n - 1 = \min_{i = 1}^{n} \max_{j = i}^{i + n - 1} \{ T_j - j \} + i + n - 1 \]

考虑换元，设 \(T_j - j = a_j\)，有：

\[ans = \min_{i = 1}^{n} \max_{j = i}^{i + n - 1} \{ a_j \} + i + n - 1 \]

有 \(a_i > a_{i+n}\) 恒成立，所以就有：

\[ans = \min_{i = 1}^{n} \max_{j = i}^{2n} \{ a_j \} + i + n - 1 \]

之后我们考虑拆贡献，答案就有：

不妨设 \(i\) 有 \(i < k \to a_i > a_k\)，\(j\) 是满足 \(a_j > a_i\) 的最小值

\[ans = \min \{a_i + j + 1 + n - 1 \} = \min \{ a_i + j \} + n \]

然后这个就相当于是在一个单调栈上维护信息，用单侧递归线段树即可。

点击查看代码

//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
int n, m, q;
const int N = 2e5 + 10;
int a[N];
struct Segment{int l, r;int dat;//全局的答案int datl;//记录左侧的答案int maxx;
}seg[N * 4];
int ask(int p, int val){if(seg[p].l == seg[p].r){return seg[p].maxx > val ? val + seg[p].l : 1e18;}if(seg[p * 2 + 1].maxx > val){return min(seg[p].datl, ask(p * 2 + 1, val));}else{return ask(p * 2, val);}
}
void upd(int p){seg[p].maxx = max(seg[p * 2].maxx, seg[p * 2 + 1].maxx);seg[p].datl = ask(p, seg[p * 2 + 1].maxx);seg[p].dat = min(seg[p].datl, seg[p * 2 + 1].dat);
}
void build(int p, int l, int r){seg[p].l = l;seg[p].r = r;if(l == r){seg[p].datl = seg[p].dat = 1e18;seg[p].maxx = a[l] - l;return ;}int mid = (l + r) >> 1;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);upd(p);
}
void change(int p, int x, int v){if(seg[p].l == seg[p].r){seg[p].maxx = v;return ;}int mid = (seg[p].l + seg[p].r) >> 1;if(x <= mid){change(p * 2, x, v);}else{change(p * 2 + 1, x, v);}upd(p);
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read();q = read();int p = read();for(int i = 1; i <= n; i++){a[i + n] = a[i] = read();}build(1, 1, n * 2);int lastans = min(1 + seg[1].maxx, seg[1].datl) + n;cout << lastans << '\n';while(q--){int l = read(), r = read();l ^= (lastans * p);r ^= (lastans * p);change(1, l, r - l);change(1, l + n, r - l - n);lastans = min(1 + seg[1].maxx, seg[1].datl) + n;cout << lastans << '\n';}return 0;
}

CF1736C2

考虑先表示出答案：

\[ans = \sum_i {i - \max_j^{i} \max\{0, j - a_j \}} \]

然后化简：

\[ans = \frac{n (n + 1)}{2} - \sum_i {\max_j^{i} \max\{0, j - a_j \}} \]

用单侧递归线段树维护即可。

点击查看代码

//これも運命じゃないか
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define Air
namespace io{inline int read(){int f = 1, t = 0; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}while(ch >= '0' && ch <= '9'){t = t * 10 + ch - '0'; ch = getchar();}return t * f;}inline void write(int x){if(x < 0){putchar('-'); x = -x;}if(x >= 10){write(x / 10);}putchar(x % 10 + '0');}
}
using namespace io;
//正难则反
int n;
const int N = 2e5 + 10;
int a[N];
struct Segment{int l, r;int dat;int maxx;
}seg[N * 4];
int ask(int p, int val){if(seg[p].maxx <= val) return (seg[p].r - seg[p].l + 1) * val;if(seg[p].l == seg[p].r){return seg[p].dat;}if(seg[p * 2].maxx <= val){return (seg[p * 2].r - seg[p * 2].l + 1) * val + ask(p * 2 + 1, val);}else{return ask(p * 2, val) + seg[p].dat - seg[p * 2].dat;}
}
void upd(int p){seg[p].maxx = max(seg[p * 2].maxx, seg[p * 2 + 1].maxx);seg[p].dat = seg[p * 2].dat + ask(p * 2 + 1, seg[p * 2].maxx);
}
void build(int p, int l, int r){seg[p].l = l;seg[p].r = r;if(l == r){seg[p].maxx = max(0ll, l - a[l]);//计算贡献区间//相当于计算 \sum \max max(i - a[i] + 1, 1ll)seg[p].dat = seg[p].maxx;return ;}int mid = (l + r) >> 1;build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);upd(p);// cerr << "Build " << l << ' ' << r << ' ' << seg[p].dat << '\n';
}
void change(int p, int x, int v){if(seg[p].l == seg[p].r){seg[p].maxx = v;seg[p].dat = seg[p].maxx;return ;}int mid = (seg[p].l + seg[p].r) >> 1;if(x <= mid){change(p * 2, x, v);}else{change(p * 2 + 1, x, v);}upd(p);
}
signed main() {
#ifndef Airfreopen(".in","r",stdin);freopen(".out","w",stdout);
#endifios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read();for(int i = 1; i <= n; i++){a[i] = read();}build(1, 1, n);int q = read();int tot = n * (n - 1) / 2 + n;// cerr << tot - seg[1].dat << '\n';while(q--){int id = read(), z = read();z = max(0ll, id - z);change(1, id, z);cout << tot - seg[1].dat << '\n';z = max(0ll, id - a[id]);change(1, id, z);}return 0;
}