线段树之懒标记和扫描线

pushdown&＃xff0c;专门解决区间修改的操作

带懒标记的线段树通常会有标记

一个简单的整数

懒标记&＃xff1a;所有被当前区间覆盖&＃xff0c;或者所有以当前区间为根节点的子树里面&＃xff0c;给子树里面每一个数添加一个数&＃xff08;特殊规定一下不包括当前节点&＃xff0c;也可以包含当前节点&＃xff0c;前后一致就行&＃xff09;

查询和修改函数要做一些改变

所以就进行一个操作就是&＃xff0c;查询的时候&＃xff0c;递归到当前点&＃xff0c;如果上面有标记&＃xff0c;就把标记清空&＃xff0c;把数加上&＃xff0c;递归到下一个

如图

有线段树的题目&＃xff0c;最重要的就是看一下线段树要维护什么

区间修改&＃xff0c;区间求和

一般pushdown放前边&＃xff0c;pushup放后面

#include
#include
#include
#include using namespace std;
#define int long long
typedef long long LL;const int N &＃61; 100010;int n, m;
int w[N];
struct Node
{int l, r;LL sum, add;
}tr[N * 4];void pushup(int u)
{tr[u].sum &＃61; tr[u << 1].sum &＃43; tr[u << 1 | 1].sum;
}void pushdown(int u)
{auto &root &＃61; tr[u], &left &＃61; tr[u << 1], &right &＃61; tr[u << 1 | 1];if (root.add){left.add &＃43;&＃61; root.add, left.sum &＃43;&＃61; (LL)(left.r - left.l &＃43; 1) * root.add;right.add &＃43;&＃61; root.add, right.sum &＃43;&＃61; (LL)(right.r - right.l &＃43; 1) * root.add;root.add &＃61; 0;}
}void build(int u, int l, int r)
{if (l &＃61;&＃61; r) tr[u] &＃61; {l, r, w[r], 0};else{tr[u] &＃61; {l, r};int mid &＃61; l &＃43; r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid &＃43; 1, r);pushup(u);}
}void modify(int u, int l, int r, int d)
{if (tr[u].l >&＃61; l && tr[u].r <&＃61; r){tr[u].sum &＃43;&＃61; (LL)(tr[u].r - tr[u].l &＃43; 1) * d;tr[u].add &＃43;&＃61; d;}else // 一定要分裂{pushdown(u);int mid &＃61; tr[u].l &＃43; tr[u].r >> 1;if (l <&＃61; mid) modify(u << 1, l, r, d);if (r > mid) modify(u << 1 | 1, l, r, d);pushup(u);}
}LL query(int u, int l, int r)
{if (tr[u].l >&＃61; l && tr[u].r <&＃61; r) return tr[u].sum;pushdown(u);int mid &＃61; tr[u].l &＃43; tr[u].r >> 1;LL sum &＃61; 0;if (l <&＃61; mid) sum &＃61; query(u << 1, l, r);if (r > mid) sum &＃43;&＃61; query(u << 1 | 1, l, r);return sum;
}signed main()
{scanf("%lld%lld", &n, &m);for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; ) scanf("%lld", &w[i]);build(1, 1, n);char op[2];int l, r, d;while (m -- ){scanf("%s%lld%lld", op, &l, &r);if (*op &＃61;&＃61; &＃39;C&＃39;){scanf("%lld", &d);modify(1, l, r, d);}else printf("%lld\n", query(1, l, r));}return 0;
}
扫描线

其实就是一个积分的思想
大佬说先学基础&＃xff0c;咕了
例题

因为乘和加的优先级不同&＃xff0c;所以&＃xff0c;不好用俩个变量维护

于是&＃xff0c;我们规定&＃xff0c;sum表示的是 每个数*mul&＃43;add的总和&＃xff0c;就是先乘再加&＃xff0c;人为规定优先级

可推导出如上图中的结论

维护序列

由于题目中有乘也有加&＃xff0c;需要特判或者写两个函数比较麻烦&＃xff0c;所以这里统一将每个操作&＃xff0c;都看作&＃xff0c;对于任意一个数x&＃xff0c;是x*c &＃43; d

除法可以看作乘倒数

#include
using namespace std;
#define endl &＃39;\n&＃39;
const int N &＃61; 100010;
#define LL long long
#define int long longint n, p, m;
int w[N];
struct Node
{int l, r;int sum, add, mul;
}tr[N * 4];void pushup(int u)
{tr[u].sum &＃61; (tr[u << 1].sum &＃43; tr[u << 1 | 1].sum) % p;
}void eval(Node &t, int add, int mul)//发现这个操作用的比较多
{t.sum &＃61; ((LL)t.sum * mul &＃43; (LL)(t.r - t.l &＃43; 1) * add) % p;t.mul &＃61; (LL)t.mul * mul % p;t.add &＃61; ((LL)t.add * mul &＃43; add) % p;
}void pushdown(int u)
{eval(tr[u << 1], tr[u].add, tr[u].mul);eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);tr[u].add &＃61; 0, tr[u].mul &＃61; 1;
}void build(int u, int l, int r)
{if (l &＃61;&＃61; r) tr[u] &＃61; {l, r, w[r], 0, 1};else{tr[u] &＃61; {l, r, 0, 0, 1};int mid &＃61; l &＃43; r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid &＃43; 1, r);pushup(u);}
}void modify(int u, int l, int r, int add, int mul)
{if (tr[u].l >&＃61; l && tr[u].r <&＃61; r) eval(tr[u], add, mul);else{pushdown(u);int mid &＃61; tr[u].l &＃43; tr[u].r >> 1;if (l <&＃61; mid) modify(u << 1, l, r, add, mul);if (r > mid) modify(u << 1 | 1, l, r, add, mul);pushup(u);}
}int query(int u, int l, int r)
{if (tr[u].l >&＃61; l && tr[u].r <&＃61; r) return tr[u].sum;pushdown(u);int mid &＃61; tr[u].l &＃43; tr[u].r >> 1;int sum &＃61; 0;if (l <&＃61; mid) sum &＃61; query(u << 1, l, r);if (r > mid) sum &＃61; (sum &＃43; query(u << 1 | 1, l, r)) % p;return sum;
}signed main()
{scanf("%lld%lld", &n, &p);for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; ) scanf("%lld", &w[i]);build(1, 1, n);scanf("%lld", &m);int op, l, r, c;for (int i &＃61; 1; i <&＃61; m; i &＃43;&＃43; ){scanf("%lld%lld%lld", &op, &l, &r);if(op &＃61;&＃61; 1){scanf("%lld", &c);modify(1, l, r, 0, c);}else if(op &＃61;&＃61; 2){scanf("%lld", &c);modify(1, l, r, c, 1);}else{printf("%lld\n", query(1, l, r));}}return 0;
}