当前位置：首页 > news >正文

线段树区间赋值 + 区间加减 + 求区间最值

news 2025/8/14 7:18:07

线段树好题：P1253 扶苏的问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间赋值 + 区间加减 + 求区间最大。

对于区间赋值和区间加减来说，需要两个懒标记，一个表示赋值cover，一个表示加减add。

区间赋值的优先级大于区间加减。

对于区间赋值来说，需要将区间加减的标记重置，因为赋值完后，之前的区间加减队现在的值没有影响。

void coverdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.cover != -INF) {left.add = right.add = 0;left.ma = right.ma = root.cover;left.cover = right.cover = root.cover;root.cover = -INF;}
}

对于区间加减来说，需要先用区间赋值得到最新的值，之后再进行加减操作。

void sumdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.add) {coverdown(u);left.ma += root.add; right.ma += root.add;left.add += root.add; right.add += root.add;root.add = 0;}    
}

线段树中一般的pushdown的顺序不变，但是在pushdown函数中，需要先执行coverdown再执行sumdown。

void pushdown(int u) {coverdown(u); sumdown(u);
}

区间加减时，只需要先进行区间赋值就行。

void modify_add(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {coverdown(u);tr[u].ma += d;tr[u].add += d;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_add(ls(u), l ,r, d);if(r > mid) modify_add(rs(u), l, r, d);pushup(u);}
}

区间赋值时，需要先将区间加减懒标记重置，其他一样。

void modify_cover(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {tr[u].add = 0;tr[u].ma = d;tr[u].cover = d;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_cover(ls(u), l, r, d);if(r > mid) modify_cover(rs(u), l, r, d);pushup(u);}
}

AC代码：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;// #define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pair<int,int> PII;const int INF = 1e18;
const int N = 1e6 + 21;// 当输入数据大于 1e6 时用快读
inline int fread() // 快读
{int x = 0, f = 1; char ch = getchar();while(ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar(); }while(ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * f;
}int w[N],n,m; // 注意 w[N] 开LL ( https://www.luogu.com.cn/problem/P2357
struct adt {int l,r;int ma,add,cover;
}tr[N << 2];
// 左子树
inline int ls(int p) {return p<<1; }
// 右子树
inline int rs(int p) {return p<<1|1; }
// 向上更新
void pushup(int u) {tr[u].ma = max(tr[ls(u)].ma, tr[rs(u)].ma);
}void coverdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.cover != -INF) {left.add = right.add = 0;left.ma = right.ma = root.cover;left.cover = right.cover = root.cover;root.cover = -INF;}
}
void sumdown(int u) {auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];if(root.add) {coverdown(u);left.ma += root.add; right.ma += root.add;left.add += root.add; right.add += root.add;root.add = 0;}    
}
void pushdown(int u) {coverdown(u); sumdown(u);
}
// 建树
void build(int u, int l, int r) {if(l == r) tr[u] = {l, r, w[r], 0, -INF};else {tr[u] = {l,r, 0, 0, -INF}; // 容易忘int mid = l + r >> 1;build(ls(u), l, mid), build(rs(u), mid + 1, r);pushup(u);}
}
// 修改
void modify_add(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {coverdown(u);tr[u].ma += d;tr[u].add += d;}else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_add(ls(u), l ,r, d);if(r > mid) modify_add(rs(u), l, r, d);pushup(u);}
}
void modify_cover(int u, int l, int r, int d) {if(tr[u].l >= l && tr[u].r <= r) {tr[u].add = 0;tr[u].ma = d;tr[u].cover = d;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify_cover(ls(u), l, r, d);if(r > mid) modify_cover(rs(u), l, r, d);pushup(u);}
}
// 查询
LL query(int u, int l, int r) {if(tr[u].l >= l && tr[u].r <= r) {return tr[u].ma;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL res = -INF;if(l <= mid) res = query(ls(u), l, r);if(r > mid ) res =max(res, query(rs(u), l, r));return res;
}void inpfile();
void solve() {int n,q; cin>>n>>q;for(int i = 1; i <= n; ++i) w[i] = fread();build(1,1,n);while(q--) {// int opt,l,r,x; cin>>opt>>l>>r;int opt = fread(), l = fread(), r = fread();if(opt == 1) {// cin>>x;int x = fread();modify_cover(1,l,r,x);} else if(opt == 2) {// cin>>x;int x = fread();modify_add(1,l,r,x);} else {cout<<query(1,l,r)<<'\n';}}
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cin>>T;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen("ANSWER.txt", "w",stdout);#endif
}