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

P4041 学习笔记

news 2026/5/12 17:36:40

毒瘤线段树。

题目传送门

这个题目需要实现 \(4\) 个操作：

操作 \(1\)：将结果加上 \(a\)；
操作 \(2\)：将结果减去 \(a\)；
操作 \(3\)：将结果乘上 \(a\)；
操作 \(4\)：将结果加上 \(a \times X\)。

考虑建一个线段树，维护区间最大值，区间最小值，加的懒惰标记，乘的懒惰标记，赋值的懒惰标记，和毒瘤操作 \(4\) 的懒惰标记。

建树

正常建树即可，要注意的在注释里。

void build(ll p, ll pl, ll pr){addtag[p] = 0; // 全局变量默认为 0，不加也行multag[p] = 1; // 注意乘法标记初始化为 1opt4tag[p] = 0;modifytag[p] = 0;if (pl == pr){ // 下面就是正常操作了maxtree[p] = mintree[p] = a[pl].val;return;}ll mid = (pl + pr) >> 1;build(ls(p), pl, mid);build(rs(p), mid + 1, pr);pushup(p);
}

加法标记修改

正常修改。

void make_addtag(ll p, ll d){addtag[p] += d;maxtree[p] += d;mintree[p] += d;
}

乘法标记修改

根据这个题目的经验，改乘法标记的时候应当把加法标记也改一遍。

void make_multag(ll p, ll d){addtag[p] *= d;multag[p] *= d;opt4tag[p] *= d;maxtree[p] *= d;mintree[p] *= d;
}

操作 \(4\) 标记修改

按照操作 \(4\) 的要求修改即可。

void make_opt4tag(ll p, ll pl, ll pr, ll d){mintree[p] += a[pl].val * d;maxtree[p] += a[pr].val * d;opt4tag[p] += d;
}

赋值标记修改

所有东西回归原始状态即可。

void make_modifytag(ll p, ll d){addtag[p] = 0;multag[p] = 1;opt4tag[p] = 0;modifytag[p] = d;maxtree[p] = d;mintree[p] = d;
}

大下传

整合即可，注意顺序！！！（否则你会蜜汁 WA）

