势能线段树专题

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

简单介绍和理解

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

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

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

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

题目

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

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

题意：

给定\(n\)个数，两种操作：

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

思路：

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

代码：

#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\)个数，三种操作：

1. 区间询问和。
2. 区间取模。
3. 单点修改。

思路：

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

代码：

#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.区间询问和。

思路：

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

代码：

#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

题意：

给定\(n\)个数，有三种操作：

1. 区间按位与。
2. 区间询问最大值。

思路：

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

代码：

#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小时。(巨坑!!!)

题意：

给定\(n\)个数，两种操作：

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

思路：

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

代码：

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

#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.