势能线段树专题

牛客竞赛数据结构专题班势能线段树、李超线段树
zngg的题解

势能线段树模板题一
题意：
操作一：对区间 [ l , r ] [l,r] [l,r] 每个数 x x x 取 x sqrt{x} x ​
操作二：求区间 [ l , r ] [l,r] [l,r] 的和

思路一：
我们没有办法直接对区间进行开方然后下传，所以pushdown就没必要写了。
对于每个数，开方6次之后达到势能上限，其结果必然为0或者1。那么对于整个区间，
可以记录开方次数（取区间内开方次数最少的那个值）是否达到6就可以了，
或者只要一个区间全为0或1的话，也可以直接返回。
code：

#include
#define ll long long
#define lc (p << 1)
#define rc (p << 1 | 1)
#define endl 'n'
using namespace std;
const int maxn = 2e5 + 9;
int n, m;
ll tr[maxn << 2], cnt[maxn << 2];
inline void pushup(int p)
{
	tr[p] = tr[lc] + tr[rc];
	cnt[p] = min(cnt[lc], cnt[rc]);
}
void build(int p = 1, int cl = 1, int cr = n)
{
	if(cl == cr){
		cin >> tr[p];
		return;
	}
	int mid = (cl + cr) >> 1;
	build(lc, cl, mid);
	build(rc, mid + 1, cr);
	pushup(p);
}
ll query(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(cl >= l && cr <= r) return tr[p];
	ll mid = (cl + cr) >> 1, ans = 0;
	if(mid >= l) ans += query(l, r, lc, cl, mid);
	if(mid < r) ans += query(l, r, rc, mid + 1, cr);
	return ans;
}
void update(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(cnt[p] > 5) return;
	if(cl == cr){
		tr[p] = (int)sqrt(tr[p]);
		++cnt[p];
		return;
	}
	int mid = (cl + cr) >> 1;
	if(mid >= l) update(l, r, lc, cl, mid);
	if(mid < r) update(l, r, rc, mid + 1, cr);
	pushup(p);
}
void work()
{
	cin >> n >> m;
	build();
	while(m--)
	{
		int op, l, r;cin >> op >> l >> r;
		if(op == 1) update(l, r);
		else cout << query(l, r) << endl;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	work();
	return 0;
}

思路二：
框架基本一样
维护区间最大值，如果区间最大值为 1 1 1，则没必要修改
code：

#include
#define ll long long
#define lc (p << 1)
#define rc (p << 1 | 1)
#define endl 'n'
using namespace std;
const int maxn = 2e5 + 9;
const ll inf = 0x3f3f3f3f3f3f;
int n, m;
ll tr[maxn << 2], Max[maxn << 2];
inline void pushup(int p)
{
	tr[p] = tr[lc] + tr[rc];
	Max[p] = max(Max[lc], Max[rc]);
}
void build(int p = 1, int cl = 1, int cr = n)
{
	Max[p] = - inf;// 因为 ai 始终是正的，所以不置为 -inf，初始全是 0 也是一样的
	if(cl == cr){
		cin >> tr[p];
		return;
	}
	int mid = (cl + cr) >> 1;
	build(lc, cl, mid);
	build(rc, mid + 1, cr);
	pushup(p);
}
ll query(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(cl >= l && cr <= r) return tr[p];
	ll mid = (cl + cr) >> 1, ans = 0;
	if(mid >= l) ans += query(l, r, lc, cl, mid);
	if(mid < r) ans += query(l, r, rc, mid + 1, cr);
	return ans;
}
void update(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(Max[p] == 1) return;
	if(cl == cr){
		tr[p] = (int)sqrt(tr[p]);
		Max[p] = tr[p];
		return;
	}
	int mid = (cl + cr) >> 1;
	if(mid >= l) update(l, r, lc, cl, mid);
	if(mid < r) update(l, r, rc, mid + 1, cr);
	pushup(p);
}
void work()
{
	cin >> n >> m;
	build();
	while(m--)
	{
		int op, l, r;cin >> op >> l >> r;
		if(op == 1) update(l, r);
		else cout << query(l, r) << endl;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	work();
	return 0;
}

势能线段树模板题二
题意：
操作一：对区间 [ l , r ] [l,r] [l,r] 每个数 x x x 取 x sqrt{x} x ​
操作二：对区间 [ l , r ] [l,r] [l,r] 每个数 加 c c c
操作三：求区间 [ l , r ] [l,r] [l,r] 的和
思路：
带修改的区间开方
我们发现对于一个序列，如果开方的前后，最大值的变化量等于最小值的变化量，那么其实这就是一个区间减的操作（因为显然这个变化量是有单调性的），因此我们只需要维护区间最大值和区间最大值即可，然后暴力修改，遇到满足条件的就区间减，然后直接return

code：

#include
#define ll long long
#define lc (p << 1)
#define rc (p << 1 | 1)
#define endl 'n'
using namespace std;
const int maxn = 2e5 + 9;
const ll inf = 0x3f3f3f3f3f3f;
ll n, m;
ll a[maxn];
struct node
{
	ll add, sum, Max, Min;
}tr[maxn << 2];

inline void addlazy(int p, int len, ll x)
{
	tr[p].add += x;
	tr[p].sum += 1ll * len * x;
	tr[p].Max += x;
	tr[p].Min += x;
}
inline void pushup(int p)
{
	tr[p].sum = tr[lc].sum + tr[rc].sum;
	tr[p].Max = max(tr[lc].Max, tr[rc].Max);
	tr[p].Min = min(tr[lc].Min, tr[rc].Min);
}
inline void pushdown(int p, int len)
{
	if(!tr[p].add) return;
	addlazy(lc, len - len / 2, tr[p].add);
	addlazy(rc, len / 2, tr[p].add);
	tr[p].add = 0;
}
void build(int p = 1, int cl = 1, int cr = n)
{
	tr[p].Max = -inf; tr[p].Min = inf;
	if(cl == cr){
		tr[p].Max = tr[p].Min = tr[p].sum = a[cl];
		return;
	}
	int mid = (cl + cr) >> 1;
	build(lc, cl, mid);
	build(rc, mid + 1, cr);
	pushup(p);
}
ll query(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(cl >= l && cr <= r) return tr[p].sum;
	pushdown(p, cr - cl + 1);
	ll mid = (cl + cr) >> 1, ans = 0;
	if(mid >= l) ans += query(l, r, lc, cl, mid);
	if(mid < r) ans += query(l, r, rc, mid + 1, cr);
	return ans;
}
void update(int l, int r, ll d, int p = 1, int cl = 1, int cr = n)
{
	if(cl >= l && cr <= r){
		if(d == -1)
		{
			ll fx = tr[p].Max - (ll)sqrt(tr[p].Max);
			ll fy = tr[p].Min - (ll)sqrt(tr[p].Min);
			if(fx == fy) {
				addlazy(p, cr - cl + 1, -fx);return;
			}
		}
		else if(d != -1) {
			addlazy(p, cr - cl + 1, d);return;
		}
	}
	pushdown(p, cr - cl + 1);
	int mid = (cl + cr) >> 1;
	if(mid >= l) update(l, r, d, lc, cl, mid);
	if(mid < r) update(l, r, d, rc, mid + 1, cr);
	pushup(p);
}
void work()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	build();
	while(m--)
	{
		ll op, l, r;cin >> op >> l >> r;
		if(op == 1) update(l, r, -1);
		else if(op == 2){
			ll k;cin >> k; update(l, r, k);
		}
		else cout << query(l, r) << endl;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	work();
	return 0;
}

Gorgeous Sequence
题意：
三个操作

1. 对区间 [ l , r ] [l,r] [l,r] ，每个数与 t t t 取 m i n min min，即 a i = m i n ( a i , t ) a_i=min(a_i,t) ai​=min(ai​,t)
2. 查询区间 [ l , r ] [l,r] [l,r] 最大值
3. 查询区间 [ l , r ] [l,r] [l,r] 所有元素之和

思路：
区间取 m i n min min，意味着只对那些大于 t t t 的数有更改。因此这个操作的对象不再是整个区间，而是“这个区间中大于 t t t 的数”。于是我们可以有这样的思路：每个结点维护该区间的最大值 M a x Max Max 、次大值 S e m a x Semax Semax、区间和 S u m Sum Sum 以及最大值的个数 C n t Cnt Cnt。接下来我们考虑区间对 t t t 取 m i n min min 的操作。

1. 如果 M a x < = t Max<=t Max<=t，显然这个 t t t 是没有意义的，直接 r e t u r n return return
2. 如果 S e m a x < t < M a x Semax
3. 如果 t < = S e m a x t<=Semax t<=Semax，这种情况我们不知道涉及多少数的过呢更新，就暴力递归向下操作，然后上传信息。

复杂度 O ( m   l o g   n ) O(m log n) O(m log n)
code：

#include
#define ls (p << 1)
#define rs (p << 1 | 1)
#define ll long long
using namespace std;
const int maxn = 1e6 + 9;
int n, m;
struct node
{
	ll sum;
	int Max, Semax, cnt, mark;	
}tr[maxn << 2];
inline void pushlazy(int p, int x)
{
	if(tr[p].Max <= x) return;
	tr[p].sum += (1ll * x - tr[p].Max) * tr[p].cnt;
	tr[p].Max = tr[p].mark = x;
}
inline void pushdown(int p)
{
	if(tr[p].mark == -1) return;
	pushlazy(ls, tr[p].mark);
	pushlazy(rs, tr[p].mark);
	tr[p].mark = -1;
}
inline pushup(int p)
{
	tr[p].sum = tr[ls].sum + tr[rs].sum;
	if(tr[ls].Max == tr[rs].Max)
	{
		tr[p].Max = tr[ls].Max;
		tr[p].Semax = max(tr[ls].Semax, tr[rs].Semax);
		tr[p].cnt = tr[ls].cnt + tr[rs].cnt;
	}
	else if(tr[ls].Max > tr[rs].Max)
	{
		tr[p].Max = tr[ls].Max;
		tr[p].Semax = max(tr[ls].Semax, tr[rs].Max);
		tr[p].cnt = tr[ls].cnt;
	}
	else 
	{
		tr[p].Max = tr[rs].Max;
		tr[p].Semax = max(tr[ls].Max, tr[rs].Semax);
		tr[p].cnt = tr[rs].cnt;
	}
}
void build(int p = 1, int cl = 1, int cr = n)
{
	tr[p].mark = -1;
	if(cl == cr){
		cin >> tr[p].sum;
		tr[p].Max = tr[p].sum;
		tr[p].cnt = 1;
		tr[p].Semax = -1;
		return;
	}
	int mid = (cl + cr) >> 1;
	build(ls, cl, mid);
	build(rs, mid + 1, cr);
	pushup(p);
}
void update(int l, int r, int d, int p = 1, int cl = 1, int cr = n)
{
	if(tr[p].Max <= d) return;
	if(cl >= l && cr <= r && tr[p].Semax < d){
		pushlazy(p, d);
		return;
	}
	int mid = (cl + cr) >> 1;
	pushdown(p);
	if(mid >= l) update(l, r, d, ls, cl, mid);
	if(mid < r) update(l, r, d, rs, mid + 1, cr);
	pushup(p);
}
int query_max(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(cl >= l && cr <= r) return tr[p].Max;
	int mid = (cl + cr) >> 1, ans1 = -1, ans2 = -1;
	pushdown(p);
	if(mid >= l) ans1 = max(ans1, query_max(l, r, ls, cl, mid));
	if(mid < r) ans2 = max(ans2, query_max(l, r, rs, mid + 1, cr));
	return max(ans1, ans2);
}
ll query_sum(int l, int r, int p = 1, int cl = 1, int cr = n)
{
	if(cl >= l && cr <= r) return tr[p].sum;
	pushdown(p);
	ll mid = (cl + cr) >> 1, ans = 0;
	if(mid >= l) ans += query_sum(l, r, ls, cl, mid);
	if(mid < r) ans += query_sum(l, r, rs, mid + 1, cr);
	return ans;
}
void work()
{
	cin >> n >> m;
	build();
	while(m--)
	{
		int op, l, r, d;
		cin >> op >> l >> r;
		if(!op){
			cin >> d; update(l, r, d);
		}
		else if(op == 1) cout << query_max(l, r) << endl;
		else cout << query_sum(l, r) << endl;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}