void pushdown(ll p, ll pl, ll pr){ll mid = (pl + pr) >> 1;if (modifytag[p]){make_modifytag(ls(p), modifytag[p]);make_modifytag(rs(p), modifytag[p]);modifytag[p] = 0;}if (multag[p] != 1){ // 别判错了make_multag(ls(p), multag[p]);make_multag(rs(p), multag[p]);multag[p] = 1;}if (addtag[p]){make_addtag(ls(p), addtag[p]);make_addtag(rs(p), addtag[p]);addtag[p] = 0;}if (opt4tag[p]){make_opt4tag(ls(p), pl, mid, opt4tag[p]);make_opt4tag(rs(p), mid + 1, pr, opt4tag[p]);opt4tag[p] = 0;}
}

为什么要注意顺序呢？原理很简单，因为有些东西修改的时候会修改其他东西。

区间修改

分区间 max 和区间 min 修改。

注意下界 \(l\) 和上界 \(r\)。

void min_update(ll p, ll pl, ll pr){if (mintree[p] >= r){ // 最小值都大于 r，说明整个区间都大于 r，直接修改即可make_modifytag(p, r);return;}if (maxtree[p] <= r || pl == pr)// 最小值小于 r，说明整个区间都小于 r，无需修改return;pushdown(p, pl, pr);ll mid = (pl + pr) >> 1;min_update(ls(p), pl, mid);min_update(rs(p), mid + 1, pr);pushup(p);
}void max_update(ll p, ll pl, ll pr){if (maxtree[p] <= l){ // 和上面同理make_modifytag(p, l);return;}if (mintree[p] >= l || pl == pr)return;pushdown(p, pl, pr);ll mid = (pl + pr) >> 1;max_update(ls(p), pl, mid);max_update(rs(p), mid + 1, pr);pushup(p);
}

求答案

类似建树一样的操作递归求解即可。

void get_ans(ll p, ll pl, ll pr){if (pl == pr){ans[a[pl].idx] = maxtree[p];return ;}pushdown(p, pl, pr);ll mid = (pl + pr) >> 1;get_ans(ls(p), pl, mid);get_ans(rs(p), mid + 1, pr);
}

完整 code

/*********************************************************** Author        : dingziyang888* Website       : https://www.luogu.com.cn/problem/* Created Time  :* FileName      :* Warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!* 1.MLE?* 2.array size enough?* 3.long long?* 4.overflow long long?* 5.multiple task cleaned?* 6.freopen?* 7.TLE?* *******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#define I using
#define AK namespace
#define IOI std
#define A return
#define C 0
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
I AK IOI;using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxn = 1e5 + 5;struct node{ll val, idx;bool operator < (const node &k) const{return this->val < k.val;// 爱放里面放里面，爱放外面放外面}
} a[maxn];ll n, l, r, q;
char ch;ll x[maxn], opt[maxn], ans[maxn], maxtree[maxn << 2], mintree[maxn << 2], addtag[maxn << 2], multag[maxn << 2], opt4tag[maxn << 2], modifytag[maxn << 2];// 这个四倍空间别忘开了ll ls(ll p){return p << 1;
}ll rs(ll p){return p << 1 | 1;
}void pushup(ll p){maxtree[p] = max(maxtree[ls(p)], maxtree[rs(p)]);mintree[p] = min(mintree[ls(p)], mintree[rs(p)]);
}void build(ll p, ll pl, ll pr){addtag[p] = 0;multag[p] = 1;opt4tag[p] = 0;modifytag[p] = 0;if (pl == pr){maxtree[p] = mintree[p] = a[pl].val;return;}ll mid = (pl + pr) >> 1;build(ls(p), pl, mid);build(rs(p), mid + 1, pr);pushup(p);
}void make_addtag(ll p, ll d){addtag[p] += d;maxtree[p] += d;mintree[p] += d;
}void make_multag(ll p, ll d){addtag[p] *= d;multag[p] *= d;opt4tag[p] *= d;maxtree[p] *= d;mintree[p] *= d;
}void make_opt4tag(ll p, ll pl, ll pr, ll d){mintree[p] += a[pl].val * d;maxtree[p] += a[pr].val * d;opt4tag[p] += d;
}void make_modifytag(ll p, ll d){addtag[p] = 0;multag[p] = 1;opt4tag[p] = 0;modifytag[p] = d;maxtree[p] = d;mintree[p] = d;
}void pushdown(ll p, ll pl, ll pr){ll mid = (pl + pr) >> 1;if (modifytag[p]){make_modifytag(ls(p), modifytag[p]);make_modifytag(rs(p), modifytag[p]);modifytag[p] = 0;}if (multag[p] != 1){make_multag(ls(p), multag[p]);make_multag(rs(p), multag[p]);multag[p] = 1;}if (addtag[p]){make_addtag(ls(p), addtag[p]);make_addtag(rs(p), addtag[p]);addtag[p] = 0;}if (opt4tag[p]){make_opt4tag(ls(p), pl, mid, opt4tag[p]);make_opt4tag(rs(p), mid + 1, pr, opt4tag[p]);opt4tag[p] = 0;}
}void min_update(ll p, ll pl, ll pr){if (mintree[p] >= r){make_modifytag(p, r);return;}if (maxtree[p] <= r || pl == pr)return;pushdown(p, pl, pr);ll mid = (pl + pr) >> 1;min_update(ls(p), pl, mid);min_update(rs(p), mid + 1, pr);pushup(p);
}void max_update(ll p, ll pl, ll pr){if (maxtree[p] <= l){make_modifytag(p, l);return;}if (mintree[p] >= l || pl == pr)return;pushdown(p, pl, pr);ll mid = (pl + pr) >> 1;max_update(ls(p), pl, mid);max_update(rs(p), mid + 1, pr);pushup(p);
}void get_ans(ll p, ll pl, ll pr){if (pl == pr){ans[a[pl].idx] = maxtree[p];return ;}pushdown(p, pl, pr);ll mid = (pl + pr) >> 1;get_ans(ls(p), pl, mid);get_ans(rs(p), mid + 1, pr);
}int main() {freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);fast;cin >> n >> l >> r;for (ll i = 1; i <= n; i++){cin >> ch >> x[i];if (ch == '+')opt[i] = 1;else if (ch == '-')opt[i] = 2;else if (ch == '*')opt[i] = 3;else opt[i] = 4;}cin >> q;for (ll i = 1; i <= q; i++)cin >> a[i].val, a[i].idx = i;sort (a + 1, a + q + 1);build(1, 1, q);for (ll i = 1; i <= n; i++){if (opt[i] == 1)make_addtag(1, x[i]);else if (opt[i] == 2)make_addtag(1, -x[i]);// 减去即加上它的相反数else if (opt[i] == 3)make_multag(1, x[i]);else make_opt4tag(1, 1, q, x[i]);min_update(1, 1, q);max_update(1, 1, q);}get_ans(1, 1, q);for (int i = 1; i <= q; i++)cout << ans[i] << endl;A C;
}

查看全文

http://www.jsqmd.com/news/351234/