特色栏目： python 批处理 net编程 Javascript Php Asp Css Html5 Android seo centos

势能线段树专题

来源：互联网收集：自由互联发布时间：2022-05-15

势能线段树(吉司机线段树)简单介绍和理解我们知道传统的支持区间修改的线段树,我们都是靠 $lazy$ 标记来节省开销的。可以使用 $lazy$ 标记必须要满足下面两个条件：区间节点的值

势能线段树(吉司机线段树) 简单介绍和理解

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

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

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

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

题目 A. 上帝造题的七分钟 2 / 花神游历各国链接: https://www.luogu.com.cn/problem/P4145 题意：

给定$n$个数，两种操作：

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

思路：

显然，我们无法使用$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$个数，三种操作：

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

思路：

如上题目一样，我们还是无法使用$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$个数，有三种操作：

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

思路：

显然区间按位与的操作我们仍旧不能使用$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$个数，两种操作：

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

思路：

显然，我们这次终于可以使用$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. 【文章原创作者：高防ip http://www.558idc.com/gfip.html欢迎留下您的宝贵建议】

上一篇：腾讯云OCR服务二次开发
下一篇：没有了

势能线段树专题

相关文章