势能线段树专题

势能线段树(吉司机线段树)

简单介绍和理解#

我们知道传统的支持区间修改的线段树,我们都是靠lazy标记来节省开销的。可以使用lazy标记必须要满足下面两个条件：

区间节点的值可以根据lazy标记来更新.
lazy标记之间可以快速相互合并.

但是很多时候我们要完成的区间修改操作是不能依靠lazy标记来完成的,比如区间开根号，区间位运算。因为这些运算都是依赖于叶子节点的值的。我们无法直接对lazy标记或者是区间的值进行修改。但是如果一直无脑递归到叶子节点,一个一个修改的话，显然时间成本我们是无法接受的。所以我们就要使用势能线段树，其实就是类似于在BFS里进行剪枝。我们发现每一个操作，总会使得其能够接受的继续进行修改的次数越来越少，就好像你一开始位于高空，每次修改会让你的高度下降，当你落到地面时，再对你修改就已经没有意义了。就是这个操作对你而言已经"退化"了。
所以我们可以这样来建立和操作这棵线段树：

在每个节点额外加入一个"势能标记",来记录和维护当前区间结点的势能情况。
对于每次的区间修改，若当前区间内所有结点的势能皆已为零，直接退出递归不再修改.
若当前区间内还存在势能不为零的结点，则继续向下递归，暴力修改要求区间内每一个势能不为零的结点.

题目#

A. 上帝造题的七分钟 2 / 花神游历各国#

链接: https://www.luogu.com.cn/problem/P4145#

题意：#

给定n个数，两种操作：

区间开根号(向下取整)。
区间询问和。

思路：#

显然，我们无法使用lazy标记来节省对区间开根号的开销，因为开根号是由每个叶子节点自己的值决定的。但我们很容易发现当一个数小于等于1以后，再对其开根号是无效的，所以我们可以维护区间最大值作为标记。一旦区间修改时发现此区间的最大值小于等于1时，我们不需要再次修改，直接return即可，否则继续向下递归修改。

代码：#

