势能线段树专题

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

简单介绍和理解

我们知道传统的支持区间修改的线段树,我们都是靠\(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.

 2 total views,  1 views today

页面下部广告