单侧递归线段树

数据结构。

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

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

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

楼房重建

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

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

具体实现可以看代码。

点击查看代码

//これも運命じゃないか
#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 Air
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    ios::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 Air
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::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 Air
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::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;
}

CF1340F

我们先把能匹配的先匹配了，考察一个性质就是加入出现 \(x, -y\) 这种情况就一定不合法，那么剩下的就一定会是一堆右括号和一堆左括号，接下来就考虑如何合并。

我们现在就是要把左边的右边和右边的左边做一个比较，然后看能否继续满足条件，然后就可以通过哈希来写。

但有一个问题是我们无法通过全部的哈希值推出局部的哈希值，于是在上面二分即可。

点击查看代码

//これも運命じゃないか
#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, q;
const int N = 1e5 + 10, MOD = 998244353, P = 100003;
int pw[N];
int iv[N];
int quick_pow(int a, int b){
	if(!b) return 1;
	if(b & 1){
		return a * quick_pow(a, b - 1) % MOD;
	}
	else{
		int tmp = quick_pow(a, b / 2);
		return tmp * tmp % MOD;
	}
}
void prework(int x){
	pw[0] = iv[0] = 1;
	int inv = quick_pow(P, MOD - 2);
	for(int i = 1; i <= x; i++){
		pw[i] = pw[i - 1] * P % MOD;
		iv[i] = iv[i - 1] * inv % MOD;
	}
}
struct Hst{
	int val, len;
	friend bool operator == (Hst x, Hst y){
		return (x.val == y.val) && (x.len == y.len);
	}
	friend Hst operator + (Hst x, Hst y){
		return {(x.val + y.val * pw[x.len]) % MOD, x.len + y.len};
	}
	friend Hst operator - (Hst x, Hst y){
		return {(x.val - y.val + MOD) * iv[y.len] % MOD, x.len - y.len};
	}
};
struct Segment{
	int l, r;
	int laz;
	Hst datl, datr;
}seg[N * 4];
int a[N];
Hst askL(int p, int val){
	if(!val){
		return {0, 0};
	}
	if(val == seg[p].datl.len){
		return seg[p].datl;
	}
	if(val <= seg[p * 2].datl.len){
		return askL(p * 2, val);
	}
	else{
		return seg[p * 2].datl + (askL(p * 2 + 1, val - seg[p * 2].datl.len + seg[p * 2].datr.len) - seg[p * 2].datr);
	}
}
Hst askR(int p, int val){
	if(!val){
		return {0, 0};
	}
	if(val == seg[p].datr.len){
		return seg[p].datr;
	}
	if(val <= seg[p * 2 + 1].datr.len){
		return askR(p * 2 + 1, val);
	}
	return seg[p * 2 + 1].datr + (askR(p * 2, val - seg[p * 2 + 1].datr.len + seg[p * 2 + 1].datl.len) - seg[p * 2 + 1].datl);
}
void upd(int p){
	if(seg[p * 2].laz || seg[p * 2 + 1].laz) {
		seg[p].laz = 1;
		return ;
	}
	seg[p].laz = 0;
	seg[p].datl = seg[p * 2].datl;
	seg[p].datr = seg[p * 2 + 1].datr;//相当于抵消的是一段前缀，然后就是反着定义
	if(seg[p * 2].datr.len <= seg[p * 2 + 1].datl.len){
		if(seg[p * 2].datr == askL(p * 2 + 1, seg[p * 2].datr.len)){
			seg[p].datl = seg[p].datl + (seg[p * 2 + 1].datl - seg[p * 2].datr);
		}
		else{
			seg[p].laz = 1;
		}
	}
	else{
		if(seg[p * 2 + 1].datl == askR(p * 2, seg[p * 2 + 1].datl.len)){
			seg[p].datr = seg[p].datr + (seg[p * 2].datr - seg[p * 2 + 1].datl);
		}
		else{
			seg[p].laz = 1;
		}
	}
}
void build(int p, int l, int r){
	seg[p].l = l;
	seg[p].r = r;
	if(l == r){
		if(a[l] > 0){
			seg[p].datr = {a[l], 1ll};
		}
		else{
			seg[p].datl = {-a[l], 1ll};
		}
		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) {
		// cerr << "RECHAGE " << p << ' '<< x << ' ' << v << '\n';
  		if(v > 0){
			seg[p].datr = {v, 1ll};
			seg[p].datl = {0, 0};
		}
		else{
			seg[p].datl = {-v, 1ll};
			seg[p].datr = {0, 0};
		}
		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);
	// cerr << "RE " << p << ' ' << seg[p].datr.len << '\n';
}
int idx[110], tot;
void get_idx(int p, int l, int r){
	if(seg[p].l >= l && seg[p].r <= r){
		idx[++tot] = p;
		return ;
	}
	int mid = (seg[p].l + seg[p].r) >> 1;
	if(l <= mid){
		get_idx(p * 2, l, r);
	}
	if(r > mid){
		get_idx(p * 2 + 1, l, r);
	}
	return ;
}
Hst pdt[110];
Hst askP(int id, int val){
	if(!val) {
		return {0, 0};
	}
	if(val == pdt[id].len) {
		return pdt[id];
	}
	if(val <= seg[idx[id]].datr.len){
		return askR(idx[id], val);
	}
	else{
		return seg[idx[id]].datr + (askP(id - 1, val - seg[idx[id]].datr.len + seg[idx[id]].datl.len) - seg[idx[id]].datl);
	}
}
bool ask(int l, int r){
	tot = 0;
	// cerr << tot << '\n';
	get_idx(1, l, r);
	
	for(int i = 1; i <= tot; i++){
		int p = idx[i];
		if(seg[p].laz) return 0;
		// cerr << i << '\n';
		if(pdt[i - 1].len < seg[p].datl.len) return 0;
		if(seg[p].datl == askP(i - 1, seg[p].datl.len)){
			pdt[i] = seg[p].datr + (pdt[i - 1] - seg[p].datl);
		}
		else{
			return 0;
		}
	}
	return (pdt[tot].len == 0);
}
signed main() {
#ifndef Air
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	n = read();
	read();
	prework(n);
	for(int i = 1; i <= n; i++){
		a[i] = read();
	}
	build(1, 1, n);
	q = read();
	while(q--){
		int op = read(), x = read(), y = read();
		// cerr << op << ' ' << x << ' ' << y << '\n';
		if(op == 1){
			change(1, x, y);
		}
		else{

			if(ask(x, y))
				cout << "Yes" << '\n';
			else
				cout << "No" << '\n';
		}
	}
	return 0;
}

posted @ 2025-12-08 12:32 Air2011 阅读(25) 评论(0) 收藏举报

刷新页面返回顶部

Airland

——『Delightful』

单侧递归线段树

楼房重建

[HNOI/AHOI2018] 转盘

CF1736C2

CF1340F

公告