Copy
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-6;
const ll N = 2e5 + 10;
const ll INF = 1e18+10;
const ll mod = 1e9+7;
#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(a) a.begin(),a.end()
struct node{
	int l, r;
	ll mx, sum;
}tree[4 * N];
ll a[N];
void build(int id, int l, int r){
	tree[id].l = l;
	tree[id].r = r;
	if(l == r){
		tree[id].mx = a[l];
		tree[id].sum = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
	tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}
ll ask(int id, int l, int r){
	int L = tree[id].l ;
	int R = tree[id].r ;
	if(L >= l && R <= r) return tree[id].sum;
	int mid = (L + R) >> 1;
	ll val = 0;
	if(l <= mid) val += ask(id << 1, l, r);
	if(r > mid) val += ask(id << 1 | 1, l, r);
	return val;
}
void change(int id, int l, int r){
	int L = tree[id].l;
	int R = tree[id].r;
	if(tree[id].mx <= 1) return;
	if(L == R) {
		tree[id].mx = sqrt(tree[id].mx);
		tree[id].sum = tree[id].mx;
		return;
	}
	int mid = (L + R) >> 1;
	if(l <= mid ) change(id << 1, l, r);
	if(r > mid ) change(id << 1 | 1, l, r);
	tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
}
int main(){
	ywh666;
	ll n ;
	cin >> n;
	for(int i = 1; i <= n ; i ++) cin >> a[i];
	int q;
	cin >> q;
	build(1, 1, n);
	while(q --){
		int op, l, r;
		cin >> op >> l >> r;
		if(l > r) swap(l, r);
		if(op == 0){
			change(1, l, r);
		}else{
			cout << ask(1, l, r) << endl;
		}
	}
	return 0 ;
}

B. The Child and Sequence#

链接: https://codeforces.com/problemset/problem/438/D#

题意：#

给定n个数，三种操作：

区间询问和。
区间取模。
单点修改。

思路：#

如上题目一样，我们还是无法使用lazy标记来方便的完成区间的修改，但是我们很容易发现如果一个数已经小于模数了，那对其取模与否是没有影响的。所以我们可以维护区间最大值，当区间修改到这个区间时，如果其最大值已经小于模数，我们直接return,否则继续递归修改。

代码：#

Copy
#include<bits/stdc++.h> 
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-6;
const ll N = 1e5 + 10;
const ll INF = 1e18+10;
const ll mod = 1e9+7;
#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(a) a.begin(),a.end()
struct node{
	int l, r;
	ll mx, sum;
}tree[4 * N];
ll a[N];
void build(int id, int l, int r){
	tree[id].l = l;
	tree[id].r = r;
	if(l == r){
		tree[id].mx = a[l];
		tree[id].sum = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
	tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}
ll qurry(int id, int l, int r){
	int L = tree[id].l ;
	int R = tree[id].r ;
	if(L >= l && R <= r) return tree[id].sum;
	int mid = (L + R) >> 1;
	ll val = 0;
	if(l <= mid) val += qurry(id << 1, l, r);
	if(r > mid) val += qurry(id << 1 | 1, l, r);
	return val;
}
void change(int id, int l, int r, int x){
	int L = tree[id].l;
	int R = tree[id].r;
	if(tree[id].mx < x) return;
	if(L == R) {
		tree[id].mx %= x;
		tree[id].sum = tree[id].mx;
		return;
	}
	int mid = (L + R) >> 1;
	if(l <= mid ) change(id << 1, l, r, x);
	if(r > mid ) change(id << 1 | 1, l, r, x);
	tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
}
void change2(int id, int idx, int x){
	if(tree[id].l == tree[id].r ){
		tree[id].mx = x;
		tree[id].sum = x;
		return;
	}
	int mid = (tree[id].l + tree[id].r) >> 1;
	if(idx <= mid) change2(id << 1, idx, x);
	if(idx > mid) change2(id << 1 | 1, idx, x);
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
	tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}
int main(){
	ywh666;
	ll n, m ;
	cin >> n >> m;
	for(int i = 1; i <= n ; i ++) cin >> a[i];
	build(1, 1, n);
	while(m --){
		int op, k, l , r, x;
		cin >> op ;
		if(op == 1){
			cin >> l >> r;
			cout << qurry(1, l, r) << endl;
		}else if(op == 2){
			cin >> l >> r >> x;
			change(1, l, r, x);
		}else{
			cin >> k >> x;
			change2(1, k, x);
		}
	}
	return 0 ;
}

C. SUM and REPLACE#

链接: https://codeforces.com/contest/920/problem/F#

题意：#

定义f(x)=x的因子个数
给定n个数，有两种操作：
1.区间修改x=f(x)。
2.区间询问和。

思路：#

还是一样，标记是无法传递我们的区间修改的。但是我们可以发现一个当的时候，对其操作又是无效的。那么我们还是可以记录一个区间最大值，当区间最大值小于等于的时候就可以直接，否则我们继续向下递归，暴力修改即可。考虑到反复执行操作之后，一个数只会越来越小，而且数字最大不超过，我们可以事先预处理出每个数的因子个数存储下来。修改的时候直接调用即可，避免反复求同一个数所产生的多余开销。

代码：#

Copy
#include<bits/stdc++.h> 
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-6;
const ll N = 3e5 + 10;
const ll M = 1e6;
const ll INF = 1e18+10;
const ll mod = 1e9+7;
#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(a) a.begin(),a.end()
struct node{
	int l, r, mx;
	ll sum;
}tree[4 * N];
int a[M + 7];
int b[N];
void push_up(int id){
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
	tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
}
void build(int id, int l, int r){
	tree[id].l = l;
	tree[id].r = r;;
	if(l == r){
		tree[id].sum = b[l];
		tree[id].mx = b[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	push_up(id);
}
void modify(int id, int l, int r){
	int L = tree[id].l;
	int R = tree[id].r;
	if(tree[id].mx <= 2) return;
	if(L == R){
		tree[id].sum = a[tree[id].sum];
		tree[id].mx = tree[id].sum;
		return;
	}
	int mid = (L + R) >> 1;
	if(l <= mid) modify(id << 1, l, r);
	if(r > mid) modify(id << 1 | 1, l, r);
	push_up(id);
}
ll qurry(int id, int l, int r){
	int L = tree[id].l;
	int R = tree[id].r;
	if(L >= l && R <= r) return tree[id].sum;
	ll sum = 0;
	if(tree[id << 1].r >= l) sum += qurry(id << 1, l, r);
	if(tree[id << 1 | 1].l <= r) sum += qurry(id << 1 | 1, l, r);
	return sum;
}

int main(){
	ywh666;
	for(int i = 1 ; i <= M ; i ++){
		for(int j = i; j <= M ; j += i){
			a[j] ++;
		}
	}
	int n, m;
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++) cin >> b[i];
	build(1, 1, n);
	while(m --){
		int op, l, r;
		cin >> op >> l >> r;
		if(op == 1){
			modify(1, l, r);
		}else{
			cout << qurry(1, l, r) << endl;
		}
	}

	return 0 ;
}

前三题的势能减少情况很明显就可以看出来，只要对这类线段树有所了解，甚至对于剪枝理解较深的话很快就可以做出来。接下来的题目势能的减少稍有难度。

D. And RMQ#

链接: https://codeforces.com/gym/103107/problem/A#

题意：#

给定个数，有三种操作：

区间按位与。
区间询问最大值。

思路：#

显然区间按位与的操作我们仍旧不能使用标记来便捷的完成区间修改。那么我们要怎么来减少操作的开销呢？我们来考虑什么时候对于一个区间而言，做一次操作对于操作的询问的结果是不影响的。我们假设对一个区间内的所有数都按位与，我们发现对于的二进制下是的位，原来区间内所有的数在该位都会变成，那么很显然如果原来的最大值在这些位置上是，其大小会减小很多，我们无法保证在它减小的时候，该区间其他数也会都减小，或者减小的很多。那么我们怎么保证其他的数在按位与以后还是比原来的最大值小呢？稍加思考我们可以发现，对于区间，若 & ，那么这次操作我们可以不做修改。因为此时证明二进制下为的位置在该区间内没有一个数在该位置上为，所以对于每个数都不会减小，也就可以保证原来的最大数还是在该区间最大的。所以我们只要多记录一个区间或的和，在区间修改时如果其满足上述式子，便可以直接，不然继续向下递归，暴力修改即可。

代码：#

Copy
#include<bits/stdc++.h> 
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-9;
const ll N = 4e5 + 10;
const ll INF = 1e18+10;
const ll mod = 1e9+7;
#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(a) a.begin(),a.end()
struct node{
	int l, r, orsum,mx;
}tree[N << 2];
int a[N];
void push_up(int id){
	tree[id].mx = max(tree[id << 1].mx, tree[id << 1 | 1].mx);
	tree[id].orsum = tree[id << 1].orsum | tree[id << 1 | 1].orsum;
}
void build(int id, int l, int r){
	tree[id].l = l;
	tree[id].r = r;
	if(l == r){
		tree[id].mx = a[l];
		tree[id].orsum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	push_up(id);
}
void modify(int id, int l, int r, int x){
	if((tree[id].orsum & x) == tree[id].orsum) return ;
	if(tree[id].l == tree[id].r){
		tree[id].mx &= x;
		tree[id].orsum &= x;
		return;
	}
	if(tree[id << 1].r >= l) modify(id << 1, l, r, x);
	if(tree[id << 1 | 1].l <= r) modify(id << 1 | 1, l, r, x);
	push_up(id);
}
void change(int id, int x, int v){
	if(tree[id].l == tree[id].r){
		tree[id].mx = v;
		tree[id].orsum = v;
		return ;
	}
	if(tree[id << 1].r >= x) change(id << 1, x, v);
	if(tree[id << 1 | 1].l <= x) change(id << 1 | 1, x, v);
	push_up(id);
}
int qurry(int id, int l, int r){
	if(tree[id].l >= l && tree[id].r <= r) return tree[id].mx;
	int val = -1;
	if(tree[id << 1].r >= l) val = max(val, qurry(id << 1, l, r));
	if(tree[id << 1 | 1].l <= r) val = max(val, qurry(id << 1 | 1, l, r));
	return val;
}
int main(){
	ywh666;
	int n, q ;
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	build(1, 1, n);
	while(q --){
		string s;
		cin >> s;
		if(s == "AND"){
			int l, r, x;
			cin >> l >> r >> x;
			modify(1, l, r, x);
		}else if(s == "UPD"){
			int x, v;
			cin >> x >> v;
			change(1, x, v);
		}else{
			int l, r;
			cin >> l >> r;
			cout << qurry(1, l, r) << endl;
		}
	}
	return 0 ;
}

E. Euler Function#

链接:https://pintia.cn/market/tag/1439767147859537920#

签到获得5金币以后花费1金币购买，一次购买只有5小时。(巨坑!!!)

题意：#

给定个数，两种操作：

区间乘法。
区间询问欧拉函数和(对大质数取模)。

思路：#

显然，我们这次终于可以使用标记了。但是它只能帮我们解决操作。我们来思考一下怎么快速解决操作，显然暴力修改是不现实的。我们注意到欧拉函数有这样的性质：
对于一个质数和一个数：
若 = ,则 ,
否则。
我们注意到这个条件的只能是质数的，但是我们进行操作时的数是什么都不保证的，所以我们很自然的可以想到将操作进行转化。我们可以不直接区间乘，我们可以把先分解质因数，在此基础上，将其质因数分别做操作，所以这会使得我们的操作的次数大大增加，但是我们可以更好的维护区间的欧拉函数和。下面我们来介绍操作如何完成。我们利用上面的欧拉函数的性质，当我们操作乘的全是质数的时候，我们只要统计，在这个区间内的所有数的质因数都中是否都存在操作乘的这个数，如果存在，那么我们对于这个区间的欧拉函数和不就又变成了一个区间乘法吗？如果不都存在，我们便可以一直暴力递归下去，一直到叶子节点。再独立判单是否存在，来决定对这个叶子节点的欧拉函数值修改多少。
那么怎么实现呢？考虑到操作的数最大只有，我们完全可以先预处理分解好以内所有数的质因数。但是显然我们在线段树的每个节点除了维护其欧拉函数值以外，我们还要维护这个区间里所有数的共同质因子，但是每次查询的时候单独去分解质因数显然开销是特别大的。所以我们在每个节点可以维护一个，这样不光存储方便，常数小，在push_up的时候我们可以直接将两个按位与，快速得到共同质因子。

代码：#

(预处理写的有点丑，筛法部分大家可以自己用更快的)

Copy
#include<bits/stdc++.h> 
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-9;
const ll N = 1e5 + 10;
const ll INF = 1e18+10;
const ll mod = 998244353;
const ll maxm = 110;
#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define all(a) a.begin(),a.end()
struct node{
	int l, r;
	ll sum, lz;
	bitset<30> bt;
}tree[N << 2];
int a[N], phi[maxm];
bitset<30> sat[maxm];
int bh[maxm];
int bh2[maxm];
void init(){
	bh[2] = 1;
	bh[3] = 2;
	bh2[1] = 2;
	bh2[2] = 3;
	int st = 3;
	for(int i = 4; i <= 100 ; i ++){
		bool f = 1;
		for(int j = 2 ; j * j <= i ; j ++){
			if(i % j == 0){
				f = 0;
				break;
			}
		}
		if(f){
			bh[i] = st ;
			bh2[st] = i;
			st ++;
		}
	}
	for(int i = 2; i <= 100 ; i ++){
		if(bh[i] != 0){
			for(int j = i ; j <= 100 ; j += i){
				sat[j][bh[i]] = 1;
			}
		}
	}

}
void euler(int n = 100){
	for(int i = 2 ; i <= n ; i ++) phi[i] = i;
	for(int i = 2 ; i <= n ; i ++){
		if(phi[i] == i){
			for(int j = i ; j <= n ; j += i){
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	phi[1] = 1;
}
void push_up(int id){
	tree[id].bt = tree[id << 1].bt & tree[id << 1 | 1].bt;
	tree[id].sum = tree[id << 1].sum  + tree[id << 1 | 1].sum ;
	tree[id].sum %= mod;
}
void push_down(int id){
	tree[id << 1].sum =tree[id << 1].sum * tree[id].lz  % mod ;
	tree[id << 1 | 1].sum =tree[id << 1 | 1].sum * tree[id].lz % mod ;
	tree[id << 1].lz = tree[id << 1].lz * tree[id].lz % mod;
	tree[id << 1 | 1].lz =tree[id << 1 | 1].lz * tree[id].lz % mod;
	tree[id].lz = 1;
}

void build(int id, int l, int r){
	tree[id].l = l;
	tree[id].r = r;
	tree[id].lz = 1;
	if(l == r){
		tree[id].sum = phi[a[l]];
		tree[id].bt = sat[a[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	push_up(id);
}

void modify(int id, int l, int r, int x){
	if(tree[id].l >= l && tree[id].r <= r){
		if(tree[id].bt[bh[x]]){
			tree[id].lz = 1ll * tree[id].lz * x % mod;
			tree[id].sum = 1ll * tree[id].sum * x % mod;
			return;
		}
		if(tree[id].l == tree[id].r){
			tree[id].lz = 1ll * tree[id].lz * (x - 1) % mod;
			tree[id].sum = 1ll * tree[id].sum * (x - 1) % mod;
			tree[id].bt[bh[x]] = 1;
			return;
		}
	}
	push_down(id);
	if(tree[id << 1].r >= l) modify(id << 1, l, r, x);
	if(tree[id << 1 | 1].l <= r) modify(id << 1 | 1, l, r, x);
	push_up(id);
}
int qurry(int id, int l, int r){
	if(tree[id].l >= l && tree[id].r <= r) return tree[id].sum % mod;
	ll val = 0;
	push_down(id);
	if(tree[id << 1].r >= l) val += qurry(id << 1, l, r);
	if(tree[id << 1 | 1].l <= r) val += qurry(id << 1 | 1, l, r);
	return val % mod;
}
int main(){
	ywh666;
	init();
	euler();
	int n, q ;
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	build(1, 1, n);
	while(q --){
		int op;
		cin >> op;
		if(op == 0){
			int l, r, x;
			cin >> l >> r >> x;
			while(x != 1){
				int nn = x;
				for(int i = 1; i <= 29 ; i ++){
					if(sat[x][i]== 1){
						modify(1, l, r, bh2[i]);
						nn /= bh2[i];
					}
				}
				x = nn;
			}
		}else{
			int l, r;
			cin >> l >> r;
			cout << qurry(1, l, r) % mod << endl;
		}
	}
	return 0 ;
}

F.#

相关阅读:
Zero-Copy零拷贝
 深度学习-卷积神经网络
 MapStruct复制对象详细介绍
 flask-socketio实现websocket通信
 【论文笔记】FCN全卷积网络
 opencv形态学-腐蚀
 科学技术创新杂志科学技术创新杂志社科学技术创新编辑部2022年第24期目录
 Mysql索引失效的几种情况总结
 Sui Gaming AMA精彩内容集锦
 http post协议实现简单的rpc协议，WireShark抓包分析
原文地址：https://www.cnblogs.com/ywhO3Olsq/p/16120157.html